Gaon12: 시작

2023-03-28T01:54:05Z

시작

새 문서

== 개요 ==
주어진 문제를 작은 사례로 나누고(Divide), 각각의 작은 문제들을 해결하여 정복(Conquer)하는 방법이다. 분할 정복법은 문제의 사례를 2개 이상의 더 작은 사례로 나눈다. 이 작은 사례는 주로 원래 문제에서 따온다. 나눈 작은 사례의 해답을 바로 얻을 수 있으면 해를 구하고 아니면 더 작은 사례로 나눈다.

'''해를 구할 수 있을 만큼 충분히 더 작은 사례로 나누어 해결하는 방법'''이다.

분할 정복법은 하향식(top-down) 접근 방법으로 최상위 사례의 해답은 아래로 내려가면서 작은 사례에 대한 해답을 구함으로써 구한다.

== 설계전략 ==
# 문제 사례를 하나 이상의 작은 사례로 '''분할(Divide)'''한다.
# 작은 사례들을 각각 '''정복(Conquer)'''한다. 작은 사례가 충분히 작지 않은 이상 재귀를 사용한다.
# 필요하다면, 작은 사례에 대한 해답을 '''통합(Combine)'''하여 원래 사례의 해답을 구한다.

== 분할 정복 사용 예 ==
* 이분검색
* 합병정렬
* 퀵정렬
* 최대값 찾기
* 임계값의 결정
* 쉬트라센 행렬곱셈 알고리즘 등

=== 이분검색 ===
문제 : 10개의 정렬된 배열에서 값을 21가진 인덱스를 찾아라.

low: 0
high: 9
middle: (low + high)/2 => 4.5 => 4

{| class="wikitable" style="text-align: center;"
| style="background-color: #00BCD4; color: white; font-size: bold;" | '''A(0)''' || style="background-color: #00BCD4; color: white; font-size: bold;" | '''A(1)''' || style="background-color: #00BCD4; color: white; font-size: bold;" | '''A(2)''' || style="background-color: #00BCD4; color: white; font-size: bold;" | '''A(3)''' || style="background-color: #00BCD4; color: white; font-size: bold;" | '''A(4)''' || style="background-color: #00BCD4; color: white; font-size: bold;" | '''A(5)''' || style="background-color: #00BCD4; color: white; font-size: bold;" | '''A(6)''' || style="background-color: #00BCD4; color: white; font-size: bold;" | '''A(7)''' || style="background-color: #00BCD4; color: white; font-size: bold;" | '''A(8)''' || style="background-color: #00BCD4; color: white; font-size: bold;" | '''A(9)'''
|-
| style="background-color: #CAF4FA; color: black; font-size: bold;" | 5 || style="background-color: #CAF4FA; color: black; font-size: bold;" | 7 || style="background-color: #CAF4FA; color: black; font-size: bold;" | 10 || style="background-color: #CAF4FA; color: black; font-size: bold;" | 12 || style="background-color: #CAF4FA; color: black; font-size: bold;" | 16 || style="background-color: #CAF4FA; color: black; font-size: bold;" | 20 || style="background-color: #CAF4FA; color: black; font-size: bold;" | 21 || style="background-color: #CAF4FA; color: black; font-size: bold;" | 25 || style="background-color: #CAF4FA; color: black; font-size: bold;" | 28 || style="background-color: #CAF4FA; color: black; font-size: bold;" | 30
|}<br>

low: 4 + 1 => 5
high: 9
middle: 7

{| class="wikitable" style="text-align: center;"
| style="background-color: #DB1A1A; color: white; font-size: bold;" | '''A(0)''' || style="background-color: #DB1A1A; color: white; font-size: bold;" | '''A(1)''' || style="background-color: #DB1A1A; color: white; font-size: bold;" | '''A(2)''' || style="background-color: #DB1A1A; color: white; font-size: bold;" | '''A(3)''' || style="background-color: #DB1A1A; color: white; font-size: bold;" | '''A(4)''' || style="background-color: #00BCD4; color: white; font-size: bold;" | '''A(5)''' || style="background-color: #00BCD4; color: white; font-size: bold;" | '''A(6)''' || style="background-color: #00BCD4; color: white; font-size: bold;" | '''A(7)''' || style="background-color: #00BCD4; color: white; font-size: bold;" | '''A(8)''' || style="background-color: #00BCD4; color: white; font-size: bold;" | '''A(9)'''
|-
| style="background-color: #FF8800; color: black; font-size: bold;" | 5 || style="background-color: #FF8800; color: black; font-size: bold;" | 7 || style="background-color: #FF8800; color: black; font-size: bold;" | 10 || style="background-color: #FF8800; color: black; font-size: bold;" | 12 || style="background-color: #FF8800; color: black; font-size: bold;" | 16 || style="background-color: #CAF4FA; color: black; font-size: bold;" | 20 || style="background-color: #CAF4FA; color: black; font-size: bold;" | 21 || style="background-color: #CAF4FA; color: black; font-size: bold;" | 25 || style="background-color: #CAF4FA; color: black; font-size: bold;" | 28 || style="background-color: #CAF4FA; color: black; font-size: bold;" | 30
|}<br>

low: 5
high: 7 - 1 = 6
middle: 5

{| class="wikitable" style="text-align: center;"
| style="background-color: #DB1A1A; color: white; font-size: bold;" | '''A(0)''' || style="background-color: #DB1A1A; color: white; font-size: bold;" | '''A(1)''' || style="background-color: #DB1A1A; color: white; font-size: bold;" | '''A(2)''' || style="background-color: #DB1A1A; color: white; font-size: bold;" | '''A(3)''' || style="background-color: #DB1A1A; color: white; font-size: bold;" | '''A(4)''' || style="background-color: #00BCD4; color: white; font-size: bold;" | '''A(5)''' || style="background-color: #00BCD4; color: white; font-size: bold;" | '''A(6)''' || style="background-color: #DB1A1A; color: white; font-size: bold;" | '''A(7)''' || style="background-color: #DB1A1A; color: white; font-size: bold;" | '''A(8)''' || style="background-color: #DB1A1A; color: white; font-size: bold;" | '''A(9)'''
|-
| style="background-color: #FF8800; color: black; font-size: bold;" | 5 || style="background-color: #FF8800; color: black; font-size: bold;" | 7 || style="background-color: #FF8800; color: black; font-size: bold;" | 10 || style="background-color: #FF8800; color: black; font-size: bold;" | 12 || style="background-color: #FF8800; color: black; font-size: bold;" | 16 || style="background-color: #CAF4FA; color: black; font-size: bold;" | 20 || style="background-color: #CAF4FA; color: black; font-size: bold;" | 21 || style="background-color: #FF8800; color: black; font-size: bold;" | 25 || style="background-color: #FF8800; color: black; font-size: bold;" | 28 || style="background-color: #FF8800; color: black; font-size: bold;" | 30
|}<br>

low: 5 + 1 = 6
high: 6

{| class="wikitable" style="text-align: center;"
| style="background-color: #DB1A1A; color: white; font-size: bold;" | '''A(0)''' || style="background-color: #DB1A1A; color: white; font-size: bold;" | '''A(1)''' || style="background-color: #DB1A1A; color: white; font-size: bold;" | '''A(2)''' || style="background-color: #DB1A1A; color: white; font-size: bold;" | '''A(3)''' || style="background-color: #DB1A1A; color: white; font-size: bold;" | '''A(4)''' || style="background-color: #DB1A1A; color: white; font-size: bold;" | '''A(5)''' || style="background-color: #1FFF3D; color: white; font-size: bold;" | '''A(6)''' || style="background-color: #DB1A1A; color: white; font-size: bold;" | '''A(7)''' || style="background-color: #DB1A1A; color: white; font-size: bold;" | '''A(8)''' || style="background-color: #DB1A1A; color: white; font-size: bold;" | '''A(9)'''
|-
| style="background-color: #FF8800; color: black; font-size: bold;" | 5 || style="background-color: #FF8800; color: black; font-size: bold;" | 7 || style="background-color: #FF8800; color: black; font-size: bold;" | 10 || style="background-color: #FF8800; color: black; font-size: bold;" | 12 || style="background-color: #FF8800; color: black; font-size: bold;" | 16 || style="background-color: #FF8800; color: black; font-size: bold;" | 20 || style="background-color: #02F758; color: black; font-size: bold;" | 21 || style="background-color: #FF8800; color: black; font-size: bold;" | 25 || style="background-color: #FF8800; color: black; font-size: bold;" | 28 || style="background-color: #FF8800; color: black; font-size: bold;" | 30
|}<br>

<syntaxhighlight lang='java'>
int[] arr = {5, 7, 10, 12, 16, 20, 21, 25, 28, 30}

public int binarySearch(int target) {
low = 0;
high = arr.length;
while (low <= high) {
middle = (low + high) / 2;
if (target == array[middle]) {
return middle;
} else if (target > array[middle]) {
low = middle + 1;
} else {
high = middle - 1;
}
}
return -1; //not found
}
</syntaxhighlight>

== 장단점 ==
=== 장점 ===
* 문제를 나눔으로써 어려운 문제를 해결할 수 있다는 엄청나게 중요한 장점이 있다.
* 이 방식이 그대로 사용되는 효율적인 알고리즘들도 여럿 있으며, 문제를 나누어 해결한다는 특징상 '''병렬적으로 문제를 해결'''하는 데 큰 강점이 있다.

=== 단점 ===
* 함수를 재귀적으로 호출한다는 점에서 함수 호출로 인한 '''오버헤드가 발생'''한다.
* 스택에 다양한 데이터를 보관하고 있어야 하므로 '''[[스택 오버플로우]]가 발생'''하거나 '''과도한 메모리 사용'''을 하게 된다.

[https://kimch3617.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B6%84%ED%95%A0%EC%A0%95%EB%B3%B5%EB%B2%95-Divide-and-Conquer CC BY로 가져옴]


[[분류:알고리즘]]

분할 정복 알고리즘 - 편집 역사

Gaon12: 시작