개요 본문에서는 파이썬의 sort() 및 sorted() 함수에 적용된 TimSort 알고리즘에 대해 설명하고자 합니다. TimSort는 삽입 정렬(Insertion Sort)과 병합 정렬(Merge Sort)의 특성을 결합하여 구현된 고도로 효율적인 정렬 알고리즘입니다. 이 글에서는 TimSort의 작동 원리와 그 구성 방식에 대해 간략히 소개하겠습니다. Binary insertion sort 특징 안정 정렬 비교 횟수가 Insertion sort에 비해 적음 Insertion sort 는 비교하는 연산에 최대 O(N^2) 시간이 소요됩니다. 반면 Binary insertion sort는 이러한 비교 연산 O(NlogN) 으로 줄일 수 있는데 어떻게 줄일 수 있는지 insertion sort의 특징과 ..
알고리즘/이론
개요 Union-Find 는 그래프 G가 주어졌을때 상호 배타적 집합(Disjoint-Set)을 표현할때 사용되는 그래프 알고리즘입니다. 임의의 두 노드가 서로 같은 그래프에 속하는지 판별하기 위해 사용됩니다. 연산 Union (합치기): 두 원소가 속한 집합을 하나로 합침 Find (찾기): 해당 원소가 속한 집합을 반환 Find 본인이 속한 집합을 찾기 위한 연산으로 기본 방법과 경로 최적화 방법이 존재합니다. 기본 방법: 최악의 경우 시간복잡도 O(N) int find_parent(int x) { if(x == parent[x]) return x; else return find_parent(parent[x]); } 경로 최적화: 시간복잡도 O(1) int find_parent(int x) { if(..
