Tech Diary Tech Diary

[백준(BOJ)] 2001_보석 줍기 JAVA 문제 : BOJ_2001번 보석 줍기 문제 설명 최대 100개의 섬이 있고 각 섬마다 최대 한 가지의 양방향 다리로 연결되어 있습니다. 각 섬마다 보석이 있는 섬과 없는 섬이 있고, 다리마다 보석을 견딜 수 있는 수가 정해져있습니다. 1번 섬에서부터 시작하여 1번 섬으로 다시 돌아와야 하는데, 이때 최대한 모을 수 있는 보석의 수를 구해야 합니다. 방문했던 다리와 섬은 다시 방문할 수 있고 섬에 있는 보석을 가져가거나 가져가지 않을 수도 있습니다. Solution 비트 마스킹 & bfs 각 섬을 지나갈 때 몇 개의 보석을 들고 있어야 하는지, 또 해당 섬에서 보석을 가져가는 게 유리한지 아닌지를 알 수 없기 때문에 모든 탐색이 필요합니다. 이를 위해 비트 마..

[백준(BOJ)] 9252_LCS 2 JAVA 문제 : BOJ_9252번 LCS 2 문제 설명 두 개의 문자열이 있고, 그 문자열의 공통부분 수열 중 가장 긴 수열을 찾는 것이다. 기존의 LCS 문제와 다른 점은 수열의 길이뿐만 아니라 수열이 어떤 문자열인지 출력해야 한다. Solution DP dp[i][j] = 첫 번째 문자열의 인덱스가 i, 두 번째 문자열의 인덱스가 j 일 때 공통부분 수열의 최댓값 이라고 정의하자. 첫 번째 문자열의 i 번째 문자와 두 번째 문자열의 j 번째 문자가 같다면, dp[i][j] = dp[i-1][j-1] + 1로 dp 값을 할당한다. i와 j의 이전 하나 이전 인덱스의 dp 값에서 두 문자가 같다면 공통부분 수열의 길이가 늘어나므로 1을 더해주는 식이다. 첫 번째 문..

[백준(BOJ)] 18405_경쟁적 전염 JAVA 문제 : BOJ_18405번 경쟁적 전염 문제 설명 NxN 크기의 시험관에서 바이러스가 매초 상하좌우로 증식한다. 이때 바이러스는 기존의 바이러스가 있는 자리엔 증식할 수 없으며 바이러스마다 증식하는 우선순위 번호가 주어진다. 주어지는 시간(s)에 주어지는 장소(x,y)에 어떤 바이러스가 있는지 출력하는 문제이다. Solution bfs bfs를 이용해서 바이러스가 상하좌우로 증식할 때 자료구조에 넣어지는 식으로 풀 수 있다. 다만, 바이러스가 증식하는 우선순위 번호가 있기 때문에 단순한 queue 구조로는 해결할 수 없다. 여러 가지 방법이 있지만 temp list를 선언해서 새로 생성되는 바이러스들을 넣어준 뒤, 한 번의 바이러스 증식이 끝난 뒤에 기..

[백준(BOJ)] 15686_치킨 배달 JAVA 문제 : BOJ_15686번 치킨 배달 문제 설명 N*N 크기의 map에서 집과 치킨집이 주어진다. 최대 m 개의 치킨집을 제외한 나머지 치킨집을 다 없애야 한다. 이때 집과 치킨집과의 최소 거리(수직거리의 차 + 수평거리의 차)의 합의 최솟값을 구해야 한다. Solution 완전 탐색(조합) N의 최대 크기는 50, M의 최대 크기는 13이다. 13개의 치킨집에서 7개의 치킨집을 선택하는 조합의 수가 가장 크므로 다음과 같이 계산해보면, 50 * 50(도시의 최대 크기) * 13C7 * 7(모든 경우의 수마다 7개의 치킨집과 거리를 확인해봄) == 30,030,000 이므로 조합을 이용한 완전 탐색으로 해결이 가능하다. Description 조합은 rec..

[백준(BOJ)] 16236_아기 상어 JAVA 문제 : BOJ_16236번 아기 상어 문제 설명 아기 상어가 상하좌우로 움직이면서 물고기를 먹습니다. 이때 물고기는 아기 상어의 크기보다 작은 물고기만 먹을 수 있고, 상어의 크기보다 큰 물고기가 있는 곳은 지나갈 수 없습니다. 가장 가까운 거리에 있는 먹을 수 있는 물고기부터 먹는데, 같은 거리에 있는 물고기가 여러 물고기라면 위 다음 왼쪽에 있는 물고기부터 먹습니다. 또 한 자기의 몸 크기 수만큼의 물고기를 먹으면 몸의 크기가 1 증가합니다. 이러한 조건에서 물고기가 한 번 이동하는 시간을 1초라고 할 때 물고기가 먹을 수 있는 모든 물고기를 먹는데 걸리는 시간을 출력해야 합니다. Solution bfs, 완전 탐색 우선 bfs로 상어의 위치부터 시작..

[백준(BOJ)] 2887_행성 터널 JAVA 문제 : BOJ_2887번 행성 터널 문제 설명 3개의 좌표 (x,y,z)로 된 N 개의 행성이 있습니다. 두 행성을 연결할 수 있는 비용은 행성의 각 좌표의 차 중 최솟값이라고 합니다. 이때 모든 행성을 터널로 연결할 때 최소 비용을 구하는 문제입니다. Solution 크루스칼 알고리즘 모든 노드를 연결하는 최소 비용의 터널을 구해야 하기 때문에 크루스칼 알고리즘을 사용해야 합니다. 주어진 터널이 없기 때문에 터널들을 비교하면서 최솟값의 터널을 찾아야 합니다. 이때 행성의 개수는 최대 100,000이 주어지므로, 모든 행성을 서로 비교해 준다면 시간 초과가 발생합니다. 잘 생각해 보면 행성 간의 최솟값은 항상 x, y, z 값의 차의 최솟값 중 하나이기 때..

[Programmers] 기둥과 보 설치(2020 KAKAO BLIND RECRUITMENT) JAVA 문제 : 기둥과 보 설치(2020 KAKAO BLIND RECRUITMENT) 문제 설명 N*N의 벽면이 주어지고 이 벽면에 기둥과 보를 설치, 삭제하는 문제입니다. 기둥은 다른 기둥의 위, 혹은 보의 양 끝 쪽에 설치될 수 있습니다. 보는 양 끝 점 중 한점에 기둥이 있거나, 양 끝 점에 보가 설치되어 있을 시 설치될 수 있습니다. 입력으로 원하는 기둥과 보의 설치, 삭제 유무와 좌표가 주어지며, 출력으로 설치, 삭제가 가능할 때 실행한 뒤의 최종 결과를 출력하는 것이 문제입니다. Solution 구현, 완전 탐색 입력값을 받은 뒤, 이 입력값을 최종 배열에 삽입합니다. 그 후 삽입한 결과(삭제나 설..

[백준(BOJ)] 3190_뱀 JAVA 문제 : BOJ_3190번 뱀 문제 설명 매초 움직이면서 꼬리를 늘려가는 뱀 게임을 구현하는 문제입니다. N*N 크기의 맵이 주어지고, 사과가 있는 각각의 위치와 뱀이 방향을 바꾸는 순간이 주어집니다. 이때 뱀이 움직인 방향에 사과가 있다면 사과를 먹고 꼬리가 늘어나지만, 사과가 없다면 기존의 꼬리 부분이 사라지고 뱀의 머리 부분이 늘어납니다. 또한 방향은 최초에 오른쪽으로 이동하며 이동방향을 기준으로 오른쪽이나 왼쪽으로 90도 회전할 수 있습니다. Solution 구현 문제에서 주어진 대로 구현을 하면 됩니다. 뱀의 현재 머리 위치와 꼬리 위치를 계속 기록해 주면서, 이동한 곳에 사과가 있으면 머리 위치만 수정해 주고, 사과가 없을 시엔 꼬리 위치도 함께 수정해 ..