김덕우

<목차>

1. 개념

2. 예제

1. 개념

분할정복(Divide and Conquer)이란 문제를 직접 해결하기 쉬운 단위로 잘게 나눈 후(분할) 작은 문제의 답을 구하여(정복) 저장하고,

작은 문제의 답을 조합하여 전체 문제를 해결하는 방법이다.

아래 그림과 수도코드에서 분할, 정복, 조합에 해당하는 부분을 표시해보았다.

2. 예제 -과반수 엘리먼트(리트코드 169)

1) 문제 

배열을 중에서 전체 엘리먼트의 절반 이상을 차지하는 값을 출력할 것을 요구한다.

위 예시를 보면, 리스트 내 7개의 엘리먼트 중 '정수 2'가 4개로  절반 이상을 차지하므로

결과 값으로 2가 출력된 것을 알 수 있다.

2) 풀이

앞서 개념에서 설명한 것처럼 분할 정복 기법은 분할, 정복, 조합 부분으로 이뤄진다.

전체 코드는 다음과 같으며 분할, 정복, 조합 파트로 세분화하여 살펴보겠다.

(1st) 분할

재귀 함수를 호출할 때, 슬라이싱을 활용하여 입력값(리스트, nums)의 범위를 조정한 한다.

하나의 배열을 두 개로 쪼개는데,

첫 번째 배열(a)은 왼쪽 절반([ : len(nums) // 2] ), 두 번째 배열은 오른쪽 절반( [len(nums) // 2 : ] )으로 슬라이싱 처리한다.

최종적으로 분할된 모습은 아래와 같을 것이다.

(2nd) 정복

끝까지 쪼개면 배열에 값이 하나만 존재할 것이다.

따라서 배열의 길이가 1이 되면 그 값(정수형)을 반환한다.

(3rd) 조합

정복으로 얻은 하위 문제 해답을 조합하여 전체 문제의 답을 구해나간다.

왼쪽 하위 문제에서 절반 이상을 차지하던 값(a)이 상위 문제 배열에서도 절반 이상(   > len(nums) // 2   )을 차지할 때, 

True(정수 1)가 반환되므로 결국 a가 리턴된다.

반대의 경우는 b가 리턴될 것이다. 

이처럼 하부 문제를 구하는 과정을 반복하여 전체 문제의 해답을 도출한다.