1. 분할 정복(Divde and Conquer)
Tip
•
문제를 소문제로 분할 즉, Top-Down Approach 방법입니다.
•
각각의 소문제를 해결하고, 소문제의 해결 결과를 이용하여 전체 문제를 해결하는 구조입니다.
Ex) 합병 정렬, 퀵 정렬
•
분할 정복법은 소문제도 분할 정복법으로 해결하기 때문에 재귀호출과 관련이 있습니다.(재귀호출을 이용하여 구현하는 경우가 많습니다.)
2. 분할 정복 예제 - 연속 부분 최대합
func getSubMax(_ array: [Int], _ start: Int, _ end: Int) -> Int {
//array의 start 부터 end 까지의 연속 부분 최대합을 반환하는 함수
if start >= end {
return array[start]
}
let mid: Int = (start + end) / 2
let leftSubMax: Int = getSubMax(array, start, mid)
let rightSubMax: Int = getSubMax(array, mid + 1, end)
var leftSum, leftMax, rightSum, rightMax, middleSubMax: Int
leftSum = 0
leftMax = -987987987
rightSum = 0
rightMax = -987987987
for i in stride(from: mid, through: start, by: -1) {
leftSum += array[i]
leftMax = leftMax < leftSum ? leftSum : leftMax
}
for i in mid + 1...end {
rightSum += array[i]
rightMax = rightMax < rightSum ? rightSum : rightMax
}
middleSubMax = leftMax + rightMax
if leftSubMax > rightSubMax && leftSubMax > middleSubMax {
return leftSubMax
} else if rightSubMax > leftSubMax && rightSubMax > middleSubMax {
return rightSubMax
} else {
return middleSubMax
}
}
Swift
복사