도입

문제를 해결하기 위한 여러 방법이 있지만 구현 난이도가 가장 낮은 방법은 무식하게 푸는 것입니다. 완전 탐색이라고도 부릅니다.

재귀 함수

재귀 함수란 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수를 가리킵니다. 재귀 함수는 '더이상 쪼개지지 않는' 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문을 포함해야 합니다. 이때 쪼개지지 않는 가장 작은 작업들을 가리켜 재귀 호출의 기저 사례라고 합니다.
설명은 간단하지만 작업을 쪼개는 기준과 기저 사례를 잘 정의하는 것이 완전 탐색으로 푸는 것의 관건입니다.

완전 탐색 레시피

이 과정이 모든 문제에 항상 적용되는 것은 아니지만, 어떤 식으로 문제에 처음 접근해야 할지에 대한 대략적인 지침이 될 것입니다.

1. 완전 탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수에 정확히 비례합니다. 최대 크기의 입력을 가정했을 때 답의 개수를 계산하고 이들을 모두 제한 시간 안에 생성할 수 있을지를 가늠합니다.
2. 가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눕니다. 각 선택은 답의 후보를 만드는 과정의 한 조각이 됩니다.
3. 그중 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성합니다.
4. 조각이 하나밖에 남지 않은 경우, 혹은 하나도 남지 않은 경우에는 답을 생성했으므로, 이것을 기저 사례로 선택해 처리합니다.

참고문헌: 구종만, 프로그래밍 대회에서 배우는 알고리즘 문제해결전략, 인사이트, (2012)