사무실에 설치된 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 만큼의 반복을 통해서 최단 경로를 구한다. 하지만 이 경우 반드시 정점..
최단 경로에 속한 경로를 모두 제외한 '거의 최단 경로'를 구하는 문제이다. 최단 경로를 먼저 구해야 하기 때문에 다익스트라 알고리즘을 사용하였다. 다익스트라 알고리즘을 구현할 때 경로를 구하기 위해서 이전 노드를 저장한다. 기존의 다익스트라와 다르게 이전 노드 하나만 저장하는 것이 아니라 모두 저장해야 다익스트라를 여러번 사용하지 않는다. (처음에 하나만 저장 했다가 시간초과가 발생하였다.) 그리고 모든 최단 경로를 구하기 위해서 distance[v] >= distance[u] + weight(v)와 같이 비교하였는다. 하지만 위와 같이 작성하면 방문할 노드를 담고있는 우선순위 큐에 불필요한 노드가 삽입되기 때문에 메모리 초과가 발생한다. 따라서 distance[v] > distance[u] + wei..
주어진 수를 목표 숫자로 만들기 위한 최소한의 연산을 구하는 문제이다. 간단하게 BFS를 동해서 해결이 가능하다. 하지만 알고리즘 구현 중 여러 실수를 하였다. 1. 단순히 최소한이라는 말에 혹하여 우선순위 큐를 사용하였다. BFS를 통해 트리를 그려보면 일반적인 큐와 우선순위 큐가 동일하게 작동한다. 2. 중복되는 수를 고려하지 않았다. 연산을 통해 만들어지는 수가 중복 될 수 있음이 명확하지만 이를 고려하지 않았다. 방문 배열을 통해 이전에 만들어진 수 인지 확인해야한다. from sys import stdin from collections import deque readline = stdin.readline def get_min_command(): init, target = map(int, read..
주어진 그래프를 이분 그래프인지 판별하는 문제이다. 가장 중요한 점은 이분 그래프를 판별하는 알고리즘이다. 처음에는 사이클이 생길 경우 반드시 이분 그래프가 될 수 없다고 생각하였다. 하지만 4개의 정점이 사각형 형태의 그래프를 형성할 경우를 가정해보면, 사이클이 생겨도 이분그래프가 될 수 있다. 결국 문제를 해결하지 못해 풀이를 찾아보았다. 대표적인 풀이는 노드마다 색을 칠하는 것이다. DFS, BFS 모두 가능하며 방문한 노드의 인접한 노드중 이미 방문한 노드의 색이 현재 노드의 색과 동일할 경우 이분 그래프가 될 수 없다. 여기서 유의 해야할 점은 모든 그래프가 연결 그래프라는 보장이 없다는 것이다. 그리고 비연결 그래프라고 할 지라도 이분 그래프라는 보장이 없기 때문에 모든 노드를 방문하여 색을 ..
0과 1로 이루어진 이미지 배열을 압축하는 쿼드트리 문제이다. 배열의 크기 N이 2의 제곱 수로 주어지는 것을 보았을 때 분할정복 기법으로 쉽게 해결할 수 있다. 좌상단, 우상단, 좌하단, 우하단 4가지 배열로 나눌 수 있으며, 각 셀의 값이 모두 동일한 경우에는 해당하는 숫자 하나만 출력하고 그렇지 않을 경우에는 해당하는 셀의 값을 출력해야한다. 배열을 나누는 방법으로는 시작 좌표 x, y 와 배열의 크기 n을 통해서 나눌 수 있다. 좌상단 = x, y 우상단 = x+n/2, y 좌하단 = x, y+n/2 우하단 = x+n/2, y+n/2 from sys import stdin readline = stdin.readline def compress_arr(): arr = input_arr.copy() d..