KMF

문제를 제대로 읽고 봄, 여름, 가을, 겨울을 차례대로 구현한다면 쉽게 해결할 수 있는 문제이다. 다만 시간 초과가 발생하기 쉬운데 절대 배열을 매년 마다 정렬해서는 안된다. 나이가 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가 나오는지 확인한다.

사무실에 설치된 CCTV는 위 다섯가지 중 하나이다. CCTV가 감시할 수 있는 방향은 위와 같고 90도 회전이 가능하다. 이때 최소 사각지대의 크기를 구하는 문제이다. N의 최대 크기가 8이기 때문에 백트래킹, 브루트 포스 알고리즘을 통해 해결할 수 있다. 1. 각 CCTV가 감시할 수 있는 방향을 구한다. 예를 들어, 1번은 상, 하, 좌, 우 각 한 방향씩 감시 가능하다. 2번 CCTV는 상하, 좌우 두 방향 감시가 가능하다. 2. CCTV를 모두 설치할 경우 사각지대의 크기를 구한다. from sys import stdin readline = stdin.readline def main(): cctvs = [] _map = [] for i in range(N): row = list(map(int, ..

재귀함수를 처음 배울 때 배우는 대표적인 문제중 하나인 N-Queen이다. 재귀를 통해 지정한 위치에 Queen을 놓는데 조건이있다. 이전에 놓았던 Queen과 일직선 혹은 대각선 상에 위치하지 않아야한다. 이를 확인하기 위해서 2가지를 확인 해야한다. 1. 일직선상에 위치하는 가? 동일한 행에는 Queen이 놓여있지 않기 때문에 이전에 놓았던 Queen 중 같은 열에 위치하는 지 확인한다. 2. 대각선상에 위치하는 가? 대각선상에 위치 한다는 것은 두 위치의 가로의 차와 세로의 차의 비교를 통해 확인 가능 하다. 만일 같을 경우 대각선상에 위치하는 것이다. 1, 2번 조건을 확인하기 위해서는 보통 열의 번호를 담고있는 배열 하나를 사용하여 반복문을 통해 확인하지만 직선, 대각선1(\), 대각선2(/) ..

N * N 크기의 보드 게임을 구현하는 문제이다. 특별한 알고리즘은 사용되지 않지만 숫자 블록의 상, 하, 좌, 우 이동을 구현하는 부분에서 꽤 까다로웠다. 네 방향 중 하나만 제대로 구현한다면 나머지는 쉽게 구현할 수 있다. 설명은 코드 주석으로 대신한다. from sys import stdin, setrecursionlimit setrecursionlimit(10 ** 6) readline = stdin.readline def main(): N = int(readline().strip()) _map = [list(map(int, readline().split())) for _ in range(N)] print(dfs(_map, N, 0)) def dfs(_map, N, moves): if moves ..

각 사건 중 순서를 알고있는 경우가 주어지고, 주어진 테스트 케이스에서 순서를 판별하는 문제이다. 보통 일의 순서를 알아내는 방법으로는 위상정렬이 존재하기 때문에 위상정렬을 먼저 시도했었지만 해결하지 못했다. 그리고 사건의 순서에 대한 정방향 그래프와 역방향 그래프를 그려 DFS를 사용하였으나 시간초과로 인해 해결하지 못하였다(시간 초과를 제외하면 해결 됐을 거라 생각한다). 결국 문제의 분류를 보게 되었는데 플로이드-와샬로 분류되어있었다. 전혀 플로이드-와샬 알고리즘으로 접근할 생각 조차 하지 못했기 때문에 몇시간이 주어져도 해결하지 못했을 것이다. 일의 순서를 판별하는 문제에 최단거리 알고리즘도 사용이 가능하다는 것을 새겨 놓아야겠다. 플로이드-와샬 알고리즘을 사용하여 문제를 해결 할 수 있는 이유는..

그래프에 음의 사이클이 존재하는 지를 판단하는 문제이다. 음의 사이클을 발견할 수 있는 알고리즘은 플로이드-와샬, 벨만-포드, SPFA 알고리즘 세 가지가 있다. 시작점이 정해지지 않아 모든 시작점에 대해서 SPFA 알고리즘을 사용하여 해결했다. 하지만 시간이 너무 오래걸려 다른 풀이를 살펴보니 시작점을 특정하고 벨만-포드 알고리즘을 사용하면 해결되었다. 이에 대해서 명확한 글은 없었지만, 무향 그래프이고 단순히 음의 사이클 여부만 판단하면 되기 때문에 벨만-포드 알고리즘을 사용한 것 같다. 한 가지 의문은 특정 시작점에 대해서 SPFA는 해결되지 않는다는 것인데 이는 시간을 가지고 알아봐야 할 것 같다. from sys import stdin readline = stdin.readline INF = 1..

한 도시에서 출발하여 나머지 도시까지의 최단 거리를 구하는 문제이다. 간선의 가중치에 음수가 존재할 수 있기 때문에 다익스트라 알고리즘을 사용할 수 없다. 음수 가중치를 가지는 간선이 있는 경우 최단 경로를 구하는 알고리즘은 플로이드-와샬, 벨만-포드 알고리즘이 존재한다. 하지만 문제에서 1번 도시에서 출발한다고 명시하였기 때문에 벨만-포드 알고리즘을 사용하는 것이 효율적일 것이다. 하지만 벨만-포드 알고리즘을 사용하면 시간초과가 발생한다. 따라서 벨만-포드 알고리즘을 최적화한 SPFA(Shortest Path Faster Algorithm)을 사용해야한다. 벨만-포드 알고리즘은 사이클이 발생하지 않게 하기 위해서 정점의 개수 - 1 만큼의 반복을 통해서 최단 경로를 구한다. 하지만 이 경우 반드시 정점..