부루트 포스 (Brute Force)

핵심 요약

브루트 포스(Brute Force)는 가능한 모든 경우를 직접 시도하여 정답을 찾는 알고리즘 전략이다.
한국어로는 보통 완전 탐색이라고도 한다.

가장 단순하지만, 동시에 알고리즘 학습에서 매우 중요한 출발점이다.
왜냐하면 브루트 포스는 문제를 해결하는 가장 기본적인 기준 풀이가 되기 때문이다.

1. 브루트 포스의 정의

브루트 포스는 가능한 후보를 하나씩 모두 검사하는 방식이다.

예를 들어 네 자리 비밀번호를 찾는 문제라면 다음과 같은 방식이다.

가능한 모든 비밀번호를 차례대로 입력해 보고, 맞는 값을 찾으면 멈춘다.

이 방식은 특별한 추론이나 규칙을 사용하지 않는다.
대신 가능한 경우를 빠짐없이 확인한다.

2. 왜 중요한가?

브루트 포스는 단순하지만 알고리즘 학습에서 중요한 이유가 있다.

첫째, 문제의 가장 기본적인 풀이를 제공한다.
어떤 문제를 처음 만났을 때, 가능한 경우를 전부 나열할 수 있는지 생각하면 문제 구조가 보인다.

둘째, 더 효율적인 알고리즘을 만들기 위한 비교 기준이 된다.
브루트 포스로 풀면 시간이 얼마나 걸리는지 계산한 뒤, 그보다 나은 방법을 찾는 식으로 사고를 발전시킬 수 있다.

셋째, 입력 크기가 작다면 브루트 포스가 오히려 가장 좋은 선택일 수 있다.
복잡한 알고리즘을 쓰는 것보다 단순하고 오류가 적기 때문이다.

3. 장점

3.1 구현이 단순하다

브루트 포스는 대체로 반복문만으로 구현할 수 있다.
복잡한 자료구조나 수학적 최적화가 필요하지 않은 경우가 많다.

3.2 정답을 놓치지 않는다

가능한 경우를 모두 확인하므로, 검사 범위 안에 정답이 있다면 반드시 찾을 수 있다.

3.3 문제 구조를 파악하기 좋다

처음에는 비효율적이더라도, 브루트 포스를 생각하면 문제의 입력, 출력, 조건, 후보군이 명확해진다.

4. 단점

4.1 경우의 수가 커지면 느리다

브루트 포스의 가장 큰 단점은 시간이다.
후보가 100개라면 괜찮지만, 1억 개라면 문제가 된다.

4.2 입력 크기에 약하다

입력 크기가 조금만 커져도 가능한 경우의 수가 폭발적으로 증가할 수 있다.
이를 조합 폭발(combinatorial explosion)이라고 한다.

예를 들어 10개의 원소 중 부분집합을 모두 확인하면 경우의 수는 다음과 같다.

2^10 = 1,024

하지만 30개의 원소라면 다음과 같다.

2^30 = 1,073,741,824

원소 수가 조금 늘었을 뿐인데 경우의 수는 급격히 증가한다.

5. 시간 복잡도와 브루트 포스

브루트 포스를 이해하려면 시간 복잡도(time complexity)를 함께 이해해야 한다.

시간 복잡도는 입력 크기가 커질 때 알고리즘의 실행 시간이 어떻게 증가하는지 나타내는 개념이다.

예를 들어 길이가 n인 배열에서 두 수의 합이 특정 값이 되는 쌍을 찾는다고 하자.

가장 단순한 브루트 포스는 모든 쌍을 확인한다.

첫 번째 원소와 두 번째 원소
첫 번째 원소와 세 번째 원소
...
두 번째 원소와 세 번째 원소
...

이 경우 대략 n × n번 비교하므로 시간 복잡도는 다음과 같다.

O(n^2)

입력 크기 n이 커질수록 실행 시간이 제곱으로 증가한다.

6. 브루트 포스가 적합한 경우

브루트 포스는 항상 나쁜 방법이 아니다.
다음 경우에는 충분히 좋은 전략이 될 수 있다.

6.1 입력 크기가 작을 때

경우의 수가 작다면 브루트 포스는 가장 간단하고 안정적인 방법이다.

6.2 정답 후보를 모두 확인해야 할 때

문제 자체가 모든 경우를 검사해야 하는 구조라면 브루트 포스가 자연스럽다.

6.3 더 나은 알고리즘을 찾기 전 기준 풀이가 필요할 때

먼저 브루트 포스로 문제를 푼 뒤, 시간 초과가 난다면 그때 최적화를 고민할 수 있다.

6.4 테스트용 정답 생성이 필요할 때

효율적인 알고리즘을 만들었을 때, 작은 입력에 대해 브루트 포스 결과와 비교하면 오류를 찾기 쉽다.

7. 브루트 포스와 완전 탐색

브루트 포스와 완전 탐색은 거의 같은 의미로 사용된다.
다만 뉘앙스에는 약간 차이가 있다.

용어	의미
브루트 포스	가능한 경우를 무식하게 모두 시도한다는 표현
완전 탐색	가능한 해 공간을 빠짐없이 탐색한다는 알고리즘적 표현

브루트 포스는 다소 직관적이고 비공식적인 표현이고, 완전 탐색은 알고리즘 문제 풀이에서 더 정돈된 표현이다.

8. 브루트 포스와 백트래킹의 차이

브루트 포스와 함께 자주 등장하는 개념이 백트래킹(backtracking)이다.

백트래킹은 모든 경우를 탐색한다는 점에서 브루트 포스와 닮았지만, 불가능한 경우를 중간에 버린다는 점이 다르다.

예를 들어 조건을 만족하지 않는 경로가 확인되면 더 깊이 탐색하지 않고 되돌아간다.

이를 가지치기(pruning)라고 한다.

브루트 포스: 모든 경우를 끝까지 확인
백트래킹: 가능성이 없는 경우는 중간에 중단

따라서 백트래킹은 브루트 포스보다 더 효율적인 완전 탐색 기법으로 볼 수 있다.

9. 브루트 포스와 그리디의 차이

그리디 알고리즘(greedy algorithm)은 매 순간 가장 좋아 보이는 선택을 하는 방식이다.

브루트 포스는 모든 선택지를 확인하지만, 그리디는 하나의 선택지를 빠르게 고른다.

구분	브루트 포스	그리디
방식	모든 경우 확인	현재 최선 선택
장점	정답 보장 가능	빠름
단점	느릴 수 있음	항상 최적해를 보장하지 않음
핵심 질문	모두 해볼 수 있는가?	지금 최선이 전체 최선인가?

10. 브루트 포스와 동적 계획법의 차이

동적 계획법(dynamic programming, DP)은 중복되는 계산을 저장해서 반복 계산을 줄이는 방식이다.

브루트 포스가 같은 계산을 여러 번 반복한다면, DP는 한 번 계산한 결과를 저장해 다시 사용한다.

예를 들어 피보나치 수열을 단순 재귀로 계산하면 같은 값을 여러 번 계산하게 된다.
이때 DP를 사용하면 계산 결과를 저장하여 시간을 크게 줄일 수 있다.

브루트 포스: 가능한 계산을 그대로 반복
DP: 중복 계산을 저장해 재사용

11. 학습할 때 자주 나오는 문제 유형

브루트 포스는 다음 문제 유형에서 자주 등장한다.

11.1 모든 조합 확인

예: 여러 숫자 중 3개를 골라 합이 특정 값에 가장 가까운 경우 찾기

11.2 모든 순열 확인

예: 도시를 방문하는 모든 순서를 확인해 최소 비용 찾기

11.3 문자열 탐색

예: 문자열 안에서 특정 패턴이 등장하는 위치를 모두 확인하기

11.4 격자 탐색

예: 체스판, 미로, 좌표 평면에서 가능한 위치를 모두 검사하기

11.5 시뮬레이션

예: 문제에서 주어진 규칙을 그대로 구현해 모든 상황을 확인하기

12. 브루트 포스를 사용할 때의 사고 순서

브루트 포스를 적용할 때는 다음 순서로 생각하면 좋다.

12.1 가능한 후보는 무엇인가?

먼저 정답이 될 수 있는 후보의 범위를 정한다.

예를 들어 비밀번호 문제라면 후보는 0000부터 9999까지다.

12.2 후보의 개수는 몇 개인가?

후보가 너무 많으면 브루트 포스가 불가능할 수 있다.
따라서 경우의 수를 먼저 계산해야 한다.

12.3 각 후보를 검사하는 데 얼마나 걸리는가?

후보 하나를 확인하는 비용도 중요하다.

전체 시간은 대략 다음과 같이 계산할 수 있다.

전체 시간 = 후보 개수 × 후보 하나를 검사하는 시간

12.4 시간 제한 안에 가능한가?

알고리즘 문제에서는 시간 제한이 중요하다.
가능한 연산 횟수를 대략 계산해 보고, 브루트 포스로 통과 가능한지 판단해야 한다.

12.5 줄일 수 있는 경우는 없는가?

모든 경우를 확인해야 하더라도, 명백히 불가능한 후보를 미리 제거할 수 있다면 효율이 좋아진다.
이 단계에서 가지치기, 정렬, 조건 필터링 등을 고려한다.

13. 간단한 예시: 두 수의 합

문제: 배열에서 두 수를 골라 합이 10이 되는 쌍을 찾는다.

배열:

[1, 3, 4, 6, 7, 9]

브루트 포스 방식은 모든 쌍을 확인한다.

1 + 3
1 + 4
1 + 6
1 + 7
1 + 9
3 + 4
3 + 6
...

이 중 1 + 9, 3 + 7, 4 + 6이 조건을 만족한다.

이 방법은 단순하지만, 배열의 길이가 커지면 비교 횟수가 빠르게 늘어난다.

14. 브루트 포스 학습에서 중요한 감각

브루트 포스를 배울 때 핵심은 단순히 “모두 시도한다”가 아니다.
더 중요한 것은 다음 감각이다.

이 문제의 모든 경우는 무엇인가?
그 경우의 수는 얼마나 되는가?
모두 시도해도 시간 안에 가능한가?
불필요한 경우를 줄일 수 있는가?

이 질문들이 알고리즘 사고의 출발점이다.

브루트 포스를 제대로 이해하면, 이후 백트래킹, 그리디, 동적 계획법, 분할 정복 같은 알고리즘 전략을 배울 때 기준점이 생긴다.

15. 오해하기 쉬운 점

15.1 브루트 포스는 항상 나쁜 방법이다?

아니다.
입력 크기가 작으면 브루트 포스가 가장 명확하고 안전한 방법일 수 있다.

15.2 브루트 포스는 알고리즘이 아니다?

아니다.
브루트 포스도 명확한 알고리즘 전략이다.
다만 효율성이 낮을 수 있을 뿐이다.

15.3 무조건 최적화해야 한다?

아니다.
문제의 입력 크기와 시간 제한을 보고 판단해야 한다.
불필요하게 복잡한 알고리즘을 쓰면 오히려 구현 오류가 늘어날 수 있다.

16. 다음 단계로 학습할 개념

브루트 포스를 이해한 뒤에는 다음 개념을 학습하면 좋다.

16.1 시간 복잡도

브루트 포스가 가능한지 판단하려면 시간 복잡도를 알아야 한다.

16.2 완전 탐색

가능한 모든 경우를 체계적으로 탐색하는 방법을 배운다.

16.3 재귀

순열, 조합, 부분집합 탐색은 재귀와 함께 자주 등장한다.

16.4 백트래킹

불가능한 경우를 중간에 제거하는 방식이다.

16.5 가지치기

탐색 공간을 줄이는 핵심 기법이다.

16.6 동적 계획법

브루트 포스에서 발생하는 중복 계산을 줄이는 방법이다.

17. 최종 정리

브루트 포스는 가능한 모든 경우를 검사하는 가장 단순한 알고리즘 전략이다.
느릴 수 있지만, 정답을 놓치지 않고 구현이 쉽다는 장점이 있다.

더 중요한 점은 브루트 포스가 알고리즘 사고의 출발점이라는 것이다.
처음에는 모든 경우를 생각하고, 그다음 경우의 수를 계산하고, 마지막으로 줄일 수 있는 부분을 찾는다.

즉 브루트 포스는 단순히 무식한 방법이 아니라, 더 정교한 알고리즘으로 나아가기 위한 기본형이다.