알고리즘 : 완전 탐색 #1 (Brute-Force, 순열, 재귀)

완전탐색(Exhaustive search)이란, 어떤 문제를 해결하기 위해 모든 경우의 수를 시도하며 정답을 찾아가는 방법입니다.

완전탐색은 일반적으로 모든 문제를 해결할 수 있지만,

아무리 컴퓨터의 성능이 뒷받침 한다 하여도 그 시간이 천문학적으로 걸릴 수 있습니다.

 

완전탐색 알고리즘으로는 다음의 다섯 가지가 쓰입니다.

1. Brute-Force : 노가다
2. 순열(Permutation)
3. 재귀(Recursive)
4. 비트마스크(Bitmask)
5. 그래프 탐색(Graph Traversal) : BFS, DFS

---

Brute-Force

---

Brute-Force 기법은 for, while, if ... 등의 반복문, 조건문을 활용하여, 가능한 모든 방법을 단순히 찾는 기법입니다. 

예를 들어 숫자로만 이루어진 3자리 비밀번호를 찾기 위해 000~999 노가다를 하는 것이 이 경우입니다.

---

순열

---

주머니에 [1, 2, 3]의 공이 있을 때, 공을 하나씩 꺼낸다고 합시다.

공을 꺼내는 순서를 고려하면 다음과 같은 경우의 수가 생기게 되죠.

 

[1, 2, 3]

[1, 3, 2]

[2, 1, 3]

[2, 3, 1]

[3, 1, 2]

[3, 2, 1]

 

총 경우의 수는 6가지로, 이는 3! = 3 * 2 * 1 과 동일한 값입니다.

이 때 공이 n개 일 때에는 n! 개의 경우의 수가 등장합니다.

백준 10974번은 순열을 활용하는 문제로, 입력한 N에 따라 [1, 2, ..., N]의 순열을 출력하는 문항입니다.

---

재귀

---

재귀 함수란 자기 자신을 호출하는 함수로,

기본적인 재귀 함수의 상세한 구동 방식은 해당 링크에서 보실 수 있습니다.

 

재귀 호출을 제한 조건 없이 계속해서 호출한다면, 무한으로 반복될 수 있습니다.

아래의 코드는 n에 어떤 수를 넣든 재귀호출로 fact(-∞) 까지 계속 불러옵니다.

int fact(int n) {
	return fact(n-1)*n;
}

따라서 조건문을 넣어 해당 조건에서 재귀호출을 탈출하는 종료 조건(Base case)이 필요합니다.

int fact(int n) {
	if(n==0) 
		return 1;
	else 
		return fact(n-1)*n;
}

 

그렇다면 이러한 재귀 호출이 완전탐색에 어떻게 쓰이게 될까요?

주로 중복 없이 n개 중 p개를 고르는 상황에서 쓰입니다.

우선 0~9의 수 중 중복 없이 3개를 고르는 코드 정도는 for 반복문만을 이용하여 작성할 수 있습니다.

for (int i = 0; i < 10; i++)
	for (int j = i + 1; j < 10; j++)
		for (int k = j + 1; k < 10; k++)
			cout << "[" << i << ", " << j << ", " << k << "]" << endl;

3개의 수를 고르기 위하여, 3개의 for 문을 중첩시켰습니다.

실행 결과로는 [0, 1, 2] 부터 [7, 8, 9] 까지, 0~9 에서 중복 없이 3개의 수를 고르는 경우가 모두 출력됩니다.

 

그런데 이 때, p가 많아진다면 for 문의 갯수가 p의 갯수만큼 늘어날 것입니다.

만약 10000개의 수 중 1000개를 뽑는 경우의 수를 출력하고 싶다면, 천 개의 for 문을 중첩시킨다는 거죠 🤯

 

재귀 호출로 고쳐 작성한다면 다음과 같습니다.

#include <iostream>
#include <vector>
using namespace std;

void combinations(vector<int>& nums, vector<int>& current, int index, int p) {
    if (current.size() == p) { // 선택된 조합의 크기가 p와 같다
        //for (int i = 0; i < current.size(); i++) { // 일반 for 루프
        //    int num = current[i];
        //    cout << num << " ";
        //}
        for (int num : current) { // range-based for 루프
            cout << num << " ";
        }
        cout << endl; // [x, x, x] 출력
        return; // 함수 탈출
    }

    if (index >= nums.size()) // index가 n에 도달
        return; // 함수 탈출

    current.push_back(nums[index]); // current 벡터에 num 추가
    combinations(nums, current, index + 1, p); // 재귀 호출

    current.pop_back(); // 추가 전 상태로 되돌리고
    combinations(nums, current, index + 1, p); // 재귀 호출
    // 새로운 조합을 계속 생성 -> 가능한 모든 조합 생성
}

int main() {
    vector<int> nums;
    int n = 10;
    int p = 3;
    for (int i = 0; i < n; i++) { // nums 벡터에 0 ~ (n-1) 채우기
        nums.push_back(i);
    }

    vector<int> current;
    combinations(nums, current, 0, p);

    return 0;
}

0부터 9까지의 수가 담긴 벡터 nums를 생성하고, combinations() 함수를 호출합니다.

combinations()은 nums, current 두 벡터와 index, p를 인자로 받는 함수입니다.

- 이 때 current는 지금 진행되는 재귀함수에서 쓸 조합 ( [0], [0,1], [4,6,7], [2,6,8,9], ⋯ )

- index는 current 벡터에 넣을 num의 원소인 num[index]를 결정,

- p는 기존에 설정한 조합의 크기, 즉 10개 중 3개를 뽑을 때의 3입니다.

 

combinations()가 돌아가는 방식으로는

- current 벡터에 nums의 원소들을 계속 추가하며 index+1을 인자로 받아 재귀호출 하거나

- 추가하지 않은 상태에서 index+1을 인자로 받아 재귀호출하는데,

이 때 current 벡터는 nums으로 만들 수 있는 모든 조합을 생성해낼 수 있습니다.

 

그렇다면 재귀 호출의 탈출 조건은 어떻게 될까요?

- 우선 원소의 갯수가 p일 때 해당 조합을 출력한 뒤 해당 함수를 탈출하고,

- index+1을 계속 하며 재귀호출 하다가 index가 nums의 index를 벗어나면 탈출합니다.

이 함수를 탈출하더라도, 다른 함수는 여전히 재귀호출을 돌고 있는 상태로,

모든 함수가 탈출하면 combinations() 함수가 완전히 끝이 납니다.

---

비트마스크

---

비트마스크는 0 ~ (n-1) 까지의 수에서 모든 부분집합을 찾을 때 유용합니다.

0~7 의 수에서 모든 부분집합의 경우는 [0], [1], ⋯, [0, 1, 2, 3], ⋯, [0, 1, 2, 3, 4, 5, 6, 7] 까지 존재합니다.

n이 커질수록 이 모든 부분집합을 그대로 데이터에 저장하기에는 무리가 있으므로,

비트마스크를 사용하여 어떠한 숫자로 치환하여 저장합니다.

위의 경우에서, 부분집합 [0, 1, 3, 4]는 11011⑵ 로 표현할 수 있고, 십진수인 27로 저장됩니다.

 

다음 글에서 이어집니다.