[알고리즘 설계] 1. 완전탐색(Exhaustive Search)

알고리즘 문제를 접근할 때 자주 사용되는 기법들이 있습니다. 가장 기본적이고 자주 쓰이는 패턴화된 방법을 [알고리즘 설계] 시리즈를 통해 정리합니다.

그 중에서 가장 기초적이면서 가장 중요한 알고리즘 해결 방법이라고 생각하는 완전탐색(Exhaustive Search)에 대해 이해해보고자 합니다.

완전탐색 (Exhaustive Search)

많은 알고리즘 문제는 대부분 쉬운 방법으로 풀립니다. 하지만 문제를 많이 풀어보지 못한 사람들은 효율적인 연산이나 좋은 방법들을 찾다가 풀지 못하거나 좋은 방법이라고 생각해 풀었더니 버그가 있어 오답을 내는 경우도 많습니다.

완전탐색(Exhaustive Search)은 그냥 모든 방법을 시도해보는 것을 말합니다. 흔히 ‘무식하게 하게 푼다’라는 의미의 Brute-force Search라고도 합니다.

별 것도 아닌 방법 같지만 모든 알고리즘 문제에서 가장 중요한 것은 정확한 답이기 때문에 가장 확실한 방법이고 컴퓨터의 빠른 연산속도를 활용하는 가장 좋은 접근 방법입니다.

그래서 문제를 처음 접하면 반드시 완전탐색으로 풀 수 있는가를 생각해야 합니다. 모든 문제에서 완전탐색으로 답을 내지 못한 문제는 복잡도를 더 이상 줄일 수 없기 때문입니다.

완전탐색 사고연습

예제1. 주어진 N개의 수에서 2번째로 큰 수는 무엇인가?

(단, N >=2)

위 문제를 해결하는 쉬운 방법을 떠올리면 오름차순으로 정렬한 다음 뒤에서 2번째 수를 뽑으면 됩니다. 정렬이 어렵다하시는 분들은 그냥 N개의 수를 전부 확인한 다음 가장 큰수를 삭제하고, 다시 한번 N-1개의 수를 확인해서 제일 큰 수를 찾으면 됩니다.

조금 더 복잡한 문제를 한번 볼까요?

위 그림과 같이 두 가지 케이스를 보시면서 어떻게 모든 경우에 대해 구할 수 있을 지 생각해보세요.

완전탐색 접근:

부분집합의 합이 0인 것을 찾는 것이므로 모든 부분집합을 구해서 합을 계산해보면 됩니다. 즉 숫자가 1개로 이루어진 부분집합, 2개로 이루어진 부분집합 등을 구해서 부분집합마다 합을 구해 0이 있는지만 확인하면 이 문제를 해결할 수 있습니다.

하지만 막상 코드로 구현하려면 마냥 쉽지는 않지만 자주 등장하는 유형들을 한번씩 구현해보시면 많은 문제가 풀릴 것입니다.

자주 등장하는 탐색 유형

문제마다 모든 경우를 탐색하는 방법은 제각각이지만 자주 등장하는 유형들이 있습니다.

위 그림처럼 크게 3가지 방법으로 나눠볼 수 있습니다. 순열, 조합, 중복순열에 대해 모든 케이스를 생성해낼 수 있으면 각각의 예제를 모두 푸실 수 있습니다.

조합을 이용하면 위에서 예제로 설명한 부분집합 문제를 풀 수 있고 순열은 유명한 외판원문제(TSP)를, 중복순열은 중복을 허용하는 냅색문제(Knapsack) 등을 풀 수 있습니다. 물론 N이 작은 경우에 한해서만요. 최적화는 그 이후의 문제입니다.

연습문제

문제 링크:: 부분수열의 합(https://www.acmicpc.net/problem/1182)

자세한 문제 설명은 위 링크로 들어가셔서 확인하시고 직접 풀어보세요!

N개의 수를 합한 결과가 S인 부분집합이 몇개인지 찾는 문제입니다. 특별한 방법을 찾으려 하지 말고 완전탐색의 방법을 접근해서 직접 구현해보시길 바랍니다.

풀이

이 문제는 N개의 수의 부분집합을 모두 만들어서 부분집합의 합이 S인 케이스가 몇 개인지 카운트하면 되는 문제입니다. 모든 부분집합을 만드는 것을 구현하실 수 있으면 쉽게 푸실 수 있습니다.

조합 문제로 N개에서 1개씩만 선택한 경우, N개에서 2개씩만 선택한 경우 등으로 구현해도 되고, 모든 부분집합을 만드는 방법을 구현해도 됩니다. 저는 후자로 구현했습니다.

집합의 크기가 N 인 경우 모든 부분집합의 개수는 2^N 이므로, 시간복잡도는 O(2^N) 입니다. 제약조건이 N은 20이하 이므로 문제없습니다.

전체 코드:

#include <stdio.h>

int N, S;
int arr[20];
int cnt;

void F(int sum, int depth)
{
	if (N == depth)
	{
		if (sum == S) cnt++;
		return;
	}

	// depth번째 값을 사용하지 않는 경우
	F(sum, depth + 1);
	// 사용하는 경우
	F(sum + arr[depth], depth + 1);
}

int main()
{
	scanf("%d%d", &N, &S);
	for (int i = 0; i < N; i++)
		scanf("%d", &arr[i]);

	cnt = 0;
	F(0, 0);

	// 부분집합의 합이 0인 경우, 공집합 제외
	if (S == 0) cnt--;

	printf("%d\n", cnt);

	return 0;
}

위 코드처럼 재귀를 이용하면 모든 부분집합을 쉽게 만들 수 있습니다.

Bit를 이용하면 하나의 숫자를 집합으로 사용할 수 있습니다. ‘숫자의 1번째 Bit가 켜져 있으면 1번째 수를 사용한다.’ 라는 식으로 표현하게 되면 1부터 2^N-1까지 숫자가 모든 부분집합을 의미하기 때문에 Bit가 켜진 것만 Sum하면 이 문제도 풀 수 있습니다.

다른 연습문제 추천

모든 순열: (https://www.acmicpc.net/problem/10974)
연산자 끼워넣기: (https://www.acmicpc.net/problem/14888)
감시: (https://www.acmicpc.net/problem/15683)

모든 경우를 탐색하는 방법이 가장 정확한 방법이니 특별한 알고리즘을 찾으려 하지말고 컴퓨터를 활용하려는 사고 연습이 중요합니다. 이러한 완전탐색 문제는 몇가지 종류를 풀다보면 구현도 금방 익숙해지실 겁니다.