머지소팅
-
[알고리즘] Divide & Conquer (분할정복기법)SW/Algorithm 2018. 1. 1. 10:30
Divide & Conquer (분할정복기법) Recursion 기반 해결기법 분할정복기법의 문제해결 시나리오 분할(Divide) : 주어진 문제를 쪼갬 정복(Conquer) : 나누어진 작은 문제는 재귀로 해결. (재귀적으로 계속 분할해간다) 통합(Combine) : 나눴던 문제들로부터 구한 해답들을 서로 통합하여 원래 문제의 해답을 만든다. Top-Down 문제해결 방법 Top-Down : 작은 문제로 분할하여 해결하는 방법 Recursion으로 알고리즘 구현 Top-Down 을 더 작은 문제로 반복해서 분할 Divide & Conquer 분할정복기법 알고리즘의 정확성 증명 (수학적 귀납법 사용) 분할정복기법 알고리즘의 시간복잡도 계산Tromino 타일 채우기 문제 : 한 모퉁이가 없는 2X2로 타일..