분할정복
분할 정복은 문제를 부분문제로 나누어 문제를 해결할 수 있는단위까지 나눈 후, 해결하고 다시 조합하는 방법이다.
분할정복은 세단계로 구성되어있다.
분할: 문제를 분할할 수 있을 만큼 같은 유형의 문제로 분할한다.
정복: 분할된 작은 문제를 해결한다.
조합: 해결된 작은 부분문제들을 조합하여 정답을 출력한다.
※ 분할정복과 동적 계획법 차이:
분할정복은 큰 문제를 여러개의 작은 문제로 나누어 해결하고, 이를 모두 조합한다.
동적계획법은 작은 문제부터 해결하여 기록하고, 기록된 정보를 통해 큰문제를 해결해나간다.
분할정복은 대표적으로 합병정렬과 퀵 정렬이 있다.
합병정렬
분할정복의 대표적인 정렬 알고리즘이다.
합병정렬의 단계
1. 주어진 배열의 크기가 0또는 1이라면 이미 정렬이 되있다고 간주하고, 그렇지 않다면 2개의 부분배열로 나눈다.
2. 부분배열의 크기가 정렬할 수 있을만큼 작지않다면 1번을 재호출한다.
3. 나눠진 부분배열을 합친다. 이때 순서에 맞춰서 정렬한다.
4. 부분배열을 조합하여 결과를 출력한다.
합병정렬의 특징:
- 합병정렬의 조합단계에서 따로 저장해둘 배열로부터 값을 가져오므로 입력과 같은 공간의 임시배열이 필요하다.
- 재귀호출로 인해 오버헤드가 발생할 수 있다.
- 연결리스트를 정렬할때는 다른 정렬방법보다 더 효율적이다.
Swift 코드로 구현
// 합병 정렬
func mergeSort(arr: inout [Int], p: Int, q: Int) -> [Int] {
// 따로 저장해둘 공간(입력된배열의 크기만큼)
var result = Array(repeating: 0, count: arr.count)
// 배열의 크기가 1 또는 0이 될때까지 최대로 나누어준다.
if p < q {
// 배열의 중간인덱스
var k = (p + q) / 2
// 배열을 둘로 나누었을때, 왼쪽배열과 오른쪽배열
var leftArr = mergeSort(arr: &arr, p: p, q: k)
var rightArr = mergeSort(arr: &arr, p: k+1, q: q)
// 배열이 최대로 나누어졌을때 아래 행동이 시작된다.
// 분할된 배열들을 정렬하며 합친다.
var i = p
var j = k+1
var d = p
// 왼쪽배열과 오른쪽배열중 한 배열이 모두 정렬이 완료될때까지
while i <= k && j <= q {
// 왼쪽배열 원소가 더크면 오른쪽배열 원소를 넣고, 오른쪽배열 원소가 더 크면 왼쪽배열 원소를 넣는다.
if leftArr[i] < rightArr[j] {
result[d] = leftArr[i]
i += 1
} else {
result[d] = rightArr[j]
j += 1
}
d += 1
}
// 한쪽의 배열이 모두 정렬되었을때, 다른 한쪽은 원소가 남아있기때문에 그대로 붙여준다.
// 남아있는 원소는 이미 이전에 정렬되어있는 원소기때문에 그대로 붙여도 좋다.
if i > k {
for index in j...q {
result[d] = rightArr[index]
d += 1
}
} else if j > q {
for index in i...k {
result[d] = leftArr[index]
d += 1
}
}
// 정렬된 원소를 배열에 넣고 리턴
for i in p...q {
arr[i] = result[i]
}
}
return arr
}
입력 & 결과:
var A = [37, 10, 22, 30, 35, 13, 25, 24]
print(mergeSort(arr: &A, p: 0, q: A.count-1))
// [10, 13, 22, 24, 25, 30, 35, 37]
위 코드 재귀호출의 흐름은 다음과 같다.
1. 왼쪽배열을 분할
2. [37, 10] 정렬 후 결합
3. [22,30] 정렬 후 결합
4. 두 배열을 정렬 후 결합
5. 왼쪽배열: [10,22,30,37]
6. 오른쪽배열을 분할
7. [35,13] 정렬 후 결합
8. [25,24] 정렬 후 결합
9 두 배열을 정렬 후 결합
10. 오른쪽 배열: [13, 24, 25, 35]
11. 왼쪽배열과 오른쪽배열을 정렬 후 결합하여 리턴
| 이름 | 최선 | 평균 | 최악 | 메모리 |
| 합병정렬 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) |
퀵정렬
퀵정렬은 임의의 수 하나를 골라, 그 수보다 작으면 왼쪽에, 크다면 오른쪽에 정렬하는 방법이다.
퀵정렬 과정
정복: 임의의수 n을 기준으로 n보다 작은수는 왼쪽배열, n보다 큰수는 오른쪽배열에 배치
분할: 배치된 배열에서 왼쪽배열과 오른쪽배열 재귀호출
퀵정렬은 정복을 먼저하고 분할하여 재귀호출을 한다.
세부과정
1. 기준이되는 원소를 선택
2. 기준원소의 인덱스를 저장하고, 나머지 원소를 검사하며 기준원소보다 작다면 인덱스+1 후 원소와 저장된인덱스와 자리바꿈
3. 모든 원소 검사 후 기준원소와 인덱스와 자리바꿈
(여기까지 완료된다면 배열은 기준원소를 기준으로 왼쪽에는 작은값, 오른쪽엔 큰값 배치됨) (정복)
4. 기준원소를 제외한 왼쪽배열과 오른쪽배열을 재귀호출한다.(분할)
5. 1-4를 반복하여 결과 도출
코드로 구현하면 다음과 같다.
// 퀵 정렬
func quickSort(arr: inout [Int], left: Int, right: Int) -> [Int] {
// 배열의 크기가 2 이상이면 정복, 아니면 그냥 출력
if left < right {
// 기준점 선택(가장왼쪽)
var pivot = arr[left]
// 기준점이 위치할 곳을 저장
var j = left
// 기준점을 제외한 배열의 원소들을 검사
for i in left+1...right {
// 원소가 기준점보다 작다면 j위치에 있는 원소와 바꿈
// 원소가 기준점보다 크다면 패스
// 이렇게 반복하면 j위치보다 이전에 위치한 원소들은 기준점보다 작은 원소들이다.
if arr[i] < pivot {
j += 1
arr.swapAt(i, j)
}
}
// 기준점과 j위치와 원소 바꾸기
// 기준점은 중간에 위치하게되고, 기준점 왼쪽은 기준점보다 작은원소, 오른쪽은 기준점보다 큰원소가 배치됨
arr.swapAt(j, left)
// 분할
// 왼쪽배열로 재귀호출
// 오른쪽배열로 재귀호출
quickSort(arr: &arr, left: left, right: j-1)
quickSort(arr: &arr, left: j+1, right: right)
}
return arr
}입력 및 결과:
var A = [25, 10, 22, 30, 35, 13, 37, 24]
print(quickSort(arr: &A, left: 0, right: A.count-1))
// [10, 13, 22, 24, 25, 30, 35, 37]
위 코드 재귀호출의 흐름은 다음과 같다.
1. 기준점:25 를 기준으로 [작은값, 25, 큰값] 배치
2. [작은값], [큰값] 재귀호출
3. 1-2 반복(기준점을 제외한 원소가 없을때까지)
| 이름 | 최선 | 평균 | 최악 | 메모리 |
| 퀵정렬 | O(nlogn) | O(nlogn) | O(n^2) | O(nlogn) |
퀵정렬의 최악의경우는 이미 정렬된 데이터를 정렬할 경우이다.
'코딩테스트 > 알고리즘' 카테고리의 다른 글
| 플로이드-워셜 알고리즘 Swift (0) | 2024.04.25 |
|---|---|
| 다익스트라 알고리즘 Swift (0) | 2024.04.24 |
| 투포인터 알고리즘 Swift (0) | 2024.04.14 |
| 순열과 조합 Swift (0) | 2024.04.10 |
| 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) Swift (1) | 2024.04.08 |
