밤이 블로그

BOJ#1541 잃어버린 괄호 * 문제https://www.acmicpc.net/problem/1541 * 풀이문제 풀이 과정 55-50+40-10-30-20+40 int minSum = 0; 1. 입력받은 String을 "-"를 기준으로 분리합니다. {55, 50+40, 10, 30, 20+40} 2. 첫번째 원소는 그냥 더해주고 (문제 조건에 따라 첫번째 숫자는 양수이다)minSum = 55; 3. 나머지 각각의 원소에 대하여 합을 구한 뒤 minSum에서 빼줍니다. {55, 50+40, 10, 30, 20+40}{55, 90, 10, 30, 60} minSum = 55 - 90 - 10 - 30 - 60; * 나의 코드https://github.com/stack07142/BOJ/blob/697a29..

BOJ#14502 연구소 * 문제https://www.acmicpc.net/problem/14502 * 풀이2017년 상반기 삼성 SW 역량평가 기출문제 입니다. 벽을 항상 3개 설치해서 안전영역의 최대값을 구해야 하는 문제입니다.즉, 완전 탐색이 필요합니다. (모든 경우를 다 해봐야 최대값을 구할 수 있음) 저는 아래와 같이 풀어보았습니다. 1. 조합을 돌려서 Map에서 빈칸 3개를 선택한 후 벽으로 바꿔줍니다. 최대 8*8 맵에서 빈칸 3개를 선택할 때 경우의 수 = (64-2)C3(바이러스가 최소 2개 있으므로) 2. 해당 Map에서 바이러스를 퍼뜨립니다. 3. (맵의 크기 - 바이러스의 수 - 벽의 수) 의 최대값을 갱신합니다. 4. 1~3 반복 * 나의 코드 https://github.com/s..

BOJ#14501 퇴사 * 문제https://www.acmicpc.net/problem/14501 * 풀이2017년 상반기 삼성전자 SW 역량테스트 기출문제입니다. dp 문제입니다. 각 경우(상담)에 대해 상담하는 경우, 상담하지 않는 경우 2가지 경우로 나눌 수 있습니다. 정의 및 점화식dp[idx] : 날짜가 idx 일 때, 이후 얻을 수 있는 금액의 최대값dp[idx] = max(dp[idx+1], dp[idx + T[idx]] + P[idx]) * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%2314501_Retire/src/Main.java import java.io.BufferedReader; import java.io.IOException..

BOJ#14503 로봇 청소기 * 문제https://www.acmicpc.net/problem/14503 * 풀이2017년 상반기 삼성전자 SW 역량테스트 기출문제입니다.설명할 것이 없는 문제입니다. 문제 조건에 맞게 구현하시면 됩니다. * 나의 코드https://github.com/stack07142/BOJ/blob/442d75f4db250b3532123d0ae00bd92b50daef30/BOJ%2314503_RobotCleaning/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * BOJ#1..

NP, NP-Hard http://www.valken.net/274

BOJ#14500 테트로미노 * 문제https://www.acmicpc.net/problem/14500 * 풀이2017년 상반기 삼성전자 SW 역량테스트 기출 문제입니다. 테트로미노에서 dfs로 탐색 가능한 블록이 있고, 탐색 불가능한 블록(ㅓ, ㅗ, ㅜ, ㅏ)이 있습니다.즉, dfs로 탐색 + (ㅓ,ㅗ,ㅜ,ㅏ)에 대해 탐색을 하면 답을 얻을 수 있습니다. (ㅓ,ㅗ,ㅜ,ㅏ) 탐색 아이디어는 다음과 같습니다. 현재 위치가 (row, col)일 때(row, col)값과 (row, col)에서 상,하,좌,우 4방향 값을 모두 더해줍니다. 그리고 4방향 값에서 최소 값을 다시 빼줍니다.= 현재 위치 값 + 4방향 sum - 4방향 값 중 최소값 즉 플러스 + 모양에서 4방향 중 가장 최소값을 빼면 (ㅓ,ㅗ,ㅜ,..

BOJ#1600 말이 되고픈 원숭이 * 문제https://www.acmicpc.net/problem/1600 * 풀이bfs 탐색 문제입니다.일반적인 격자(상,하,좌,우) 문제에서 말처럼 이동하는 부분이 추가되었다고 생각하면 됩니다. 즉, 각 위치에서 상하좌우(4방향) + 말(8방향) 이렇게 12가지 방향으로 탐색을 진행하면 됩니다.문제는 중복된 정점을 다시 방문하지 않도록 처리하는 것입니다. 처음에 제가 실수했던 점은 discovered[row][col][말로 방문한 경우 or 원숭이로 방문한 경우] 로 중복된 정점을 처리했었는데 이것의 반례로 아래의 예가 있습니다. 15 50 1 1 0 10 0 1 0 10 0 0 1 10 1 0 1 01 1 0 1 0 정답 : 6 말의 움직임에 의해 (2,1)에 위치..

BOJ#1263 시간 관리 * 문제https://www.acmicpc.net/problem/1263 * 풀이일상 생활에서 흔히 하는 고민을 다룬 문제인 것 같습니다. 😅(내일 무슨 무슨 일을 언제까지 해야 되니까, 몇시쯤 집에서 나가면 되겠구나! ) 첫째 줄에 일의 개수 N,그 다음 N개의 줄에 T와 S가 주어집니다. ( T : 필요한 시간, S : 납기 ) 일단 S 기준으로 오름차순 정렬을 합니다. 내림차순으로 해도 상관없습니다. 3 58 141 165 20 0시 부터 일을 시작할 수 있으므로가장 마지막 일(4번째 일)을 끝내기 위해서는 15시에는 일을 시작해야 합니다. 그리고 이것은 3번째 일에 영향을 주게 됩니다. 3 58 141 16 155 20 이어서 3번째 일을 끝내기 위해서는 14시에는 일을..

BOJ#3190 뱀 * 문제https://www.acmicpc.net/problem/3190 * 풀이map과 direction 2차원 배열을 선언하였습니다. map이 가질 수 있는 값 : 0(빈칸), 1(뱀), 2(사과) direction이 가질 수 있는 값 : 상, 하, 좌, 우→ 각 위치(row, col)에서 머리 또는 꼬리가 어느 방향으로 이동해야 하는지 알기 위함 시뮬레이션 진행 알고리즘은 아래와 같고, 중간 중간에 map과 direction 정보를 업데이트해서 답을 찾을 수 있게 하였습니다. 머리 이동 - 맵을 벗어난 경우 - 종료 - 빈칸인 경우 - 꼬리 이동 - 사과인 경우 - None - 뱀인 경우 - 종료 ↓ 테스트 케이스 보기 (클릭) ↓5054 D8 D12 D15 D20 L 20 83..

BOJ#2931 가스관 * 문제https://www.acmicpc.net/problem/2931 * 풀이이 문제는 어려운 문제인지, 쉬운 문제인지 헷갈리네요. - 삭제된 노드는 단 1개이고 쉽게 찾을 수 있다. (출발점에서 파이프를 따라가보면 삭제된 노드가 나온다)- 위치는 구했고 거기에 맞는 파이프만 찾으면 되는데 노드에서 출입구가 몇개이고 어느 방향으로 뚫려있는지만 알면? 파이프를 구할 수 있다. 쉽다고 생각하면 쉬운데,,,정형화된(?) bfs, dfs 탐색으로는 어떻게 풀까? 문제 의도는 뭘까 아무튼 bfs, dfs 몰라도 자기 생각을 코드로 옮길 수 있으면 이 문제는 쉽게 풀 수 있을 것 같습니다.입사 시험에 적당한 문제 ↓ 테스트 케이스 보기 (클릭) ↓4 4Z...|...|....--M 4 1..