무식하게 풀기(Brute Force)

이 문서는 책 "알고리즘 문제 해결 전략"을 토대로 만들어졌습니다.

Contents

1. 무식하게 풀기란?
2. 예제 1 - N까지의 합
3. 예제 2 - N개 중 R개 고르기
4. 결론

무식하게 풀기란?

"Computer Science 정복하기" 두 번째 프로젝트 알고리즘의 첫 번째 장 "무식하게 풀기"입니다. 무식하게 푸는 것은 알고리즘 설계의 가장 기초로써, 컴퓨터의 빠른 성능을 이용하여 가능한 경우의 수를 모두 탐색하는 방법입니다.

 

흔히들 "Brute Force" 혹은 "완전 탐색 알고리즘"이라고 부르는 이 알고리즘 패러다임에 대해서 몇 개의 예제를 통해서 공부해보도록 하겠습니다. 참고적으로 이 알고리즘 패러다임은 문제를 반복되는 작은 조각으로 나누는 것입니다. 이를 위해서 재귀 호출을 이용한 반복문을 주로 이용합니다. 재귀에 대한 설명은 다음 문서를 참고하세요.

 

재귀 문서

gurumee92/datastructure

 

예제 1 - N까지의 합

먼저 1부터 N까지의 합을 구하는 프로그램을 만들어봅시다. 제일 간단한 방법은 for문을 통해서 1부터 N까지 순회하여 합을 구하는 방법입니다.

 

int sum(int N) {
    int result = 0;

    for (int i=1; i<=N; i++){
        result += i;
    }

    return result;
}

 

이제 재귀 호출 방식을 통해서 1~N까지 순회하여 그 값들의 합을 구해봅시다. 먼저 재귀는 크게 2가지 부분으로 나뉘는데, 다음과 같습니다.

 

1. 재귀 탈출부
2. 재귀 호출부

재귀 탈출에 대해 잘 설정해주어야 합니다. 이를테면, 위의 반복문처럼 1부터 시작해서 N일 때까지 크기를 늘려서 합을 구할 수 있습니다. 아래 코드처럼 말이죠.

 

int sum(int N, int i) {
    if (N == i){
        return N;
    }

    return i + sum(N, i+1);
}

 

위의 코드는 입력 i가 1에서 N까지 커지고 있습니다. 실제로 우리한테 중요한 것은 N인데 말이죠. "무식하게 풀기"라고 해서 진짜 무식하게 풀면 안됩니다. 우리는 똑똑하게 모든 경우의 수를 돌아야 합니다. 개인적인 생각으로, 보통 알고리즘을 풀때는 입력의 개수가 작을 수록, 입력의 크기가 작을 수록 문제를 풀기가 용이합니다.

 

그래서 재귀를 쓰더라도 입력이 커지는 방향보다는 작아지는 방향을 선택하는 것이 좋습니다. 아래 코드를 살펴보십시오.

 

int sum(int N) {
    if (N == 1){
        return 1;
    }

    return N + sum(N-1);
}

 

N에서 1로 차차 입력을 줄이기만했을 뿐인데, 입력의 개수조차 줄었습니다. 맞습니다. i는 필요하지 않습니다. 우리한테 중요한 것은 N이니까요. 오히려 이런 쪽이 코드도 보기 쉽고 나중에 최적화를 쓸때, 더 재활용이 쉬워집니다.

예제 2 - N개 중 R개 고르기

이번 예제는 왜 반복문보다 재귀 호출문을 써야 하는지에 대한 답을 줄 수 있을 것 같습니다. 이번 예제는 0부터 순서대로 번호가 매겨진 N개의 원소 중 R개를 고르는 문제입니다. 즉, n = 7, r = 3이라면 다음의 경우의 수가 나타납니다.

 

n=7, r=3
(0, 1, 2), (0, 1, 3), (0, 1, 4), (0, 1, 5), (0, 1, 6), (0, 2, 3), (0, 2, 4), (0, 2, 5),  (0, 2, 6),
(0, 3, 4), (0, 3, 5), (0, 3, 6), (0, 4, 5), (0, 4, 6), (0, 5, 6), (1, 2, 3),  (1, 2, 4), (1, 2, 5),
(1, 2, 6), (1, 3, 4), (1, 3, 5), (1, 3, 6), (1, 4, 5), (1, 4, 6),  (1, 5, 6), (2, 3, 4), (2, 3, 5),
(2, 3, 6), (2, 4, 5), (2, 4, 6), (2, 5, 6), (3, 4, 5), (3, 4, 6), (3, 5, 6), (4, 5, 6)

 

어떻게 해결할 수 있을까요? 이 문제는 3중 반복문을 돌면 쉽게 해결할 수 있습니다. 아래 코드처럼 말이죠.

 

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

 

그런데, r이 하나 늘어 4개일 때는요? 5개일 때는요? r개가 늘수록 내부 반복문 개수가 그에 맞춰 늘어야 합니다. 문제에서 n, r은 변하는 수입니다. 그렇다는 것은 단순 for문을 이용한 반복문으론 이 문제를 해결하기가 매우 어렵다는 것을 의미합니다. 이제 재귀 호출문을 이용해서 이를 해결하는 코드를 살펴볼까요?

 

다음은 이를 해결하기 위한 전체 코드입니다.

 

#include <iostream>
#include <vector>

using namespace std;
//단순 벡터를 출력하는 함수입니다. 넘어가주세요.
void printPicked(const vector<int> & v) {
    for (const auto & i : v) {
        cout << i << " ";
    }
    cout << endl;
}

//이 함수가 실제적으로 문제를 해결하는 함수입니다.
void pick(vector<int> & picked, int n, int r) {
    //만약 r == 0, 즉, 모든 원소를 고른 경우입니다.
    //이 경우 선택한 원소를 출력한 후, 재귀를 탈출합니다.
    if (r == 0) {
        printPicked(picked);
        return;
    }
    //현재 고를 수 있는 가장 작은 수를 계산합니다.
    int small = picked.empty() ? 0 : picked.back() + 1;
    //이 단계에서 원소를 하나 고르는 것입니다.
    for (int next = small; next < n; next++) {
        picked.push_back(next);
        pick(picked, n, r-1);
        picked.pop_back();
    }
}
//메인 함수입니다. 초기 상황을 위해서, 빈 벡터를 넣어줍니다.
int main () {
    int n = 7, r = 4;
    vector<int> picked;
    pick(picked, n, r);
    return 0;
}

 

한 번 n=4, r=2의 상황을 직접 그려보세요. 그리고 n=4, r=3의 상황을 그려보세요. 왜 알고리즘을 해결하는데 재귀 호출이 반복문보다 유리한지, 재귀 호출방식이 얼마나 우아한지 충분히 감상하실 수 있을겁니다.

 

결론

우리는 이번 장에서 "무식하게 풀기"라는 알고리즘 패러다임을 배웠습니다. 보통 코딩 시험의 경우, 완전 탐색만으로도 해결하는 경우가 왕왕 있습니다. (네이버, 카카오, 삼성 제외) 또한, 먼저 무식하게 풀어보면, 동적 계획법, 분할 정복 등 다른 알고리즘 패러다임을 통해서 최적화하기도 쉬워집니다.

 

다음은 "무식하게 풀기"를 통해서 풀 수 있는 문제들과 그 풀이에 대한 문서입니다. 한 번 문제들을 풀어보고 제가 어떻게 해결했는가 비교해보세요. 많은 도움이 되실겁니다.

 

보글 게임

알고스팟 문제 풀이 BOGGLE

 

이 문제의 경우 무작정 풀기만으로 해결할 수 없습니다. 때문에 동적 계획법을 통해 알고리즘을 최적화시키는 방법도 포함되어 있습니다.

 

보드판 덮기

알고스팟 문제 풀이 BOARDCOVER

소풍

알고스팟 문제 풀이 PICNIC

시계 맞추기

알고스팟 문제 풀이 CLOCKSYNC