상후니의 개발 블로그

* 정렬 알고리즘 ( Sort Algorithm ) 정렬 알고리즘은 굉장히 다양하고 상황 마다 효율적인 알고리즘이 다를 수 있다. 우선 간단한 것부터 개념 정리를 할 것이고 정렬에 관한 내용을 갱신해가며 업데이트 할 예정이다. ( 아래에 구현된 코드는 검증되지 않은 코드이다. ) 알고리즘을 만족하지 못하는 케이스가 있을 수 있다. *선택 정렬 ( Selection Sort ) / O( N2 ) => 처음부터 끝까지 탐색 후 데이터를 첫 순서 놓기 -> 2번째 idx 부터 끝까지 찾고 옮기기... { 1, 5, 10, 7, 2 } { 1, 5, 10, 7, 2 } { 1, 2, 10, 7, 5 } { 1, 2, 5, 7, 10 } { 1, 2, 5, 7, 10 } void SelectSort(std::ve..

*상호 배타적 집합 (Disjoint Set) => 유니온-파인드 Union-Find (합치기-찾기) => 서로 다른 원소들이 같은 집합에 속해있는지, 속해있지 않은지 판별 가능. => 대표적으로 크루스칼 알고리즘 MST 를 찾는데 활용. ( 싸이클 방지 ) int Find(int u) { if (u == _parent[u]) return u; return Find(_parent[u]); } void Union(int u, int v) { u = Find(u); v = Find(v); if (u == v) return; _parent[u] = v; } *문제점 1. Find 함수는 Union 연산 시, 덧붙여지는 각 원소들이 새로운 parent 를 가리키도록 갱신해야하기 때문에 O(n) 시간 복잡도를 가..