[완전 탐색] Combinatorial search 조합 탐색

1. 조합 탐색 동적 계획법이나 분할 정복 등의 디자인 패러다임은 적절히 적용 될 때는 매우 유용하나 모든 문제에 적용할 수 없다. 이럴 경우 결국 완전 탐색으로 풀어야 한다. 완전 탐색은 탐색 공간의 크기에 직접적으로 비례한다. 따라서 문제의 규모가 클 경우 사용하기 어렵다는 문제가 발생한다. 이런 완전 탐색을 포함해, 유한한 크기의 탐색 공간을 뒤지면서 답을 찾아내는 알고리즘들을 알고리즘 문제해결 전략에서는 조합탐색이라고 부른다. 조합 탐색에는 다양한 최적화 기법이 있으며 모두 기본적으로 모두 최적해가 될 가능성이 없는 답들을 탐색하는 것을 방지하여 만들어 봐야 할 답의 수를 줄이는 것을 목표로 한다. 조합 탐색을 최적화하기 위해 어떤 방법을 사용해야 할지 찾아내는 것은 문제 자체에 대한 깊은 식견을..

2021.01.19