[CS 면접 질문] 알고리즘
병합 정렬 (Merge Sort)
병합 정렬은 정렬하고자 하는 배열을 절반씩 분할하여 이를 다시 합하면서 정렬하는 방법이다. 더이상 나누어지지 않을 때 까지 분할하다가 원소가 하나인 배열일 때 자기 자신, 즉 원소 하나를 반환한다. 이 때 반환한 값끼리 combine될 때 비교가 이뤄지며, 비교 결과를 기반으로 정렬되어 임시 배열에 저장된다. 실제 정렬은 나눈 것을 병합하는 과정에서 이뤄지는 것이다.
| 시간복잡도 | 공간복잡도 |
|---|---|
| O(nlogn) | O(n) |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
void mergeSort(int[] arr) {
int[] helper = new int[arr.length];
mergeSort(arr, helper, 0, arr.length-1);
}
void mergeSort(int[] arr, int[] helper, int low, int high) {
if (low < high) {
int middle = (low+high)/2;
mergeSort(arr, helper, low, middle); // 왼쪽 절반 정렬
mergesort(arr, helper, middle+1, high); // 오른쪽 절반 정렬
merge(arr, helper, low, middle, high); // 병합
}
}
void merge(int[] arr, int[] helper, int low, int middle, int high) {
/* 절반짜리 두 배열을 helper 배열에 복사 */
for (int i=low; i<=high; i++) {
helper[i] = arr[i];
}
int helperLeft = low;
int helperRight = middle+1;
int current = low;
/* helper 배열 순회. 왼쪽 절반과 오른쪽 절반을 비교해 작은 원소를 원래 배열에 복사 */
while (helperLeft <= middle && helperRight <= high) {
if (helper[helperLeft] <= helper[helperRight]) {
arr[current] = helper[helperLeft];
helperLeft++;
} else {
arr[current] = helper[helperRight];
helperRight++;
}
current++;
}
/* 왼쪽 절반에 남은 원소를 원래 배열에 복사 */
for (int i=helperLeft; i<=middle-helperLeft; i++) {
arr[current++] = helper[i];
}
}
퀵 정렬 (Quick Sort)
퀵 정렬은 무작위로 선정된 한 원소인 피봇(pivot)을 사용해 배열을 분할하는데, 피봇보다 작은 원소들은 앞에, 큰 원소들을 뒤로 보낸다. 배열과 그 부분 배열을 반복적으로 분할해 나가면 결국 배열은 정렬된 상태에 도달한다. 하지만 피봇이 중간값(median)에 가깝다는 보장이 없기 때문에, 최악의 경우(피봇이 배열의 최솟값 또는 최댓값일 때) 수행 시간이 O(n^2)이 될 수 있다.
| 시간복잡도 | 공간복잡도 |
|---|---|
| O(nlogn) | O(logn) |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void quickSort(int[] arr, int left, int right) {
int index = partition(arr, left, right);
if (left < index-1) { // 왼쪽 절반 정렬
quickSort(arr, left, index-1);
}
if (index < right) { // 오른쪽 절반 정렬
quickSort(arr, index, right);
}
}
int partition(int[] arr, int left, int right) {
int pivot = arr[(left+right)/2]; // 분할 기준 원소
while (left <= right) {
// 왼쪽에서 오른쪽으로 옮겨야 하는 원소 탐색
while (arr[left] < pivot) left++;
// 오른쪽에서 왼쪽으로 옮겨야 하는 원소 탐색
while (pivot < arr[right]) right--;
// 원소를 swap하고 left와 right 이동
if (left <= right) {
swap(arr, left, right);
left++;
right--;
}
}
return left;
}
정렬 알고리즘 시간, 공간 복잡도 비교
| 알고리즘 | 공간복잡도 | 시간복잡도 (avg) | 시간복잡도 (worst) |
|---|---|---|---|
| 버블 정렬 (Bubble Sort) | O(1) | O(n^2) | O(n^2) |
| 선택 정렬 (Selection Sort) | O(1) | O(n^2) | O(n^2) |
| 삽입 정렬 (Insertion Sort) | O(1) | O(n^2) | O(n^2) |
| 병합 정렬 (Merge Sort) | O(n) | O(nlogn) | O(nlogn) |
| 퀵 정렬 (Quick Sort) | O(1) | O(nlogn) | O(n^2) |
| 힙 정렬 (Heap Sort) | O(1) | O(nlogn) | O(nlogn) |
| 계수 정렬 (Counting Sort) | O(n) | O(n) | O(n) |
| 기수 정렬 (Radix Sort) | O(n) | O(n) | O(n) |
이분 탐색 (Binary Search)
정렬된 배열 안에서 특정 원소를 찾을 때 탐색 범위를 절반씩 줄여나가는 방식의 알고리즘으로, 선형탐색에 비해 빠른 속도를 보장한다. O(logN)의 시간복잡도를 갖는다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int binarySearch(int[] arr, int key) {
int start = 0;
int end = arr.length - 1;
int mid = 0;
while (start <= end) {
mid = (start + end) / 2;
if (arr[mid] == key) {
return mid;
} else if (arr[mid] < key) {
start = mid + 1;
} else if (arr[mid] > key) {
end = mid - 1;
}
}
return -1;
}
동적 계획법 (Dynamic Programming)
동적 계획법이란 주어진 문제를 풀기 위해 문제를 여러 개의 하위 문제(sub-problem)로 나누어 푸는 방법이다. 작은 문제들 속에서 ‘계속 반복되는 연산’을 활용하여 빠르게 풀 수 있는 것이 핵심이다.
동적 계획법의 조건
- 작은(하위) 문제에서 반복이 일어난다.
- 같은 문제는 항상 정답이 같다.
이 두 가지 조건이 충족한다면 동적 계획법을 이용하여 문제를 풀 수 있다.
같은 문제가 항상 정답이 같고, 반복적으로 일어난다는 점을 활용해 메모이제이션(Memoization)1으로 큰 문제를 해결해나가는 것이다.
구현 방식
- Top-down : 큰 문제를 풀다가 풀리지 않은 작은 문제가 있다면 그때 해결하는 방법 (재귀 방식)
- Bottom-up : 작은 문제부터 차근차근 구하는 방법
참고 자료
Interview_Question_for_Beginner
tech-interview-for-developer
Notes
메모이제이션(Memoization): 한 번 계산한 문제는 다시 계산하지 않도록 저장해두고 활용하는 방식 ↩︎