분할정복 (1) 썸네일형 리스트형 Chap 3. 분할 정복 알고리즘 분할정복 알고리즘 : 주어진 문제의 입력을 분할하여 문제를 해결(정복)하는 방식의 알고리즘 부분 해(분할)를 취합( =정복)하여 원래 문제의 해를 얻음 부분문제와 부분해 더 이상 분할할 수 없을 때까지 분할한다. → 분할한 문제들의 해를 취합 → 부분 취합을 다시 취합 (1) 분할 과정 [상황] 입력 = n 분할 = n을 3개로 분할 각각 분할된 부분 문제의 크기 = n/2 *질문 = 여기서 n을 3개로 분할한 것이므로 각각 분할된 부분 크기는 n/3이 아닌가? ⇒ n이라는 전체 크기를 3등분하여 반으로 나눈다는 의미 3등분을 전체에 대한 것이 아니라 전체의 반의 반이 하나의 등분으로 생각하면 된다. [ 이를 일반화 하면 ] 입력 = n 분할 = n을 b개로 분할 각각 분할된 부분 문제의 크기 = n/a.. 이전 1 다음