브루트 포스 알고리즘을 처음 만났을 때가 생각난다.
지금까지 배웠던 바에 의하면 프로그램은 항상 최적의 길을 찾아서 움직여야한다.
그렇기에 어떻게 하면 조금이라도 연산을 덜 할수 있는지 고민해왔다.
조금이라도 시간복잡도, 공간복잡도를 낮추기 위해 효율적인 프로그램을 만들어야하는데
갈 수 있는 모든 케이스를 점검한다는 브루트 포스는 충격이었다.
그런데 공부해 보니 그럴만 했다.
할 수 있을 땐 해야한다. 컴퓨터는 우리 생각보다 계산을 잘했고, 그러는 게 훨씬 효율적이었다.
자 본론으로 들어가서 브루트 포스(brute-force)는
brute의 뜻에서 볼 수 있듯이 야만적으로 할 수 있는 모든 걸 무차별 대입하는 방법이다.
사실 생각해보면 이 방법은 무조건 답을 찾아내는 방법으로 우리가 일상에서나 어디서나 처음으로 사용해본 알고리즘이 아닐까 싶다.
예시를 가지고 한 번 알아보자.
boj 2798 블랙잭
이 문제에서는 N(3<=N<=100)개의 카드 중에 M(10 ≤ M ≤ 300000)을 넘지 않으면서 M에 가장 가까운 세장의 카드를 뽑아내는 문제이다.
세장을 뽑아야하니 총 세번의 반복문을 돌아야한다.
그렇다고해서 세번 모두 n까지의 반복을 할 순 없다. 그렇다간 이미 뽑힌 카드를 또 뽑을 위험이 있기 때문이다.
우선 첫 번째 반복문은 0부터 n-3까지만 반복해야한다. 그래야 두 번째와 세 번째 요소를 선택할 수 있다.
두 번째 반복문에서는 for(int j = i+1; j < n-1; j++) j는 i+1부터 n-2까지 반복한다. 이 범위는 첫 번째 카드 이후부터 선택하고 나머지 한번의 탐색을 위해 n-2까지만 탐색한다.
세 번째 반복문 for (int k = j+1 ; k < n; k++) k는 j + 1부터 n - 1까지 반복으로 첫 번째와 두 번째 카드 이후부터 끝까지 선택한다.
int main() {
int n, m;
cin >> n >> m;
vector<int>v(n);
int sum = 0;
int maxs = 0;
for (int i = 0; i < n; i++) {
cin >> v[i];
}
for (int i = 0; i < n-2 ; i++) {
for (int j = i+1 ; j < n-1 ; j++) {
for (int k = j+1 ; k < n; k++) {
sum = v[i] + v[j] + v[k];
if (sum <= m) {
maxs = max(maxs, sum);
}
}
}
}
cout << maxs;
}선택한 세 요소의 합을 sum 변수에 저장하고 그 값을 이용해 m에 가장 근접한 값을 찾아서 출력한다.
사실 브루트 포스 알고리즘의 경우에는 이렇다 할 알고리즘 코드를 보이기도 어렵고 더 길게 설명할 것 까지는 없다고 생각한다. 물론 보안쪽과 같이 브루트 포스의 영역이 좀 더 중요하게 여겨지는 분야에 관심이 있다면 더 공부하는 것을 추천한다.
단순 알고리즘 공부에서는 이정도면 충분한 것 같다.
모든 선택지를 하나씩 대입하며 확인한다는 개념이기 때문에 주어진 조건에 따라 반복문이든 재귀함수든 그대로 만들어주면 된다. 사실 말은 쉬워도 실제로 문제를 보고 고민하고 결과를 도출하기는 결코 쉽지는 않다...
마지막으로 브루트 포스는 조심히 사용해야한다. 가능한 모든 경우를 고려하기 때문에 조건에 따라 시간복잡도가 말도안되게 커질 수 있기 때문이다.
위 블랙잭 문제만 해도 내 코드는 시간복잡도가 O(N^3)으로 N이 커진다면 기하급수적으로 그 복잡도가 커질 수 있다.
주어진 조건을 잘 보고 브루트포스가 적용될 수 있는지 한눈에 알아보는 눈을 키울 필요가 있다.
