[알고리즘] 부루트포스 (1)

Dandyoung·2023년 11월 23일

부르트포스(Brute Force)

  • 부르트포스는 모든 경우의 수를 다 해보는 것이다.
  • 예를들어, 비밀번호가 4자리이고 숫자로만 이루어져 있다고 한다면,
  • 0000 ~ 9999까지 다 입력해보면 된다.
  • 경우의 수는 총 10,000가지이다.

이때, 경우의 수를 다 해보는데까지 걸리는 시간이 문제의 시간제한을 넘지 않아야 한다.

부르트포스 단계

  1. 문제의 가능한 경우의 수를 계산해본다.
  2. 가능한 모든 방법을 다 만들어본다.
  3. 각각의 방법을 이용해 답을 구해본다.

1. 가능한 모든 경우의 수

  • 직접 계산을 통해 구한다. 대부분 손으로 계산해볼 수 있다.

2. 가능한 모든 방법

  • 하나도 빠짐없이 만들어야 한다.
  • 대표적으로 그냥 다 해보는 방법, for문 사용, 순열 사용, 재귀호출 사용, 비트마스크 사용이 있다.

3. 각각의 방법을 이용해 답을 구한다.

  • 이 단계는 어렵지 않다. 문제에 나와있는 대로 답을 계산해본다.

부루트 포스 문제의 시간 복잡도는 대부분 O(경우의 수 * 방법 1개를 시도해보는 데 걸리는 시간 복잡도)가 걸린다.

실습) 그냥 다 해보기

https://www.acmicpc.net/problem/2309

아홉명의 난쟁이 중 일곱명의 난쟁이를 찾는 문제이다.
아홉명 중 일곱명을 고르는것은, 아홉명 중 두명을 고르는 것과 같다!

  • 난쟁이의 수를 N이라고 했을 때,
  • 두 명을 고르는 경우의 수는 N2N^2이라 할 수 있다.

9C2=9C2 = 9∗82∗1\frac{9 * 8}{2*1} =36= 36가지

NC2=NC2 = N∗(N−1)2∗1\frac{N *(N-1)}{2*1} =O(N2)= O(N^2)

그럼, 나머지 난쟁이의 키의 합을 고르는 시간 복잡도는 O(N2)O(N^2)이다.

따라서, 이 문제는 O(N3)O(N^3)으로 해결할 수 있다.

소스코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    vector<int> v;
    // 총 숫자 합.
    int sum = 0;
    for(int i = 0; i < 9; i++){
        int a;
        cin >> a;
        sum += a;
        v.push_back(a); 
    }
    // 오름차순으로 정렬
    sort(v.begin(), v.end());

    // 2중 for문 설계. 
    for(int i = 0; i < v.size() -1; i++){
        for(int j = i + 1; j < v.size(); j++){
            // 두 수를 뻇는데 100이 된다면, v[i]와 v[j] 는 빠져야할 숫자. 
            if(sum - (v[i] + v[j]) == 100){
                // v[i]와 v[j]를 제외하고 싹다 출력.
                for(int k = 0; k < v.size(); k++){
                    if(k != i && k != j){
                        cout << v[k] << endl;
                    }
                }
                // 프로그램 종료.
                return 0;
            }
        }
    }
    return 0;
}
  • '일곱 난쟁이를 찾을 수 없는 경우는 없다.'라고 했기 때문에,
  • 합이 100인 경우가 무조건 존재한다.
  • 또, 문제에서 '가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.'라고 했기 때문에,
  • 최초로 등장한 한번의 경우만 출력하면 된다.

조금 실수가 있었던 부분이 있는데, 출력 후에, return 0;를 호출해 프로그램을 종료하는 부분이다.

return 0;를 추가하지 않아서 2번의 실패가 있었다..
만약 return 0;를 추가하지 않으면, 프로그램이 모든 경우를 확인한 후에도 계속 실행되는데 이유가 있었던 것 같다. (그런데, 문제를 읽어보면 그대로 실행되도 큰 문제 없지 않나,,?)

profile
코딩이어려운당신에게,,

0개의 댓글