brute force

brute force

    '무식하게 푼다(brute-force)'는 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 말합니다.

이렇게 가능한 방법을 전부 만들어 보는 알고리즘들을 가리켜 흔히 완전 탐색(exhaustive search)라고 부릅니다. 

 

+ 

프로그래밍 대회에서 대부분의 사람들이 가장 많이 하는 실수는 쉬운 문제를 어렵게 푸는 것입니다. 

문제를 마주하면 가장 먼저 무식하게 풀 수 있는 지 생각 해보는 것도 좋은 방법입니다. 

 

재귀호출과 완전 탐색

재귀 호출 (recursion)

    재귀함수 (recursive funciton): 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼객 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수입니다. 

 

다음은 재귀 호출의 기초적인 성질을 이해하기 위해 가장 간단한 반복문을 재귀 함수로 구현한 것입니다. 

// 필수 조건 n >= 1
// 결과: 1부터 n까지의 합을 반환한다.
int sum(int n) {
    int ret = 0;
    for (int i = 1; i <= n; ++i) {
        ret += i;
    }
    return ret;
}

// 필수 조건 n >= 1
// 결과: 1부터 n까지의 합을 반환한다.
int recursiveSum(int n) {
    if (n == 1) {
        return 1; //더이상 쪼개지지 않을 때,
    }
    return n + recursiveSum(n - 1);
}

 

• recursiveSum의 if문처럼 쪼개지지 않은 최소한의 작업에 도달했을 때 답을 반환하는 조건문을 추가해야 합니다. 
• 이때, 쪼개지지 않는 가장 작은 작업들을 가리켜 재귀 호출의 기저사례(base case)라고 합니다. 
• 재귀 호출은 기존에 반복문을 사용해 작성하는 코드를 다르게 짤 수 있는 방법을 제공해 줍니다. 
• 문제의 특성에 따라 재귀 호출은 코딩을 훨씬 간편하게 해 줄 수 있는 무기가 됩니다. 

 

예제: 중첩 반복문 대체하기

•  0부터 차례대로 번호 매겨진 n개의 원소 중 네 개를 고르는 모든 경우를 출력하는 코드
•  n == 7이라면, (0.1.2.3, (0,1,2,4), (0,1,2,5), ..., (3,4,5,6)의 모든 경우 출력한다. 

#include <iostream>
using namespace std;

// 0부터 차례대로 번호 매겨진 n개의 원소 중 네 개를 고르는 모든 경우를 출력하는 코드
// n == 7이라면, (0.1.2.3, (0,1,2,4), (0,1,2,5), ..., (3,4,5,6)의 모든 경우 출력

int main(void)
{
    int n = 7;
    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;
                }
            }
        }
    }
    return 0;
}

 

• 위의 코드 조각이 하는 작업은 네 개의 조각으로 나눌 수 있습니다. 각 조각에서 하나의 원소를 고른 후, 남은 숸소들을 고르는 작업을 자기 자신을 호출해 떠넘기는 재귀 함수를 작성합니다. 
• 이때 남은 원소들을 고르는 작업을 다음과 같은 입력들의 집합으로 정의할 수 있습니다. 
• 원소들의 총 개수, 더 골라야 할 원소들의 개수, 지금까지 고른 원소들의 번호
• 아래의 코드는 이 작업을 하는 재귀 함수를 보여줍니다. 

#include <iostream>
#include <vector>

using namespace std;

void printPicked(vector<int> &picked);
// 0부터 차례대로 번호 매겨진 n개의 원소 중 네 개를 고르는 모든 경우를 출력하는 코드
// n == 7이라면, (0.1.2.3, (0,1,2,4), (0,1,2,5), ..., (3,4,5,6)의 모든 경우 출력

// n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘
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();
    }
}

void printPicked(vector<int> &picked) {
    for(vector<int>::iterator iter = picked.begin(); iter != picked.end(); iter++) {
        cout<<*iter<<" ";
    }
    cout<<endl;
}

int main()
{
    vector<int> a;
    int n = 6;
    int toPick = 3;
    pick(n, a, toPick);


	return 0;
}

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

 

 

 

예제: 보글게임