분할 정복 알고리즘의 기본 개념
분할 정복의 핵심 아이디어는 분할 정복 이름 그대로 '분할(Divide)', '정복(Conquer)', '결합(Combine)' 의 세 단계로 이루어져 있다.
- 분할 : 큰 문제를 여러 개의 작은 문제로 나눈다.
- 정복 : 나눈 작은 문제들을 각각 해결한다.
- 결합 : 해결한 결과를 합쳐서 전체 문제의 답을 만든다.
쉽게 설명하면 큰 케이크를 한 번에 먹으려 하면 힘들지만, 조각조각 나눠서 먹으면 쉬운것과 비슷하다.
분할 정복의 대표 알고리즘으로는 병합 정렬과 퀵 정렬이 있다.
1. 병합 정렬(Merge Sort)
병합 정렬은 배열을 반으로 나누고, 각각을 정렬한 뒤, 두 정렬된 배열을 합쳐서 전체 배열을 정렬하는 방법이다.
멀쩡히 있는 배열을 왜 쪼갤까?
배열을 작게 나누면, 작은 문제들은 쉽게 해결되고, 마지막에 이들을 합치면 큰 문제도 쉽게 풀린다는 개념이다.
fun mergeSort(arr: IntArray): IntArray {
if (arr.size <= 1) return arr // 배열 크기가 1 이하이면 이미 정렬된 상태
val mid = arr.size / 2
val left = mergeSort(arr.copyOfRange(0, mid))
val right = mergeSort(arr.copyOfRange(mid, arr.size))
return merge(left, right)
}
fun merge(left: IntArray, right: IntArray): IntArray {
var i = 0
var j = 0
val merged = mutableListOf<Int>()
while (i < left.size && j < right.size) {
if (left[i] <= right[j]) {
merged.add(left[i])
i++
} else {
merged.add(right[j])
j++
}
}
while (i < left.size) {
merged.add(left[i])
i++
}
while (j < right.size) {
merged.add(right[j])
j++
}
return merged.toIntArray()
}
fun mainMergeSort() {
val arr = intArrayOf(38, 27, 43, 3, 9, 82, 10)
println("원본 배열: ${arr.joinToString(", ")}")
val sortedArr = mergeSort(arr)
println("정렬된 배열: ${sortedArr.joinToString(", ")}")
}
위 코드의 실행 결과를 살펴보자
원본 배열: 38, 27, 43, 3, 9, 82, 10
정렬된 배열: 3, 9, 10, 27, 38, 43, 82
원본 배열이 정렬되는 것을 볼 수 있다.
2. 퀵 정렬(Quick Sort)
퀵 정렬은 배열에서 하나의 값을 피벗(pivot)으로 선택한 후, 피벗보다 작은 값과 큰 값으로 배열을 분할하고, 이를 재귀적으로 정렬하는 방법이다.
코드로 알아보는게 이해가 더 쉬울것 같다.
fun quickSort(arr: IntArray, low: Int = 0, high: Int = arr.size - 1) {
if (low < high) {
val pi = partition(arr, low, high)
quickSort(arr, low, pi - 1)
quickSort(arr, pi + 1, high)
}
}
fun partition(arr: IntArray, low: Int, high: Int): Int {
val pivot = arr[high] // 1. 피벗으로 배열의 마지막 원소를 선택
var i = low - 1 // 2. i는 피벗보다 작거나 같은 요소들이 위치할 인덱스의 마지막 위치를 추적
// 3. low부터 high - 1까지 반복하여 피벗과 비교
for (j in low until high) {
if (arr[j] <= pivot) { // 만약 현재 값이 피벗보다 작거나 같으면,
i++ // i를 한 칸 증가시키고,
// 4. arr[i]와 arr[j]를 교환하여, 피벗보다 작은 값들을 배열 앞쪽으로 모읍니다.
val temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
}
// 5. i + 1 위치와 피벗(arr[high])을 교환하여, 피벗이 정렬된 위치에 오도록 합니다.
val temp = arr[i + 1]
arr[i + 1] = arr[high]
arr[high] = temp
return i + 1 // 피벗의 최종 위치를 반환합니다.
}
fun mainQuickSort() {
val arr = intArrayOf(10, 7, 8, 9, 1, 5)
println("원본 배열: ${arr.joinToString(", ")}")
quickSort(arr)
println("정렬된 배열: ${arr.joinToString(", ")}")
}
코드를 살펴보면 분할, 정복, 결합을 모두 볼 수 있다.
'자료구조&알고리즘 > Kotlin 활용' 카테고리의 다른 글
| Kotlin 연습하기(12) - 해시 테이블 (0) | 2025.04.25 |
|---|---|
| Kotlin 연습하기(11) - 투 포인터와 슬라이딩 윈도우 알고리즘 (2) | 2025.04.23 |
| 프로그래머스 (기초) - 5명씩 (0) | 2025.04.18 |
| Kotlin 연습하기(10) - 그리디 알고리즘 (2) | 2025.04.14 |
| Kotiln 연습하기(9) - DFS / BFS (1) | 2025.04.11 |