divide and conquer : 문제해결전략 중 하나
Divide and Conquer:
어떤 문제를 유사한 형태를 가지는 더 작은 크기의 서브 문제들로 나눈 후 이들을 재귀적으로 같은 방식으로 해결한 뒤 각 서브 문제들을 해결한 결과를 활용하여 원래 문제를 해결하는 방식
활용되는 곳
: merge sort , quick sort, binary search 등
Divide and conquer 3단계
- Divide → 기존 문제를 작은 부분 문제로 나눔
- Conquer → 각 부분 문제를 해결
- Combine → 부분 문제들의 솔루션을 합쳐서 기존 문제를 해결
- 재귀적인 경우가 많긴함
- Base Case인지 Recursive Case 인지 판단하기
- Base Case : 이미 문제가 충분히 작아서 부분 문제로 나누지 않아도 바로 답을 알 수 있는 경우
- Recursive Case : 문제가 커서 바로 답을 알 수 없어서, 같은 형태의 부분 문제들로 쪼개서 풀어야 하는 경우
recursive가 개념이 아직도 어렵긴하지만, 그래도 일부는 이해되기 시작하고 있다(라고 생각한다)