귀하는 로그인되어 있지 않습니다. 이대로 편집하면 귀하의 IP 주소가 편집 기록에 남게 됩니다.스팸 방지 검사입니다. 이것을 입력하지 마세요!== 개요 == 주어진 문제를 작은 사례로 나누고(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로 가져옴] <!--분류--> [[분류:알고리즘]] 편집 요약 가온 위키에서의 모든 기여는 크리에이티브 커먼즈 저작자표시-동일조건변경허락 라이선스로 배포된다는 점을 유의해 주세요(자세한 내용에 대해서는 가온 위키:저작권 문서를 읽어주세요). 만약 여기에 동의하지 않는다면 문서를 저장하지 말아 주세요. 또한, 직접 작성했거나 퍼블릭 도메인과 같은 자유 문서에서 가져왔다는 것을 보증해야 합니다. 저작권이 있는 내용을 허가 없이 저장하지 마세요! 취소 편집 도움말 (새 창에서 열림)