[완전탐색] 완전탐색에 대해 알아보자

완.전.탐.색! 말 그대로 무식하게 모든 경우를 다 보는 것입니다!
컴퓨터의 가장 강한 이점인 '속도'를 극한으로 이용할 수 있는 방법입니다.
보통 완전 탐색은 최적화 문제에서 많이 사용합니다.
최적화 문제란, 여러가지 경우를 만들 수 있을 때, 가장 적합한 답의 경우를 구하는 문제를 말합니다.
예를 들면, 마을 사이를 잇는 도로가 있고 도로마다 거리가 다를 때, A에서 B로 가는데 가장 짧은 도로의 길이를 구하는 문제가 있습니다.
이와 같은 문제를 풀 때 완전탐색을 이용하면 A에서 B로 가는 모든 도로의 경우를 구한 뒤에 그 중 거리가 가장 짧은 값을 답으로 선정합니다.
물론, 완전탐색을 이용해서 문제를 풀기 위해서는 문제의 조건에서 주어진 시간 내에 풀 수 있을지 잘 생각해보아야 합니다.
완전탐색을 너무 많이하면 결국 시간내에 풀 수 없는 경우가 생기기 때문입니다.

보통 완전 탐색을 구현할 때에는 재귀를 많이 사용합니다. (물론, 재귀 말고도 for문을 이용하거나 다른 방법을 이용할 수 있습니다!)
재귀 함수란, 자신이 수행할 작업을 유사한 작은 조각으로 쪼개서 문제를 해결하는 방법입니다.
이를 위해서, 자기 자신을 함수 내에서 다시 호출합니다.
따라서, 재귀 함수를 잘못 사용하면 계속해서 무한 루프를 도는 경우가 생깁니다.
이렇게 되면 보통 스택이 터지기 때문에 segmentation 오류가 생깁니다.
이를 피하기 위해서 재귀 함수는 크게 General case와 Base Case로 나눕니다.
Base Case는 재귀 함수가 최소의 조각으로 나누어져서 return을 하는 부분입니다.
그리고 General Case는 작은 조각들의 결과를 이용해 더 큰 조각의 결과를 만들어 결국 원하는 결과를 얻을 수 있습니다.
이해를 쉽게 하기 위해서 재귀 함수를 이용하여 1부터 n까지의 합을 구하는 함수를 만들어 봅시다.

int sum(int n)
{
    //Base Case
    if(n == 1) return 1;
 
    //General Case
    return n + sum(n - 1);
}

보통 완전 탐색의 경우를 사용하는 경우는 크게 3가지 유형이 있습니다.

1. 모든 순열 만들기.
2. 모든 조합 만들기.
3. 부분 집합 만들기.

이에 대해선 나중에 다시 설명하겠습니다!


재귀함수로 순열 만들기
비트 마스킹으로 조합 만들기
비트 마스킹으로 부분집합 만들기