복습용 블로그

C++의 STL에는 vector와 queue 등 아주 좋은 친구들이 많다. 그 중 PS 에서 많이 쓰는 vector와 priority_queue 의 정렬 기능에 대해 정리하고자 한다. 1. vector algorithm STL 을 이용해 sort 함수로 vector를 쉽게 정렬할 수 있다. (단순 배열도 가능) sort(vec.begin(), vec.end()) 가 기본 사용법이며, vec의 처음부터 끝까지를 기본적으로 오름차순으로 정렬한다. 역순 정렬을 하고자 하면 sort(vec.rbegin(), vec.rend()) 와 같이 사용 가능하다. 하지만 이는 int, float, pair 등 기본 타입에만 적용이 된다. 따라서 operator 가 정의되지 않은 데이터 타입 (struct 로 직접 만든 데..

MST (Minimum Spanning Tree, 최소 신장 트리) 는 그래프에서 전체 가중치 합이 최소가 되도록 만든 트리입니다. MST를 구하는 방식으로는 크루스칼 알고리즘, 프림 알고리즘이 있습니다. 크루스칼 알고리즘은 모든 edge를 정렬 후, 가중치 순으로 하나씩 이어보며, 사이클이 발생하면 다음 엣지를 대상으로 검사하는 방식입니다. 그러므로 복잡도는 정렬 시 사용되는 O(E log E) 입니다. 프림 알고리즘은 아무 노드를 시작점으로 해당 노드로부터 가장 가까운 노드를 이어나가는 것을 반복합니다. 이 때, 선택된 다음 노드와 연결된 노드와 시작점 노드 간의 거리를 업데이트하며, 다음 가까운 노드 선택 시 해당 거리를 기준으로 선택합니다. 프림 알고리즘의 경우, 가장 가까운 노드를 찾는다의 기준..

유니온 파인드 알고리즘은 무향 그래프에서 disjoint set을 union 하는 과정입니다. (유향 그래프의 경우, SCC에서 사용하는 타잔, 코사라주 등 이용) 각 그래프 노드의 부모 노드를 찾고, find 하는 과정을 반복합니다. 이 때 부모 노드는 단순히 바로 연결된 노드가 아닌, 최상위로 찾을 수 있는 부모를 의미합니다. 따라서 사이클이 발생하는 경우는 두 노드의 부모 노드가 동일한 경우입니다. 예를 들어, 1-2 / 2-3 / 2-4/ 3-4 와 같은 연결이 주어진다면, 3-4의 입력 때 사이클이 발생합니다. (부모 기준 : 작은 값이 부모) 코드는 다음과 같습니다. #include using namespace std; int find_parent(int node, int parent[]) {..

벨만 포드 알고리즘은 음수인 가중치를 갖는 엣지가 있을 때 한 정점에서 모든 정점으로의 최단 거리를 구하는 알고리즘입니다. 다익스트라와의 차이는 음수 가중치 유무인데, 다익스트라 알고리즘을 동일하게 적용 시, 가장 짧은 거리를 갖는 노드 선택으로 인해 제대로 계산이 되지 않습니다. 따라서 음수 가중치가 존재하는 경우, 벨만 포드 알고리즘을 사용하면 되며, 전체 복잡도는 O(VE) 입니다. 벨만 포드 알고리즘은 모든 edge를 대상으로 노드 수만큼 지속적으로 업데이트를 합니다. 즉, dist[to] > dist[from] + arr[from][to] 인 경우 업데이트를 합니다. (dist : 시작 노드로부터 각 노드까지 거리) 단, 음수 사이클이 존재할 수도 있으므로, 이러한 경우를 판단해주어야 합니다. ..

플로이드 워셜 알고리즘은 그래프의 모든 정점에서 모든 정점으로의 최단 거리를 구하는 알고리즘입니다. 한 노드를 중간 지점으로 두고 나머지 노드 간의 거리를 해당 중간 노드를 거쳐갈 때 업데이트를 시킵니다. 점화식은 다음과 같습니다. D[a][b] = min(D[a][b], D[a][k], D[k][b]) a : start, b : finish, k : middle 주의할 점은 loop 3번을 돌 때 중간노드를 첫 번째 loop 로 잡아야 하는 점입니다. 아래와 같은 그래프에서 플로이드 워셜 알고리즘 코드는 다음과 같습니다. #include using namespace std; #define INF 987654321 void floyd_warshall(int graph[5][5], int nodeNum) ..