도입

동적 계획법이나 분할 정복 등의 디자인 패러다임은 적절히 적용될 때는 매우 유용하지만, 모든 문제에 적용할 수는 없습니다. 적절한 분할 방법이 없는 문제를 분할 정복으로 풀 수도 없고, 중복되는 부분 문제가 전혀 없거나 메모리를 너무 많이 사용하는 문제에 동적 계획법을 쓸 수도 없습니다. 이런 경우에 우리는 결국 시작점인 완전 탐색으로 돌아와 다시 시작해야 합니다.
완전 탐색 알고리즘은 대개 답을 만드는 과정을 여러 개의 선택으로 나눈 뒤, 재귀 호출을 이용해 각각의 선택지를 채워가는 형태로 구현되곤 합니다. 이때 부분 답과 완성된 답의 집합을 탐색 공간이라고 부릅니다. 예를 들면 여행하는 외판원 문제(TSP)에서 탐색 공간의 한 원소는 지금까지 방문한 정점의 목록과 현재 위치로 구성됩니다.
완전 탐색은 모든 답을 다 만들어 보면서 문제를 해결하므로 문제의 규모가 조금이라도 클 경우 사용하기 어렵다는 문제점이 있습니다.
완전 탐색을 포함해, 유한한 크기의 탐색 공간을 뒤지면서 답을 찾아 내는 알고리즘들을 조합 탐색이라고 부릅니다. 조합 탐색에는 다양한 최적화 기법이 있으며, 이들은 접근 방법은 다르지만 모두 기본적으로 모두 최적해가 될 가능성이 없는 답들을 탐색하는 것을 방지하여 만들어 봐야 할 답의 수를 줄이는 것을 목표로 합니다.
조합 탐색을 최적화화기 위해 어떤 방법을 사용해야 할지 찾아내는 것은 문제 자체에 대한 깊은 식견을 요구하며, 속도와 정확도 사이의 상충 관계, 다양한 입력 형태 사이의 상충 관계 등을 모두 고려해야 합니다. 이렇게 어려운 문제이기 때문에 조합 탐색에는 딱히 정답이 없습니다.
조합 탐색 최적화 기법들은 크게 두 가지로 분류할 수 있습니다.

• 가지치기(pruning) 기법은 탐색 과정에서 최적해로 연결될 가능성이 없는 부분들을 잘라냅니다.
• 좋은 답을 빨리 찾아내는 기법들은 탐색의 순서를 바꾸거나, 탐색 시작 전에 탐욕법을 이용해 적당히 좋은 답을 우선 찾아냅니다. 완전 탐색의 경우 답을 어떤 순서로 찾아내건 상관없지만, 가지치기와 함께 사용할 경우 더 좋은 답을 알고 있으면 좀더 일찍 탐색을 중단할 수 있기 때문에 탐색의 효율이 좋아집니다.

조합 탐색 기법들

최적해보다 나빠지면 그만두기

가장 기초적인 가지치기 방법은 현재 상태의 답이 지금까지 구한 최적해와 같거나 더 나쁠 때 탐색을 중단하는 것입니다.

휴리스틱을 이용한 가지치기

휴리스틱을 이용해 답의 남은 부분을 어림짐작하는 가지치기를 이용하면 좀더 똑똑하게 가지치기를 할 수 있습니다.
휴리스틱을 이용한 가지치기는 남은 조각들을 푸는 최적해를 찾기는 오래 걸리더라도, 이 값을 적당히 어림짐작하기는 훨씬 빠르게 할 수 있다는 점을 이용해 가지치기를 수행합니다.
휴리스틱 알고리즘에는 문제가 있을 수 있습니다. 휴리스틱 알고리즘은 어디까지나 어림짐작이기 때문에 그 값이 맞지 않습니다. 만약 휴리스틱이 최적해를 잘못 짐작해 걸러내 버린다면 영영 최적해를 찾을 수 없습니다. 이런 일이 일어나지 않기 위해서는 문제를 과소평가하는 휴리스틱을 사용해야 합니다. 낙관적인 휴리스틱이라고도 말합니다.

탐색의 순서 바꾸기

탐색의 순서를 바꿔서 좋은 답을 좀더 일찍 발견할 확률이 올라간다면 가지치기를 더 많이 할 수 있습니다. 순서를 바꿔 조합 탐색을 수행하는 것은 탐색을 시작하기 전에 탐욕적 알고리즘으로 초기해를 구하는 것과 같은 효과가 있습니다.

마지막 단계 메모이제이션하기

조합 탐색 과정에서 같은 상태를 두 번 이상 맞닥뜨리는 것은 흔한 일입니다. 이 경우 메모이제이션을 하면 좋습니다.
물론 대부분의 경우 메모이제이션을 그냥 사용하기에는 메모리가 부족할 것입니다. 이 문제를 해결하기 위해, 남은 조각의 수가 미리 정해둔 수 $k$ 이하일 때만 메모이제이션을 하는 것이 좋습니다.
단 메모이제이션으로 이득을 쉽게 얻을 수는 없습니다. 가지치기를 사용하는 함수는 쉽게 메모이제이션할 수 없기 때문입니다. 메모이제이션을 하기 위해서는 함수의 반환 값이 현재의 상태에만 영향을 받아야 하는데, 가지치기를 적용하면 현재 상태까지 오기 위한 경로에 따라 반환 값이 달라질 수 있습니다. 물론 경로까지 메모이제이션의 키로 사용하면 답이 틀리지는 않겠지만, 경로들은 서로 겹치지 않기 때문에 메모이제이션을 쓰는 의미가 없습니다. 따라서 이 방법을 사용하기 위해서는 가지치기를 사용하지 않는 동적 계획법 함수를 별도로 작성한 뒤, 마지막 $k$단계에 도달하면 이 함수를 사용하도록 구현해야 합니다.

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