Heap 은 binary tree 형태로 값을 저장하되, 루트 노드에 max heap이면 최댓값이, min heap 이면 최솟값이 저장되는 자료구조를 말한다. 최댓값이나 최솟값을 구해야 하는 경우, heap이라는 자료구조를 사용하면 굉장히 편하게 구할 수 있다. 우선순위 큐는 기본 큐 구조와 달리 입력 순서가 아닌 우선순위 순서로 자료를 저장하는 자료구조를 말한다. 우선순위 큐 (Priority Queue)는 Heap을 사용하여 구현하는데 우선순위에 따른 오름차순 정렬은 Min Heap으로, 내림차순 정렬은 Max Heap으로 구현할 수 있다. 물론, java 에 Priority Queue 라이브러리가 있기 때문에 바로 사용할 수 있지만, 공부를 위해 라이브러리를 사용하지 않고 짜보았다. 먼저, Min ..
[알고리즘] Java로 구현하는 쉬운 Merge Sort (병합 정렬, 합병 정렬)
알고리즘을 시작할 때 가장 먼저 배워야 할 것은 정렬, 즉 sorting이라고 생각한다. 버블 정렬, 선택 정렬, 퀵 정렬 등 많은 정렬이 있지만, 내가 사용하는 것은 병합 정렬이다. 병합 정렬(=합병 정렬)의 시간복잡도는 O(nlogn)인데, 왜 이 시간 복잡도가 나오는지 먼저 알아보자. 병합 정렬은, 원소가 저장되어 있는 배열을 계속 쪼개서 길이가 1인 배열을 만들고, 그 이후 정렬하면서 합치는 알고리즘이다. Merge sort 는 binary tree 형태로 쪼개기 때문에 가질 수 있는 최대 깊이는 log n 이 된다. 이때, 각 분할 (n개) 별로 합병을 진행하므로, 총 시간 복잡도는 O(nlogn)이 된다. 이때, quick sort는 최악의 경우 O(n^2)의 시간 복잡도를 가지게 되는데, m..