기록

문제 보기 이 문제는 백트랙킹(Backtracking) 문제이다. 상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 구해야 한다. 상어가 먹을 수 있는 물고기가 여러 개 일 때 번호가 가장 높은 것을 먹는다고 최종적으로 최댓값이 된다는 보장이 없다. 따라서 모든 경우에 대해서 끝까지 진행하고 최종적으로 판단해야 한다. 알고리즘 구현 과정은 아래와 같다. 1. 현재 상어 위치에 있는 물고기를 먹는다. 2. 모든 물고기를 이동시킨다. 3. 상어가 먹을 수 있는 물고기를 파악한다. 4. 3번의 모든 경우에 대해서 dfs 탐색을 진행한다. 코드 import copy dx = [-1, -1, 0, 1, 1, 1, 0, -1] dy = [0, -1, -1, -1, 0, 1, 1, 1] def food(array, ..

문제 보기 이 문제는 BFS 문제이다. 아기 상어가 상, 하, 좌, 우로 움직이면서 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 구해야 한다. 아기 상어의 움직임은 전형적인 BFS로 처리하면 된다고 생각하였고, 아기 상어가 이동 위치를 결정하는 방법에 대해 고민하였다. 그 결과 해당 위치에서 아기 상어가 먹을 수 있는 물고기 정보를 모두 구한 후 정렬을 사용하여 해결하였다. 알고리즘 구현 과정은 아래와 같다. 1. 현재 아기 상어 위치에서 먹을 수 있는 물고기를 파악한다. - 먹을 수 있는 물고기가 없으면 종료한다. 2. 정렬을 통해서 가장 가까운 물고기를 구하고 먹는다. 3. 현재 아기 상어의 크기만큼 물고기를 먹었다면 아기 상어의 크기 정보를 1 증가시킨다. 코드 from c..

문제 보기 이 문제는 그리디 문제이다. 크레인을 통해서 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구해야 한다. 크레인의 값과 박스의 값을 무작위가 아닌 큰 값부터 순차적으로 진행하는 것이 가장 효율적이라고 생각하였다. 알고리즘 구현 과정은 아래와 같다. 1. 크레인과 박스 값을 내림차순으로 정렬한다. 2. 상자를 옮겼는지 확인하기 위한 Flag 배열을 추가하였다. 3. 모든 크레인 값을 순회하면서 해당 크레인이 옮길 수 있는 가장 큰 상자를 옮기고 Flag 값을 1로 업데이트한다. 4. 모든 Flag 값이 1이면(Count = M) 반복문을 종료한다. 추가적으로 상자의 값을 크레인이 담을 수 없는 경우는 모든 박스를 배로 옮길 수 없으므로 따로 처리하였다! 코드 from collections im..

문제 보기 이 문제는 DFS 문제이다. N이 주어졌을 때 수식의 결과가 0이 되는 모든 수식을 찾는 프로그램을 작성해야 한다. 모든이라는 글자가 나오면 자연스럽게 완전 탐색(Brute Force)을 생각하게 된다. 또한 자연수 N의 범위가 크지 않아서 완전 탐색으로도 충분히 구현 가능할 것이라고 생각하였다. 시간제한이 충분하지 않을 때는 BFS를 많이 사용하지만 여유로우면 DFS를 즐겨 사용한다. 해당 문제는 위에서 말했듯이 시간제한이 여유로웠으며 순차적으로 연산('+', '-', '')을 삽입하는 DFS가 가장 구현하기 편해 보였다. 알고리즘 구현 과정은 아래와 같다. 1. 1 ~ N의 값을 갖는 리스트를 생성한다. 2. 숫자 사이에 연산을 대입한다. ('+', '-', '' 모든 경우를 고려한다) 3..

문제 보기 이 문제는 플로이드 와샬(Floyd Warshall) 문제 이다. 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하면 된다. 하나의 경로가 아닌 모든 경로를 구해야하기 때문에 플로이드 와샬이 적합하다. 사실 문제 이름을 통해서 플로이드 와샬을 유추할 수도 있다..! 플로이드 와샬을 구현하는 것은 어렵지 않으나, 3중 for문이기 때문에 n값이 작을때만 가능하다는 점을 유의해야 한다. i에서 j로 가는 비용과 i에서 k를 거치고 j로 가는 경우를 계속해서 비교하면 된다. for k in range(N): for i in range(N): for j in range(N): d[i][j] = min(d[i][j], d[i][k] + d[k][j]) 코드 im..

문제 보기 이 문제는 이분 탐색(Binary Search) 문제이다. 주어진 기타 레슨을 M개 이하의 구역으로 분리하는 블루레이 크기 중 최솟값을 출력하면 된다. 이분 탐색을 진행하기 위해서 Left, Right를 아래와 같이 초기화하였다. Left = sum(기타 레슨) // M Right = sum(기타 레슨) answer(최종답) = Right 위 과정을 진행한 후 본격적인 이분 탐색 과정은 다음과 같다. 1. mid값을 구한다. (left + right) // 2 2. mid값이 기타 레슨의 최댓값보다 작은지 판단한다. - 작다면 기타 레슨을 담을 수 없으므로 left = mid + 1로 업데이트한다. 3. mid값으로 기타 레슨을 M개 이하의 구역으로 나눌 수 있는지 판단한다. - 나눌 수 있다..

문제 보기 이 문제는 백트랙킹(Backtracking) 문제이다. N의 최댓값이 16이기 때문에 dp가 아닌 백트랙킹으로도 충분히 통과할 수 있다고 생각하였다. 파이프의 한쪽 끝을 (N, N)으로 이동시키는 방법의 수를 구해야 한다. 파이프는 이동하는 방향을 통해 다른 한쪽을 추측할 수 있으므로 바깥쪽 칸만 저장한다. (실제로는 추측할 필요도 없다) 알고리즘 과정은 아래와 같다. 1. 인덱스가 (N - 1, N - 1)인지 확인한다. 2. 가로 방향으로 이동할 수 있는지 파악한다. - (현재 방향(가로 or 대각선)과 이동하고자 하는 위치 벽인지 확인) 3. 세로 방향으로 이동할 수 있는지 파악한다. - (현재 방향(세로 or 대각선)과 이동하고자 하는 위치 벽인지 확인) 4. 대각선 방향으로 이동할 수..

문제 보기 이 문제는 DP 문제이다. N명의 아이들을 번호 순서대로 옮기는 최소한의 수를 구하면 된다. 최소한의 수를 구하기 위해서는 움직이지 않아도 되는 아이들을 구하면 된다. 움직이지 않아도 되는 아이들은 현재 번호 순서에서 가장 긴 증가하는 수열에 해당한다. 알고리즘 과정은 아래와 같다. 1. 가장 긴 증가하는 수열을 구한다. 2. 전체 인원수에서 가장 긴 증가하는 수열의 길이를 뺀다. 코드 if __name__ == "__main__": N = int(input()) # 아이들의 수 people = [int(input()) for _ in range(N)] # 아이들 번호 순서 정보 # 2차원 dp dp = [[0] * N for _ in range(N)] # 가장 긴 증가하는 부분수열 for i..

문제 보기 이 문제는 BFS이다. 개인적으로 골드 5 난이도에서 가장 어려웠다. BFS를 구현하는 것은 어렵지 않았으나, BFS를 적용하기 위해서 가장 바깥쪽 테두리를 파악하는 게 핵심이었다. 처음에는 단순하게 적용하였다. 상, 하, 좌, 우를 살펴보면서 0이 있으면 가장 바깥쪽이다라고 생각하고 구현하였지만 틀렸다. 그 이유는 내부 0과 외부 0을 구별하지 못했기 때문이다. 따라서 내부 0과 외부 0을 구별하기 위해서 총 2단계의 BFS를 진행하였다. (0, 0)은 무조건 외부 0이기 때문에 (0, 0)을 큐에 넣은 후 연결된 모든 0을 -1로 바꿔줌으로써 내부 0과 외부 0을 구별하였다. 알고리즘 순서를 정리하자면 아래와 같다. 1. 외부와 내부 0을 구분한다. 2. 치즈를 모두 담은 큐를 대상으로 b..

문제 보기 이 문제는 DP 문제이다. 처음에는 완전 탐색(BFS)으로 접근을 하였다. 전체 반복 횟수가 최대 100이라는 것만 생각하였으며 반복하는 동안 큐의 삽입, 삭제 연산 횟수까지 고려하지 못했었다. 문제점을 찾은 후 시간 복잡도를 줄이기 위하여 DP를 생각하였다. 이전의 숫자 정보를 계속해서 가지고 있어야 하기 때문에 1차원 DP로는 불가능하였고 2차원 DP로 구현하였다. dp[i][j] = i번째 숫자까지 연산을 진행했을 때 j값을 나타낼 수 있는 경우의 수 위 식을 생각한 후 코드를 구현하는 것은 어렵지 않았다. 1. 입력받은 수를 num_list의 리스트에 대입 2. dp의 크기 (N - 1) * 21로 선언한 후 0으로 초기화 - 행의 크기가 N - 1인 이유는 최종적인 값을 계산하기 위한..