12. 브루트 포스

브루트 포스

빠른 설명

브루트 포스는 가능한 모든 경우를 직접 확인하는 방법이다. 경우의 수가 작거나 제한이 작을 때 가장 확실하다.

언제 쓰는가

• $N$이 작을 때
• 모든 조합, 순열, 부분집합을 확인해야 할 때
• 먼저 완전탐색으로 기준 답을 만든 뒤 최적화를 생각할 때

시간복잡도

• 이중 반복문: $O(N^2)$
• 부분집합 전체 탐색: $O(2^N)$
• 순열 전체 탐색: $O(N!)$

참고자료

• Wikipedia - Brute-force search
• USACO Guide - Complete Search
• GeeksforGeeks - Brute Force Approach

C++ 코드

#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
int main() {
    vector<int> a = {2, 7, 11, 15};
    int target = 9;
 
    for (int i = 0; i < (int)a.size(); i++) {
        for (int j = i + 1; j < (int)a.size(); j++) {
            if (a[i] + a[j] == target) {
                cout << i << ' ' << j << '\n';
            }
        }
    }
}

Python 코드

a = [2, 7, 11, 15]
target = 9
 
for i in range(len(a)):
    for j in range(i + 1, len(a)):
        if a[i] + a[j] == target:
            print(i, j)