전체 글

위상 정렬이란?위상 정렬이란 방향 비순환 그래프의 각 노드를 순서대로 배열하는 것을 의미한다. 가장 대표적인 예시로는 "순서가 정해져 있는 작업들을 정렬하는 것"이 있다.$A$ 다음 $B$를 해야 하고, $B$ 다음 $C$를 해야 한다면, $A$-$B$-$C$ 순으로 정렬하는 것이다. 위상 정렬 구현하기(Kahn 알고리즘)Kahn 알고리즘은 위상 정렬의 대표적인 알고리즘이다.진입 차수라는 개념을 사용하는데, 이는 말 그대로 한 정점 $A$에 대해 $A$로 향하는 간선의 수를 의미한다. Kahn 알고리즘은진입 차수가 0인 노드를 큐에 집어넣는다.큐에서 노드를 하나씩 뽑으며 연결된 노드들의 진입 차수를 1 줄인다.큐가 빌 때까지 진행한다.모든 정점을 방문하기 전에 큐가 빈다면 해당 그래프에는 사이클이 존재해..

최소 신장 트리란?신장 트리(스패닝 트리)란 그래프 내의 모든 정점을 포함하는 트리를 의미한다.트리이므로 간선의 수는 (정점의 수 - 1)이며, 사이클은 존재하지 않는다. 신장 트리 중 가중치의 합이 최소인 트리를 최소 신장 트리라고 한다. 최소 신장 트리 구하기크루스칼 알고리즘(Kruskal's Algorithm)크루스칼 알고리즘은 가중치가 가장 작은 간선부터 확인하며 사이클이 생기지 않는 경우 MST에 포함하는 그리디(Greedy)적인 방법이다. 먼저 그래프 내의 모든 간선을 가중치에 대한 오름차순으로 정렬한다.이후 반복문을 돌며 가중치가 작은 가중치부터 MST에 포함 가능한지 여부를 판별하는데, 서로소 집합을 이용하는 방법이 가장 대중적이다.($A$와 $B$가 이미 같은 집합에 있다면, 이미 해당 ..

최장 공통 부분 수열이란?최장 공통 부분 수열이란 두 수열이 주어졌을 때, 둘 모두의 부분 수열이 되는 수열 중 가장 긴 것을 의미한다. 예를 들어,MANGOJUICEAGODATRIP위 두 문자열의 LCS는 AGOI이다. LCS 길이 구하기LCS는 DP를 이용해 구할 수 있다.두 수열 $a_n, b_n$이 있을 때, $a_n$의 $i$번째 원소와 $b_n$의 $j$번째 원소까지 봤을 때의 최장 공통 부분 수열의 길이를 $dp[i][j]$라고 하자. 아래와 같은 점화식을 세울 수 있다.$i = 0$ 또는 $j = 0$일 때, $dp[i][j] = 0$$a_i = b_j$일 때, $dp[i][j] = dp[i - 1][j - 1] + 1$$a_i \neq b_j$일 때, $dp[i][j] = MAX(dp[..

이분 그래프란?이분 그래프란 그래프의 모든 정점을 두 그룹으로 나누어 같은 그룹끼리 이어지는 간선이 없도록 만들 수 있는 그래프를 의미한다.이렇게 되면 이분 그래프의 모든 간선은 서로 다른 그룹의 정점을 연결하게 된다.  이분 그래프 판별어떤 그래프가 이분 그래프인지 아닌지는 DFS나 BFS를 이용해 판별할 수 있다. 특정 정점 하나를 잡아 A그룹으로 둔다.해당 정점과 이어진 정점들은 B그룹으로 둔다.마찬가지로 B그룹 정점과 이어진 정점들은 다시 A그룹으로 둔다.진행 중 모순이 발생했다면 해당 그래프는 이분 그래프가 아니다. 아래 문제를 한 번 풀어보자.더보기import sysfrom collections import dequeinput = sys.stdin.readlinek = int(input())f..

BFS를 이용한 완전 탐색 조건: 모든 간선의 가중치가 동일할 때 결과: 한 정점에서 다른 모든 정점까지의 거리 구현 방법 / 시간복잡도: 큐 / $O(V+E)$ 간선에 가중치가 없거나 모두 동일한 경우 단순 탐색으로 $O(V+E)$만에 최단 경로를 찾을 수 있다. 더보기 from collections import deque distances = [None] * V queue = deque([0]) distances[0] = 0 while queue: target = queue.popleft() for next_target in graph[target]: if distances[next_target] == None: queue.append(next_target) distances[next_targe..