브루트포스 알고리즘: 모든 가능성을 탐색하는 직관적인 방법
브루트포스(Brute Force) 알고리즘은 모든 가능한 경우의 수를 일일이 확인하며 문제의 해답을 찾는 가장 직관적인 문제 해결 방식이다. 마치 바늘을 찾기 위해 건초더미를 하나씩 뒤지는 것과 같다고 할 수 있다.
왜 브루트포스를 사용할까?
- 단순하고 직관적이라 알고리즘 설계 및 구현이 쉽다.
- 모든 경우를 탐색하기 때문에 정확한 해답을 찾을 수 있다.
- 경우의 수가 적은 문제에서는 빠르게 해답을 찾을 수 있다.
하지만 브루트포스의 한계도 명확하다.
- 경우의 수가 많아질수록 해결 시간이 기하급수적으로 증가한다.
- 모든 경우의 수를 저장해야 하므로 많은 메모리를 필요로 한다.
- 대규모 문제에는 현실적으로 사용하기 어렵다.
브루트포스 알고리즘은 크게 선형 구조와 비선형 구조로 나눌 수 있다.
- 선형 구조: 배열, 리스트 등 순차적인 자료 구조를 이용하여 문제를 해결한다. 예를 들어, 정렬되지 않은 배열에서 특정 값을 찾는 순차 탐색이 있다.
- 비선형 구조: 트리, 그래프 등 비선형적인 자료 구조를 이용하여 문제를 해결한다. 예를 들어, 모든 가능한 경우의 수를 탐색하는 백트래킹, 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) 등이 있다.
브루트포스 알고리즘을 사용하기 위해서는 문제의 해답이 명확하게 정의되어 있어야 하고, 모든 가능한 해답의 후보군이 유한해야 한다. 일반적으로 문제를 해결하기 위한 모든 가능한 경우의 수를 생성하고, 각 경우의 수가 문제의 조건을 만족하는지 확인한 후, 조건을 만족하는 경우의 수를 해답으로 저장하는 과정을 거친다.
결론적으로 브루트포스 알고리즘은 문제 해결의 기본적인 접근 방식이지만, 모든 문제에 효과적인 것은 아니다. 문제의 규모와 특성에 따라 더 효율적인 알고리즘을 선택해야 한다. 브루트포스 알고리즘은 다른 알고리즘을 설계하고 이해하는 기반이 되며, 복잡한 문제를 해결하기 위한 첫걸음이 될 수 있다.
예시:
- 정렬되지 않은 배열에서 특정 값 찾기: 배열의 모든 요소를 순차적으로 비교하여 값을 찾는다.
- N-Queen 문제: N×N 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 모든 경우의 수를 찾는다.
- 암호 해독: 모든 가능한 암호 조합을 시도하여 원래의 문자열을 복원한다.
주의:
- 브루트포스 알고리즘은 시간과 메모리 측면에서 비효율적일 수 있으므로, 문제의 규모가 클 경우에는 다른 알고리즘을 고려해야 한다.
- 브루트포스 알고리즘은 다른 알고리즘의 기반이 되므로, 알고리즘 설계의 첫 단계로 사용될 수 있다.
실전문제 (백준/#2798/블랙잭)
#include <iostream>
using namespace std;
int main() {
int n, m = 0;
int sum = 0;
int result = 0;
cin >> n >> m;
int arr[n];
for(int i = 0; i < n; i++) {
cin >> arr[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 = arr[i] + arr[j] + arr[k];
if(sum > result && sum <= m) {
result = sum;
}
}
}
}
cout << result;
return 0;
}
문제풀이
문제 분석
- 목표: 주어진 카드 중 3장을 선택하여 합이 M을 넘지 않으면서 M에 가장 가까운 값을 찾는다.
- 입력: 카드의 개수 N, 목표값 M, 각 카드의 숫자
- 출력: 선택한 3장의 카드 합
해결 전략 (브루트포스)
- 모든 경우의 수 탐색: 세 개의 카드를 선택하는 모든 경우의 수를 탐색한다. (3중 for문)
- 합 계산: 선택한 세 개의 카드의 합을 계산한다.
- 조건 확인: 합이 M을 넘지 않으면서, 이전까지 계산한 합 중 가장 M에 가까운 값인지 확인한다.
FE-Engineer