감소 정복(decrease-and-conquer)은 주어진 문제에 대한 풀이와 더 작은 문제에 대한 풀이의 관계를 찾아내는 것을 바탕으로 하는 전략이다. 일단 그 관계를 찾아내면 큰 문제를 작은 문제로 환원시키는 재귀 알고리즘을 유도할 수 있으며 그 과정을 반복하다 보면 직접 풀 수 있을 정도의 작은 문제에 다다르게 된다.¹ 예를 들면 이렇다.

유명 인사 문제 n명이 있을 때 어떤 사람이 다른 사람을 아무도 모르지만 다른 사람들이 모두 그를 안다면 그 사람을 유명 인사라고 부르자. “이 사람을 압니까?”라는 질문만으로 유명 인사를 알아내는 방법을 제시하라.

편의상 n명 중에 유명 인사가 존재한다고 가정하자. 그러면 이 문제는 한 번에 1씩 줄이는 알고리즘으로 해결할 수 있다. n = 1이면 그냥 당연히 그는 유명 인사다. n > 1이면 그중 두 명을 뽑고 각각 A, B라고 부르자. 그리고 B를 아는지 A에게 물어본다. A가 B를 알면 유명 인사 후보군에서 A는 제외할 수 있다. A가 B를 모른다면 B를 유명 인사 후보군에서 제외하면 된다. 그리고 유명 인사가 될 수 있는 나머지 n - 1명의 사람에 대해 이 문제를 재귀적으로 (즉, 같은 방법으로) 풀 수 있다.

간단히 연습 삼아 강 건너기 퍼즐(2.004)을 풀어보면 어떤 방법인지 알 수 있을 것이다.