KMF

한 도시에서 출발하여 나머지 도시까지의 최단 거리를 구하는 문제이다. 간선의 가중치에 음수가 존재할 수 있기 때문에 다익스트라 알고리즘을 사용할 수 없다. 음수 가중치를 가지는 간선이 있는 경우 최단 경로를 구하는 알고리즘은 플로이드-와샬, 벨만-포드 알고리즘이 존재한다. 하지만 문제에서 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..

요세푸스 순열을 구하는 문제이다. 요세푸스 순열을 구할때 유의해야할 점은 배열이 순환한다는 것이다. 이는 배열의 인덱스를 구할때 인덱스가 배열의 크기보다 큰 경우 인덱스는 K-1만큼 커진다. from sys import stdin readline = stdin.readline def get_ys_seq(): idx = K - 1 stack = [i+1 for i in range(N)] result = [] for _ in range(N): if len(stack)

DFS를 사용한다는 것 말고는 제대로된 접근도 하지 못한 문제이다. 임의의 한 노드를 얼리어답터로 할 것인지 하지 않을 것인지 기준을 잡는 것이 중요하다. 1. 현재 노드가 얼리어답터일 경우: 자식 노드는 얼리어답터일 수도 아닐 수도 있다. 2. 현재 노드가 얼리어답터가 아닐 경우: 자식노드는 반드시 얼리어답터이어야 한다. 다음으로는 점화식을 만들어야 한다. 얼리어답터인 경우를 0, 그렇지 않을 경우를 1로 하고 2차원 배열을 선언한다. DP 노드는 현재 노드가 얼리어답터일 경우 최소 얼리어답터 수와 현재 노드가 얼리어답터가 아닐 경우 얼리어답터의 최소 수를 담고 있다. DP[node][0] = 0 : node는 얼리어답터가 아니다 DP[node][1] = 1 : node는 얼리어답터 이다. 점화식 DP..

외판원 순환 문제( TSP: Traveling Salesperson Problem)이다. TSP는 하나의 시작점에서 모든 도시를 단 한번씩만 방문하여 원래 도시로 돌아오는 문제를 말한다. TSP를 해결하기 위한 방법은 두 가지가 존재한다. 1. 완전탐색 O(N!) 2. 다이나믹 프로그래밍 O(N^2 * 2^N) 만약 도시의 개수가 10개 이하라면 완전탐색도 사용이 가능하다. 하지만 일반적으로 다이나믹 프로그래밍을 사용한다. 그리고 방문한 도시를 구분하는 방법이 이전에 풀었던 문제와 다른데 비트 마스크를 사용한다. 만약 1, 2, 3, 4의 도시가 존재한다면, 1과 2 도시를 방문할 경우 1100과 같이 나타낸다. 비트 마스크로 나타내어 만약 방문한 도시가 동일하다면 비용도 동일하기 때문에 굳이 모두 직정..

주어진 대나무 숲에서 가장 오래 살 수 있는 기간을 구하는 문제이다. n*n 크기의 대나무 숲이 주어지고, 대나무가 더 많은 방향으로만 이동이 가능하다. 한 Cell당 하루를 살 수 있고 최대한 살 수 있는 기간을 구하기 때문에 DFS를 사용해야 한다는 것을 알 수 있다. 그리고 매 지점마다의 최대 값을 구하는 것 보다 이미 지나간 지점의 값을 저장해 놓는 것이 효율적이기 때문에 DP를 활용한다. 소스 코드 from sys import stdin, setrecursionlimit setrecursionlimit(10 ** 6) readline = stdin.readline N = int(readline()) dp = [[0] * N for _ in range(N)] _map = [[0] * N for _..

45656과 같이 모든 자릿수가 1씩 차이나는 수를 계단 수라 정의하고, 주어진 N자리 수의 총 계단의 수를 파악하는 문제이다. N의 수는 N-1의 1의 자리 수 +- 1을 1의 자리 수에 추가하는 규칙을 가지고 있다는 것을 발견하고 나열 하면 아래와 같이 나타난다. N=1 1, 2, 3, 4, 5, 6, 7, 8, 9 N=2 10, 21, 32, 43, 54, 65, 76, 87, 98 12, 23, 34, 45, 56, 67, 78, 89 .... 위와 같이 나열하다 보니 아래와 같은 점화식을 도출해 낼 수 있었다. N = 짝수 2 * D[i-1] - (i-1) N = 홀수 2 * (D[i-1] - (i-2)) 하지만 적절한 점화식이 아니었고 다른 분의 풀이를 참고하였다. 1의 자리수 N 0 1 2 ..