수학적 귀납법
분할 정복(Divide And Conquer)
큰 문제를 여러 개의 작은 문제로 쪼갠 다음(분할)
작은 문제들의 답을 이용해 큰 문제의 답을 구함(정복)
- 동적 계획법(DP)와 차이점?
- 분할 정복
- 문제의 크기가 충분히 작은 경우 직접 해결
- 문제의 크기가 큰 경우 k>=1개의 부분 문제로 쪼개서 각각 해결
- 분할 정복의 시간 복잡도
- T(N) = D(N) + sum T(i) + C(N)
- N : 입력의 크기
- T(N) : 입력의 크기가 N인 문제를 풀 때 걸리는 시간
- D(N) : 크기가 N인 문제를 부분 문제로 분할할 때 걸리는 시간
- C(N) : 크기가 N인 문제에서 부분 문제의 답을 합칠 때 걸리는 시간
- 분할 정복의 예 : 병합 정렬