알고리즘 - 분할정복

분할정복(divide and conquer) 방법은 순환적으로 문제를 푸는 하향식 접근 방법이다.

분할정복은 3가지 단계 분할(divide), 정복(conquer), 결합(combine)으로 이루어져 있습니다.

분할정복 방법을 사용할 알고리즘으로는 대표적으로 이진탐색, 합병 정렬, 선택 문제가 있습니다.

 

이진탐색(Binary Search)

이진탐색은 주어진 자료가 정렬되어 있을 때, 사용할 수 있는 검색 알고리즘입니다.

참고로 이진탐색은 분할(배열을 반으로 나누는 과정)과 정복(값의 대소 비교)은 존재하지만, 값을 찾는 순간 모든 과정이 끝나므로 결합 과정이 필요하지 않습니다.

따라서, 이진탐색은 분할과 정복으로만 이루어져 있습니다.

이진탐색의 시간복잡도

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val array = intArrayOf(10,40,25,35,47,9,89,100,2)
    array.sort()
    val target = readLine().toInt()
    val idx = bSearch(0, array.size - 1, array, target)

    println("array : ${array.contentToString()}\ntarget : $target\nidx : $idx")
    if (idx in array.indices) {
        println("array[$idx] : ${array[idx]}")
    }
}

fun bSearch(left: Int, right: Int, array : IntArray, target : Int) : Int {
    if (left > right) {
        return -1
    }

    // 정복
    val mid = (left + (right - left) / 2)
    if (array[mid] == target) {
        return mid
    } else if (array[mid] > target) {
        // 분할
        return bSearch(left, right = mid - 1, array, target)
    } else if (array[mid] < target) {
        // 분할
        return bSearch(left = mid + 1, right, array, target)
    }

    return -1
}

---

합병정렬(Merge Sort)

합병 정렬은 배열의 크기가 1이 될 때까지 계속하여 분할하고 크기가 가장 작아지면 정복(나눠진 부분 배열을 정렬)을 하기 시작합니다. 마지막으로 결합(두 부분 배열을 합병)합니다.

 

1. 분할

분할은 위에 그림처럼 이루어지고 정복(두 부분 배열을 정렬)도 아주 간단합니다.

 

2. 정복과 결합

위와 같이 두 개의 부분 배열을 정렬하려면 우선 30과 25 중에 작은 값을 먼저 배열에 넣습니다.

이제 30과 55 중에 작은 값을 넣습니다.

이렇게 계속 반복하면 결국 두 배열의 정렬이 완성됩니다.

---

선택 문제

선택문제는 배열에서 i번째로 작은 수를 찾는 문제입니다.

이는 퀵정렬에서 사용하는 분할 정복을 사용해서 쉽게 풀 수 있습니다.

퀵정렬처럼 주어진 수들을 분할정복한 후에 기준이 됐던 pivot의 인덱스가 i보다 크면 왼쪽 배열을 작으면 오른쪽 배열을 자릅니다.

후에 이전과 같은 작업을 반복하면 됩니다.

 

위의 배열을 예시로 들면 30의 인덱스가 i보다 크면 왼쪽 배열에서 위 작업을 반복

30의 인덱스가 i보다 크면 오른쪽 배열에서 위 작업을 반복합니다.

5번째로 작은 수를 구했다면 30을 리턴.

1~4번째로 작은 수면 10, 15, 20, 25에서 위 작업을 반복.

6~8번째로 작은 수면 35,40,45에서 위 작업을 반복합니다.

 

[직접 구현해본 코드]

fun main() {
    val array = IntArray(15)
    var i = 0

    try {
        repeat(10) {
            i = (array.size * Math.random()).toInt()
            array.forEachIndexed { idx, num ->
                array[idx] = (Math.random() * 100).toInt()
            }

            val pIdx: Int = select(array, i = i, left = 0, right = array.size - 1)
            println("${i}번째로 작은 수는 ${array[pIdx]}\narray : ${array.contentToString()}")

            val answer = array[pIdx]
            array.sort()
            println(array.contentToString())
            if (answer != array[i]) {
                throw Exception("테스트 케이스가 틀림.")
                return
            }
        }
    } catch (e: StackOverflowError) {
        println(e.localizedMessage)
    }
}

fun select(array: IntArray, i: Int, left: Int, right: Int): Int {
    // 'i' can't be bigger than arrays size
    if (array.size < i) {
        return -1
    }

    val pIdx: Int = partition(array, start = left, end = right)
    if (i == pIdx) {
        return pIdx
    } else if (i > pIdx) {
        // 오른쪽 검색
        return select(array, i, left = pIdx + 1, right = right)
    } else {
        // 왼쪽 검색
        return select(array, i, left = left, right = pIdx - 1)
    }
}

fun partition(array: IntArray, start: Int, end: Int): Int {
    val pivot = array[start]
    var lPointer = start
    var rPointer = end
    while (lPointer <= rPointer) {
        while (lPointer < end && array[lPointer] <= pivot) {
            lPointer++
        }
        while (rPointer > start && array[rPointer] >= pivot) {
            rPointer--
        }

        if (lPointer <= rPointer) {
            val temp = array[lPointer]
            array[lPointer] = array[rPointer]
            array[rPointer] = temp

            if (lPointer == rPointer) {
                break
            }
        }
    }

    val temp = array[start]
    array[start] = array[rPointer]
    array[rPointer] = temp
    return rPointer
}