KMF

지도의 (0, 0) 지점에서 (M-1, N-1)까지 내리막길로 이동할 수 있는 경로의 수를 구하는 문제이다. 다이내믹 프로그래밍을 사용하여 해결 할 수 있다. 다이내믹 프로그래밍에는 Bottom-up 방식인 Tabulation 기법과 Top-down 방식인 Memoization 기법이 존재한다. Tabulation 기법은 보통 반복문으로 구현하며, Memoization은 보통 재귀 함수로 구현한다. 메모리나 시간 복잡도를 고려하였을 때 Memoization에 비해 Tabulation이 더 효율적이지만 상황에 따라 다르게 적용될 수 있으므로 두 가지 방법 모두 알고있어야 한다. Tabulation 예제 // Tabulated version to find factorial x. int dp[MAXN]; //..

(r, c)를 방문한 순서를 구하는 문제이다. 분할 정복 알고리즘으로 해결할 수 있다. 브루트 포스를 통해 모든 셀을 방문하여 (r, c)에 대한 순서를 구할 수도 있지만 시간 초과가 발생한다. 따라서 이미 주어지는 r, c의 값을 가지고 최적화를 해야한다. 전체 배열의 시작점(가장 왼쪽 구석 지점)을 start_row, start_col이라 가정했을 때, 전체 배열을 4등분하고 각각의 배열 시작점과 끝점을 나타내면 아래와 같다. 시작: start_row, start_col 끝: start_row + 세로의 길이 / 2 -1, start_col+ 가로의 길이 / 2 - 1 시작: start_row, start_col+ 가로의 길이 / 2 끝: start_row + 세로의 길이 / 2 -1, start_c..

10 * 10 격자판의 1을 모두 덮는 최소 색종이 개수를 구하는 문제이다. 단순 반복문 보다는 백트래킹 알고리즘을 사용하면 쉽게 해결할 수 있다. 1. 색종이 사이즈 배열 S에 지금까지 사용한 색종이의 개수를 저장한다. 2. 재귀 함수를 사용한다. 열 번호를 하나씩 증가시키고 열 번호가 10일 경우 행 번호를 하나 증가시키고 다시 열번호를 0으로 초기화한다. 3. 열번호가 10일 경우 색종이의 총 개수를 반환하며, 가장 작은 경우를 출력한다. 색종이 사이즈가 s * s라고 할때 s에 0 - 4를 대입하여 반복한다. 만일 해당 색종이를 5장 미만 사용했다면 해당 구간의 배열을 완전탐색하여 모든 값이 1인 경우 색종이로 덮는다. 이는 1을 0으로 치환하는 것으로 대신한다. 덮은 후 열 번호를 s+1 증가시..

문제에 주어진 조건에 따라 그대로 구현하는 문제이다. 문제를 크게 두개로 나누면 낚시왕이 이동 후 상어를 낚는 것, 상어가 이동하는 것으로 나눌 수 있다. 낚시왕이 상어를 낚는 것 낚시왕은 1초가 지나면 오른쪽으로 이동한다. 이동한 열에서 가장 바닦에 가까운 상어를 낚는다. 상어가 이동하는 것 먼저 방향이 1, 2,(상, 하), 3, 4(우 ,좌)인 것을 나누어 생각한다. 그 중 3, 4인 것을 예로 설명 하겠다. 현재 위치(열 번호)와 끝 지점간 차이를 구한다. 이때 끝 지점은 방향이 3일 경우 C가 되고 4일 경우는 1이 될 것이다. 그 차이가 속도보다 크거나 같은 경우 현재 위치에서 속도를 뺀다. 이는 최대한 도달할 수 있는 지점이 끝 지점이기 때문에 방향을 바꾸어 돌아 오는 것을 생각하지 않아도 ..

N*M의 격자판에서 3명의 궁수를 위치시켜 잡을 수 있는 적의 최대를 구하는 문제이다. 궁수가 적을 잡는 경우 1. 궁수는 D 거리 이하에 있는 적만을 잡을 수 있다. 2. 궁수는 가장 가까운 적을 죽인다. 3. 그러한 적이 여러명 존재할 경우 가장 왼쪽에 위치한 적을 죽인다. 4. 같은 적을 죽일 수 있다. 궁수 배치하기 가능한 모든 궁수들의 배치를 구해야 하기 때문에 itertools 모듈의 combinations를 사용한다. 죽일 적 찾기 & 적 죽이기 D 거리 이하에 위치하고 가장 가까운 적을 찾기 위해서 BFS를 활용한다. 이때 파이썬의 heapq 모듈을 사용한다. 궁수와 적간의 거리, 궁수의 위치를 큐에 저장한다. 단 거리가 D를 초과하면 잡을 수 있는 적이 존재하지 않기 때문에 (-1, -1..

아기 상어가 N * N 크기의 공간을 먹이를 먹으면서 움직이는 최단 거리를 구하는 문제이다. 최단 거리를 구하는 알고리즘은 다양하게 존재하지만 이 문제는 BFS를 사용하여 해결할 수 있다. 파이썬의 heapq 모듈을 사용한다. heaq에는 아기 상어의 이동 횟수, 위치, 크기, 지금까지 먹은 물고기의 수가 저장된다. heapq 모듈은 가장 첫번째 원소를 기준으로 정렬하기 때문에 반드시 이동 횟수를 가장 처음에 위치해야한다. 먹이를 먹는 우선순위가 몇 가지 존재하는데 유의해야한다. 1. 가장 가까운 먹이를 우선적으로 먹는다 heapq모듈을 사용한 BFS로 자연스럽게 해결된다 2. 가장 가까운 먹이가 여러 마리일 경우, 가장 위쪽에 위치한 물고기를 먹는다. 또 그러한 물고기가 여러 마리인 경우 가장 왼쪽에 ..

문제를 제대로 읽고 봄, 여름, 가을, 겨울을 차례대로 구현한다면 쉽게 해결할 수 있는 문제이다. 다만 시간 초과가 발생하기 쉬운데 절대 배열을 매년 마다 정렬해서는 안된다. 나이가 5의 배수인 나무가 여덟 방향으로 번식을 하고, 새로 나타난 나무는 모두 1살이기 때문에 새로 나타난 나무들을 모두 배열의 끝쪽에 위치 시키면 다시 정렬할 필요가 없다. 그리고 (r, c)에 위치한 나무들은 이미 정렬 되어 있고, k 번째 부터 영양분 섭취를 하지 못해 죽었을 경우 이후 나무들은 모두 자료구조에서 제거 해준다.

도시에 존재하는 치킨 집을 M개 만큼 남기는 경우의 수 중 최소 치킨 거리를 구하는 문제이다. 모든 치킨 집 중 M개를 뽑는 조합을 구하면 쉽게 답이 도출된다. 다만 나는 시간 초과로 인해 조금 헤매었다. 그 이유는 지금까지 조합과 순열에 대한 차이를 인지하면서 알고리즘을 작성하지 않았던기 때문이다. 조합은 순서를 무시하기 때문에 [1, 2]와 [2, 1] 동일하다. 즉 [(1, 2), (3, 2)]에 위치한 치킨 집을 폐업 시키는 경우와 [(3, 2), (1, 2)]에 위치한 치킨 집을 폐업 시키는 경우가 동일한 것이다. 이러한 문제에 순열 알고리즘을 사용하였으니 시간초과가 발생하는 것이 당연한 것이었다. 순열과 조합 알고리즘의 간단한 예시는 아래와 같다. # 순열 li = [1, 2, 3, 4, 5,..

0세대: 1 1세대: 1 2 2세대: 1 2 3 2 3세대: 1 2 3 2 3 0 3 2 4세대: 1 2 3 2 3 0 3 2 3 0 1 0 3 0 3 2 ... 드래곤 커브의 시작 지점과 방향, 세대가 주어지며 드래곤 커브는 세대에 따라 확장된다. 네 꼭지점이 모두 드래곤 커브에 포함되는 1 * 1 크기의 셀 개수를 구하는 문제이다. 처음 문제를 풀 경우 세대마다 드래곤 커브를 구하고 이를 90도 회전하는 알고리즘을 생각할 수 있다. 하지만 이러한 알고리즘을 작성하면 매우 복잡해진다. 대신 드래곤 커브의 방향에서 규칙을 찾으면 문제가 간단해진다. 세대에 따른 선분의 방향을 구하면 아래와 같다. →(0)인 경우 0세대: 0 1세대: 0 1 2세대: 0 1 2 1 3세대: 0 1 2 1 2 3 2 1 4세..

사다리 게임에 주어진 사다리에 가로선을 추가하여 i번째 사다리 게임의 결과가 i가 나오도록 하는 문제이다. 문제 자체는 백트래킹 알고리즘으로 간단히 해결할 수 있다. 하지만 시간, 메모리 제한을 고려하여 최적화 해야한다. 사다리를 배열로 치환하고 (r, c)에 사다리가 있을 경우 1 또는 True, 없을 경우 0 또는 False로 표시한다. 그리고 사다리를 놓으며 따라 내려간다. 만약 i가 (i, c)에서 사다리를 만날 경우 i = i + 1, (i-1, c)에서 만날경우 i = i - 1을 수행한다. 반복마다 사다리를 타고 내려가 임의의 i에 대해서 결과가 i가 나오는지 확인한다.