나의 경험이 나를 구성한다

정렬 알고리즘은 일반적으로 비교 정렬을 하는데, 각 원소의 값을 비교하지 않고 정렬하여 시간복잡도를 O(N)으로 줄이는 특수한 정렬 알고리즘이 존재한다. 그 중 하나가 계수 정렬 (Counting Sort)이다. 추가로 정렬을 하기 위해서 각 원소의 값을 최소 1번씩은 확인해야 하므로 정렬 알고리즘이 O(N)보다 시간 복잡도는 낮아질 수 없다는 것은 자명하다.  Counting Sort는 정렬하고자 하는 값의 범위가 O(N)을 넘지 않는 경우 사용할 수 있다. 예를 들어 k 이하의 자연수가 될 수 있고, 실수라고 한다면 수의 범위가 무한해지기 때문에 사용할 수 없다. Counting Sort의 동작 원리는 말 그대로 값을 세서 개수를 기록해둔 뒤 나중에 순서대로 데이터를 배치하는 것이다. 도식을 통해 이..

알고리즘 2024. 9. 7. 16:23

24.03.20 수정 - 처음에 데이터 전체를 힙 구조로 만드는 과정이 O(NlogN)이라고 상한을 과하게 잡아서 작성했는데, 실제로는 Θ(N)의 시간 안에 해결된다. 증명과정을 추가하여 작성했다. 힙 정렬은 힙(Heap)이라는 자료구조를 이용해 정렬하는 방식이므로 우선 힙에 대해 이해할 필요가 있다. 다음은 Heap의 조건이다. Heap이란? 1. 완전 이진 트리이다. 모든 경로의 가장 아래층을 제외하고는 모두 채워져있다. 2. 왼쪽부터 노드가 채워진다. 3. 부모 노드의 값이 자식 노드의 값보다 항상 작다(크다). Heap은 3번 조건에 따라 MaxHeap와 MinHeap으로 나뉜다. 부모 노드의 값이 자식 노드의 값보다 작으면 MinHeap, 크면 MaxHeap이다. 보통 MaxHeap을 사용하는 ..

알고리즘 2024. 3. 17. 11:09

평균적인 상황에서 높은 성능을 발휘하는 퀵 정렬이다. C++ STL 자료구조의 정렬에서 사용되는 것으로 알고 있다. 퀵 정렬은 최악의 상황 (후술)에서는 O(N^2)까지 시간 복잡도가 증가할 수도 있지만 대부분의 상황에서는 O(NlogN) 안에서 해결된다. O(NlogN)이라는 것은 MergeSort와 비슷한 구조의 알고리즘이라는 것이고, 실제로 동작 방식에 차이는 있지만 더 작은 문제로 쪼개서 해결한다는 점은 동일하다. MergeSort와의 큰 차이점에는 1. 문제가 쪼개지는 균형이 보장되지 않는다, 2. MergeSort는 작은 문제를 해결한 뒤 합치는 방식 (bottom-up)이라면 QuickSort는 큰 문제부터 해결하면서 정렬되는 방식 (top-down)이다. 가 있다. 퀵 정렬 (Quick S..

알고리즘 2024. 3. 17. 08:08

병합 정렬은 문제를 더 작은 문제로 쪼개서 재귀적으로 풀이한다. 대표적인 O(NlogN) 정렬 알고리즘이다. 병합 정렬 (Merge Sort) 소개 기본적인 아이디어는 데이터를 절반으로 나눠서 전반부와 후반부를 각각 정렬해서 합치는 방식을 재귀적으로 반복하는 방식이다. 그래서 재귀호출하는 MergeSort 부분과 정렬된 두 데이터를 합치는 Merge 부분으로 나뉜다. 최종적으로 원소가 1개 남게 될 때 까지 계속 문제를 쪼갠 뒤, Merge(병합) 과정에서 순서에 맞게 데이터를 정렬하면서 두 데이터 그룹을 합치는 과정이 반복된다. 예를 들어 위 그림에서 1과 3으로 나뉘어졌다면 [1,3]으로 합쳐지고, 5와 2로 나뉘어졌다면 [2,5]로 합쳐진다. [1,3]과 [2,5]를 또 합치게 된다면 각각의 데이터..

알고리즘 2024. 3. 17. 06:29

삽입 정렬 역시 Θ(N^2) 의 시간 복잡도를 지닌 정렬 알고리즘이다. 사실 정렬 알고리즘은 어디서부터 정렬할지 정하기 나름이지만 필자는 삽입 정렬을 왼쪽부터 정렬된 상태를 늘려나간다고 공부했다. 개념적으로 왼쪽부터 정렬된 공간을 1씩 늘려나간다고 생각할 수 있다. 삽입 정렬 (Insertion Sort) 소개 삽입 정렬은 왼쪽부터 정렬된 공간을 1씩 순차적으로 늘려나가면서 정렬하는 과정이다. 차례대로 원소를 보면서 왼쪽의 정렬된 공간의 알맞은 자리에 삽입하면서 정렬된다는 의미에서 삽입 정렬이라는 이름이 붙게 되었다. 글로만 설명하려니까 어려우므로 그림을 보면서 이해하면 될 것 같다. 그림에서는 알맞은 자리로 한 번에 이동하는 것처럼 표시했지만 사실은 현재 삽입하려는 원소를 바로 아래의 인덱스부터 차례대..

알고리즘 2024. 3. 17. 04:16

버블 정렬은 O(N^2) 시간 복잡도의 효율이 좋지 않은 정렬 알고리즘 중 하나이다. 아이디어가 간단하면서도 처음 접했을 때 나름 신선하기 때문에 정렬을 처음 배울 때 많이 배우게 되는 것으로 알고 있다. 그리고 버블 정렬의 경우 어떤 처리를 하면 조금이나마 알고리즘 효율을 개선할 수 있고, 정렬되어 있는 데이터를 처리하는 데 걸리는 시간 복잡도를 O(N)으로 낮출 수 있다. 선택 정렬보단 비교적 효율적으로 개선할 수 있는 정렬 알고리즘이다. 버블 정렬 (Bubble Sort) 개념 소개 버블 정렬은 두 인접한 데이터를 순차적으로 비교하면서 부분적으로 정렬하는 방식이다. 데이터 전체에 대해 한 번 순차적으로 정렬을 마치고 나면 최댓값이 가장 마지막으로 정렬된다. 위 그림과 같이 2개씩 차례대로 비교하면서..

알고리즘 2024. 3. 17. 03:17

선택 정렬(Selection Sort)은 알고리즘 효율이 낮은 정렬 알고리즘 중 하나이다. 선택 정렬에서 "선택"이라는 것은 여러 개의 데이터 중 특정 순서에 있는 데이터를 구하는 동작이다. 예컨대 최댓값, 최솟값 또는 i 번째로 큰 데이터 등을 얻는 것이 "선택"이다. 그래서 선택 정렬은 데이터 중 최댓값을 계속 한 쪽으로 몰아넣으면서 정렬하는 방식이다. 선택 정렬 (Selection Sort) 개념 소개 처음부터 차례대로 비교하며 데이터 전체 중 최댓값을 찾는다. 최댓값과 가장 마지막에 위치한 값을 swap 한다. 가장 마지막을 제외한 데이터에 대해 1, 2번을 반복한다. 선택 정렬은 아이디어 자체는 간단하지만 어떠한 경우에서도 Θ(N^2)의 효율을 보인다.선택 정렬 알고리즘은 처음부터 차례대로 비교..

알고리즘 2024. 3. 17. 02:52

문제 : [start, end] 형태의 여러 개의 interval이 주어졌을 때, 그 interval 들의 합집합을 계산하라. 아이디어 1. 주어진 순서대로 자신 이후의 interval들과 비교하여 (정확히는 자신의 end와 비교대상의 start, end가 더 크면 겹치는 부분 존재) 합집합을 계산. 예상 시간복잡도 : (n-1)+(n-2)+...+1 = n(n-1)/2, O(n^2) 아이디어 2. 주어진 interval들을 start에 대해 정렬한다. 이후 위 아이디어처럼 하나씩 비교하다가 겹치지 않는 interval (K)이 발견되는 K 이후 interval들의 start가 최소 K의 start보다 크므로 더 이상 비교할 필요 없어지고, K 이하의 interval 들은 건너뛰고 비교 기준을 바로 K로..

알고리즘 2024. 3. 7. 12:30