완전탐색 - 중첩 반복문 대체하기

문제와 내용은 "프로그래밍 대회에서 배우는 알고리즘 문제해결 전략" 책을 참고하였습니다.

알고리즘 문제 해결 전략

 

---

 

0번부터 차례대로 번호가 매겨진 n개의 원소 중 네 개를 고르는 모든 경우를 출력하는 코드를 작성해보자. 예를 들어 n = 7이라면 (0, 1, 2, 3), (0, 1, 2, 4), (0, 1, 2, 5), ..., (3, 4, 5, 6)의 모든 경우를 출력하는 것 말이다. 물론 다음과 같은 4중 for문을 써서 이것을 간단하게 할 수 있다.

for (int i = 0; i < n; ++i)
	for (int j = i + 1; j < n; ++j)
		for (int k = j + 1; k < n; ++k)
			for (int l = k + 1; l < n; ++l)
				cout << i << " " << j << " " << k << " " << l << endl;

만약 5개를 골라야 한다면 5중 for문을 쓰면 된다. 6개면 6중, 7개면 7중 for문이 될것이다. 위와 같은 중첩 for문은 골라야 할 원소의 수가 늘어날수록 코드가 길고 복잡해지는 데다, 골라야 할 원소의 수가 입력에 따라 달라질 수 있는 경우에는 사용할 수 없다는 문제가 있다. 재귀 호출은 이런 경우에 단순한 반복문보다 간결하고 유연한 코드를 작성할 수 있도록 도와준다.

 

위 코드 조각이 하는 작업은 네 개의 조각으로 나눌 수 있다. 각 조각에서 하나의 원소를 고르는 것이다. 이렇게 원소를 고른 뒤, 남은 원소들을 고르는 작업을 자기 자신을 호출해 떠넘기는 재귀 함수를 작성한다. 이때 남은 원소들을 고르는 '작업'을 다음과 같은 입력들의 집합으로 정의할 수 있다.

 

• 원소들의 총 개수

• 더 골라야 할 원소들의 개수

• 지금까지 고른 원소들의 번호

// n : 전체 원소의 수
// picked : 지금까지 고른 원소들의 번호
// toPick : 더 고를 원소의 수
// 일 때, 앞으로 toPick개의 원소를 고르는 모든 방법을 출력한다.
void pick(int n, vector<int>& picked, int toPick)
{
	// 기저 사례 : 더 고를 원소가 없을 떄 고른 원소들을 출력한다.
	if (toPick == 0) { printPicked(picked); return; }
	// 고를 수 있는 가장 작은 번호를 계산한다.
	int smallest = picked.empty() ? 0 : picked.back() + 1;
	// 이 단계에서 원소 하나를 고른다.
	for (int next = smallest; next < n; ++next)
	{
		picked.push_back(next);
		pick(n, picked, toPick - 1);
		picked.pop_back();
	}
}

이 코드는 실질적으로 앞의 코드 조각에서 for문 하나만을 별도의 함수로 떼낸 것과 다르지 않다. 이 코드는 텅 빈 답에서 시작해서 매 단계마다 하나의 원소를 추가하는 일을 반복하다가, 하나의 답을 만든 뒤에는 이전으로 돌아가 다른 원소를 추가하는 식으로 모든 답을 생성한다. 이 방법은 중첩 for문과 다르게 n개의 원소 중 몇 개를 고르든지 사용할 수 있다는 장점이 있다.

 

이와 같이 재귀 호출을 이용하면 특정 조건을 만족하는 코드를 쉽게 작성할 수 있다. 때문에 재귀 호출은 완전 탐색을 구현할 때 아주 유용한 도구이다.