Divide and Conquer

 

분할정복

재귀적 기술로 단순한 알고리즘이 아니라 문제를 풀기위한 방법론에 가깝다. 문제에 접근하는 사고 방식을 제시하며, 단계는 아래와 같다.

 

  • 단계
    1. 기본 단계를 해결한다. 가능한 간단한 문제여야 한다.
    2. 문제가 기본 단계가 될 때까지 나누거나 작게 만든다.

 

  • 예시

## 배열 내 숫자들의 합계를 구하려 한다.
#재귀 함수를 사용할 시 -
'''
1. 기본단계를 찾는다. 
   가장 간단한 배열로 원소개수가 0개이거나 1개인 배열을 보통 기본으로 한다.

2. 재귀함수를 호출할 때마다 호출 대상이 되는 배열의 크기가 점점 감소하도록 한다.
    리스트를 받는다  > 리스트가 비어 있으면 0을 반환한다.
                    > 그렇지 않다면 총합은 리스트의 첫 번째 숫자와 나머지 리스트의 총합을 더한 값이 된다.


**재귀에서는 상태를 추척한다는 점을 염두한다. (부분적으로 실행된 함수 호출의 상태를 모두 저장)
'''

 

 

reference

도서 : Hello Coding 그림으로 개념을 이해하는 알고리즘