Algorithm

[백준, Java] 1052번 : 물병

🔗 문제 링크 https://www.acmicpc.net/problem/1052 😮 문제 해결 방법 문제에서 같은 양이 들어있는 물병끼리 하나로 합칠 수 있고 처음에는 모든 물병에는 물이 1L가 들어있다고 제시되어 있다. 처음부터 두 개의 물병을 한 개의 병으로 합쳐가면, 2L → 4L → 8L 이런식으로 증가할 수 밖에 없다. 이는 물병이 2의 제곱 값이 되어야 병이 하나로 합쳐지는 것을 알 수 있다. N개의 물병을 K개의 물병으로 합치는 경우 최소 개수의 물병을 사기 위해선 남은 물병(N) 보다 작으면서 가장 큰 2의 제곱 값을 매번 구해 빼주는 작업을 K-1번 해주고, 그래도 물병이 남아있다면 마지막(K번째)에는 남은 물병으로 한 병을 만들어야 하므로 남은 물병보다 크면서 가장 작은 2의 제곱값을 ..

[백준, Java] 9663번 : N-Queen

🔗 문제 링크 https://www.acmicpc.net/problem/9663 😮 문제 해결 방법 첫 번째 행부터 차례로 모든 배치에 퀸을 놓아보는 방식의 완전탐색 문제이다. 퀸을 배치하기 전에 이전 행에 놓인 퀸 들이 움직일 수 없는 위치에 놓아야 하기 때문에 행 마다 퀸을 배치하면서 이전 행의 퀸의 배치와 겹치지 않는지 판단하는 로직을 추가한다. 이전 행의 퀸들과 겹칠 수 있는 경우는 2가지가 있다. 이전 행들에 놓인 퀸의 열과 현재 놓을 퀸의 열이 동일한 경우 이전 행들에 놓인 퀸과 현재 놓을 퀸이 대각선에 존재하는 경우 동일한 행에 퀸이 놓이는 경우도 고려해야하지만, 재귀를 이용해 한 행 (depth)마다 퀸을 배치할 것이기 때문에 동일한 행에 두 개이상의 퀸이 놓이는 경우는 발생하지 않는다. ..

[백준, Java] 18352번 : 특정 거리의 도시 찾기

🔗 문제 링크 https://www.acmicpc.net/problem/18352 😮 문제 해결 방법 문제의 조건에서 최대 300,000개의 도시가 입력으로 주어질 수 있다고 명시했기 때문에, 인접행렬 방식이 아닌 인접 리스트 방식으로 해결해야한다. 시작 도시부터 도달할 수 있는 모든 도시에 대해 최단거리를 구하는 알고리즘은 “다익스트라"를 사용할 수 있다. 물론, 해당 문제에서도 다익스트라 알고리즘을 사용할 수 있지만, 각 도시간 거리가 1로 고정이 되어있기 때문에 BFS를 이용해서도 문제를 해결할 수 있다. 출발 도시를 시작으로 BFS를 구현한다. 연결된 도시 중 방문하지 않고, 현재 도시에서 거리에 +1 한 값보다 연결된 도시 거리가 멀다면 최단 거리로 갱신한다. 시작 도시로 부터 도달할 수 있는 ..

[백준, Java] 1062번 : 가르침

🔗 문제 링크 https://www.acmicpc.net/problem/1062 😮 문제 해결 방법 문제에서 남극 단어의 시작과 끝은 anta, tica로 끝난다고 했기 때문에 a,n,t,i,c는 반드시 배워야 하는 글자이다. a,n,t,i,c를 포함해 남은 알파벳 중 k개를 조합한다. 조합한 알파벳을 남극 단어마다 해당 알파벳을 모두 포함하는지 판단하면서 배울 수 있는 단어를 체크한 후 현재 까지 최대로 배울 수 있는 단어 개수와 현재 배울 수 있는 단어 개수를 비교해서 갱신한다. a,n,t,i,c는 반드시 배워야 하는 글자이므로 K가 5보다 작다면 남극 단어를 배울 수 없기 때문에 0을 리턴한다. K가 5보다 크다면 이미 5개를 배웠기 때문에 a,n,t,i,c를 제외한 (K - 5)개의 글자를 백트래..

[백준, Java] 16928번 : 뱀과 사다리 게임

🔗 문제 링크 https://www.acmicpc.net/problem/16928 😮 문제 해결 방법 주사위를 조작할 수 있다고 문제에서 제시했기 때문에 매 위치마다 1~6번까지의 주사위를 던진 후 위치를 담은 Node 객체에 다음 위치와 다음 거리(주사위 던진 개수)를 넣어 큐에 넣어주었다. 매 주사위 굴린 후의 위치에서는 뱀과 사다리가 있는 칸인지 먼저 확인한다. 뱀과 사다리가 있는 칸인 경우 주사위를 한번 굴린 것으로 뱀과 사다리를 탄 이후의 칸으로 이동이 가능하기 때문에 뱀과 사다리 탄 이후 칸 거리 배열에 현재까지 위치의 주사위 개수 + 1을 한 값을 넣어준다. 뱀과 사다리가 없는 칸인 경우 주사위 굴린 이후의 칸 거리 배열에 현재 까지의 주사위 개수 + 1 한 값을 넣어준다. 현재 큐의 칸이 ..