[그래프] 최소 신장 트리(Minimum Spanning Tree)
2024. 5. 5. 14:22
프로그래밍/알고리즘
최소 신장 트리란?신장 트리(스패닝 트리)란 그래프 내의 모든 정점을 포함하는 트리를 의미한다.트리이므로 간선의 수는 (정점의 수 - 1)이며, 사이클은 존재하지 않는다. 신장 트리 중 가중치의 합이 최소인 트리를 최소 신장 트리라고 한다. 최소 신장 트리 구하기크루스칼 알고리즘(Kruskal's Algorithm)크루스칼 알고리즘은 가중치가 가장 작은 간선부터 확인하며 사이클이 생기지 않는 경우 MST에 포함하는 그리디(Greedy)적인 방법이다. 먼저 그래프 내의 모든 간선을 가중치에 대한 오름차순으로 정렬한다.이후 반복문을 돌며 가중치가 작은 가중치부터 MST에 포함 가능한지 여부를 판별하는데, 서로소 집합을 이용하는 방법이 가장 대중적이다.($A$와 $B$가 이미 같은 집합에 있다면, 이미 해당 ..
[DP] 최장 공통 부분 수열(LCS; Longest Common Subsequence)
2024. 4. 27. 18:56
프로그래밍/알고리즘
최장 공통 부분 수열이란?최장 공통 부분 수열이란 두 수열이 주어졌을 때, 둘 모두의 부분 수열이 되는 수열 중 가장 긴 것을 의미한다. 예를 들어,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[..
[그래프] 이분 그래프(Bipartite Graph)와 이분 매칭(Bipartite Matching) with 쾨닉의 정리(Kőnig’s theorem)
2024. 4. 24. 15:36
프로그래밍/알고리즘
이분 그래프란?이분 그래프란 그래프의 모든 정점을 두 그룹으로 나누어 같은 그룹끼리 이어지는 간선이 없도록 만들 수 있는 그래프를 의미한다.이렇게 되면 이분 그래프의 모든 간선은 서로 다른 그룹의 정점을 연결하게 된다. 이분 그래프 판별어떤 그래프가 이분 그래프인지 아닌지는 DFS나 BFS를 이용해 판별할 수 있다. 특정 정점 하나를 잡아 A그룹으로 둔다.해당 정점과 이어진 정점들은 B그룹으로 둔다.마찬가지로 B그룹 정점과 이어진 정점들은 다시 A그룹으로 둔다.진행 중 모순이 발생했다면 해당 그래프는 이분 그래프가 아니다. 아래 문제를 한 번 풀어보자.더보기import sysfrom collections import dequeinput = sys.stdin.readlinek = int(input())f..
[그래프] 최단 경로 탐색 알고리즘 총정리(다익스트라, 벨만-포드, 플로이드-워셜, 0-1 BFS)
2024. 4. 21. 15:49
프로그래밍/알고리즘
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..
투 포인터(Two Pointers) (Python)
2024. 4. 18. 14:32
프로그래밍/알고리즘
투 포인터 알고리즘이란? 투 포인터 알고리즘이란 일차원 배열에서 말 그대로 2개의 포인터를 이동시키며 원하는 값을 찾아내는 알고리즘을 의미한다. 참고로 두 포인터간의 간격이 항상 동일한 경우 슬라이딩 윈도우 알고리즘과 동일해진다. 어떻게 구현할까? 두 포인터의 위치를 저장할 변수를 만든다. (주로 left, right와 같은 단어를 사용한다.) 두 포인터의 초기 위치와 탐색 조건을 지정한다. 초기 위치는 left = right = 0으로 지정하거나 left = 0, right = n - 1로 지정하는 경우가 많다. 탐색 조건은 left