방송대 컴퓨터과학과 알고리즘 출석수업대체(만점)

목차

없음

본문내용

1. 분할정복 방법

주어진 문제의 입력을 더 이상 나눌 수 없을 때까지 두 개 이상의 작은 문제들로 순환적으로 분할하고, 이렇게 분할된 작은 문제들을 각각 해결한 후 이들의 해를 결합하여 원래의 문제의 해를 구하는 방식으로, 각 순환호출이 이루어질 때마다 다음과 같은 3단계의 작업이 이루어진다.
1) 분할(divide) : 주어진 문제의 입력을 여러 개의 작은 문제로 분할한다．
2) 정복(conquer) : 작은 문제들을 순환적으로 분할한다．만약 더 이상 분할되지 않을 정도로 충분히 작다면 순환호출 없이 작은 해를 구한다(정복한다）.
3) 결합(combine,합병）: 작은 문제에 대해 정복된 해를 결합하여 원래 문제의 해를 구한다．
분할된 작은 문제는 원래의 문제에 비해 입력 크기만 작아졌을 뿐 문제 자체는 원래 문제와 동일하며，서로 독립적이기 때문에 각각의 작은 문제를 다시 순환적으로 분할하고 그 결과를 통합하는 것이 가능하다．

참고 자료

없음