# 크루스칼 알고리즘(Kruskal Algorithm) 크루스칼 알고리즘은 최소 신장 트리 (Minimum Spanning Tree)를 만드는데 사용하는 알고리즘으로 그리디 알고리즘으로 분류된다. 비용이 작은 간선을 선택하며 서로소 집합 자료구조를 이용해 사이클이 발생하지 않도록 처리하는 방법이다. 이를 통해 불필요한 간선(사이클이 발생하는 간선)이 선택되지 않으면서도 간선 비용의 합이 가장 작은 신장 트리를 만들 수 있다. 모든 간선을 정렬하고 순회하기 때문에 간선의 수가 적은 그래프에서 활용하기에 적합하다. 간선의 수가 노드에 비해 훨씬 많다면 프림 알고리즘의 사용을 고려하자. 서로소 집합을 이용한 사이클 판별 서로소 집합을 통해 사이클인지 확인하는 방법은 간선 양쪽 노드의 find 연산 결과가 같은..
# 서로소 집합 (Disjoint sets) 서로소 집합이란 공통 원소가 없는 두 집합을 의미한다. 아래 그림의 왼쪽 두 집합은 서로소 관계이며, 오른쪽은 아니다. 서로소 집합은 여러 개의 서로소 관계로 이루어진 데이터를 처리하기 위한 자료구조로 사용되며 몇몇 그래프 알고리즘에서 주요하게 사용된다. 서로소 집합은 union / find 두 가지 연산으로 구현할 수 있으며, 이 때문에 union-find 자료구조로 불리기도 한다. Union 연산은 2개의 집합을 하나로 묶는 연산이며, find 연산은 특정 원소가 어느 집합에 속해있는지 찾는 연산이다. 서로소 관계인지 확인 시에는 find 연산의 결과가 다른지 확인하면 된다. # Process 모든 연결 관계에 대하여 union 연산을 이용해 서로 연결된 ..
순열과 조합... 중고등학교 때부터 학부까지 그렇게 많이 그 공식을 써왔는데... 이젠 공식조차 기억이 안난다. 그리고 순열과 조합의 각 케이스를 프로그래밍적으로 구하는 건 더더욱 해본적이 없다. 이번에 정리해두고 헷갈릴 때마다 꺼내 쓰자. 개념 순열 (Permutation) 서로 다른 n개 중 r개를 순서에 상관있게 선택하는 경우의 수이다. {1, 2, 3} 중 2개 원소를 선택한다고 하면, {1, 2}, {1, 3}, {2, 1}, {2, 3}, {3, 1}, {3, 2}의 6가지 경우가 나온다. 공식으로 경우의 수만 구하자면, 아래와 같다. 배열 (Combination) 서로 다른 n개 중 r개를 순서에 상관 없이 선택하는 경우의 수이다. {1, 2, 3}중 2개의 원소를 선택한다면, {1, 2},..
# 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 필요로 할 때 사용한다. 특정 시작점에서 다른 지점까지의 최단 경로를 탐색하는 다익스트라 알고리즘보다 넓은 범위를 탐색하는 만큼 시간 복잡도는 O(N3)으로 매우 느리지만 구현이 매우 간편하다. 따라서 모수가 작으며 여러 지점 사이 거리를 파악해야 하는 상황에서 사용할 만 하다. 플로이드 워셜 알고리즘은 두 노드 사이 다른 노드를 거쳐 갔을 때 더 작은 비용이 발생하는지 확인하는 작업을 반복 수행한다. Dynamic programming의 일종으로 볼 수 있으며 점화식으로 나타내면 다음과 같다. $$ D_{ab}=min(D_{ab}, D_{ak} + D_{k..
# 다익스트라 알고리즘 (Dijkstra's algorithm) 다익스트라 알고리즘은 한 노드에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘이다. 모든 간선의 값이 0 이상일 때, 즉 음의 간선이 없을 때에만 사용할 수 있는 알고리즘이다. 가장 비용이 적은 노드를 선택해 임의의 과정을 반복하기 때문에 그리디 알고리즘으로 분류된다. 다익스트라 알고리즘은 아래와 같은 순서로 진행된다. 출발 노드 선택 최단 거리 테이블을 초기화 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택 선택한 노드에서 다른 노드로 가는 비용 계산 및 테이블 업데이트 종료 조건까지 3, 4번 반복 3번에서 최단 거리가 가장 짧은 노드를 선택하는 방법에 따라 시간 복잡도가 달라진다. 최단 거리 테이블을 단순히 선형 탐색하는..
# Dynamic Programming (DP) Wikipedia의 설명을 인용하자면 일반적인 Dynamic Programming이란, 'it refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner.' 즉, 어떤 문제를 해결하고자 할 때 작은 단위의 문제를 재귀적으로 풀어내어 단순화시키는 것을 의미한다. 따라서 DP를 활용하기 위해서는 다음 조건이 필요하다. 1. 큰 문제를 작은 문제로 나눌 수 있어야 한다. (optimal substructure) 범위를 Computer Sicence로 한정시키자면 여기에 하나의 조건이 더 추가되게 된다. 2. 작은 문제의 답..
