백과

직접 풀 수 없는 문제를 적당히 나누어서 푸는 수법을 체계화한 것. 먼저 풀 수 있는 문제(부모문제)를 직접 풀 수 없으면 몇 개의 자식문제로 분할하여, 각각의 자식문제는 부모문제보다 풀기 쉽게 된다. 자식문제를 하나 골라서 그것이 풀리지 않으면 다시 작은 자식문제로 분할한다.

부모문제에서 자식문제, 자식문제에서 손자문제로 분할하는 과정은 반드시 부모문제를 뿌리, 자식문제를 노드로 하는 트리 구조에 표현된다. 직접 풀리는 자식문제는 지분(技分)이 없으므로 잎에 해당한다. 선택한 자식문제가 풀리는 경우는 트리로 되돌리고 또 풀리지 않는 문제는 골라서 해결한다.

자식문제가 전부 풀리면, 주어진 문제가 풀리게 된다. 일반적으로 자식문제를 선출하여 기준이나 자식문제로 분할하는 방법 등에 의해서 계산량은 크게 변한다.