브루트포스와 백트래킹 차이는 완전탐색을 하느냐 마느냐보다, 후보를 끝까지 다 본 뒤 판정하는지, 아니면 중간에 실패를 알고 가지를 자를 수 있는지에 더 가깝습니다.
이번 글에서는 브루트포스를 모든 후보를 다 확인하는 기본선으로, 백트래킹을 부분 해를 검사하며 탐색 공간을 줄이는 전략으로 나눠 설명하겠습니다. 코딩테스트에서 어떤 문제에서 갈리는지까지 함께 보겠습니다.
브루트포스는 무엇이고 백트래킹은 무엇일까
브루트포스는 가능한 후보를 체계적으로 전부 검사하는 방식입니다. 반면 백트래킹은 후보를 만들다가 이미 틀렸다고 판정되는 갈래를 바로 버리는 방식입니다.
- 브루트포스: 완성된 후보를 하나씩 끝까지 확인한다
- 백트래킹: 부분 후보 단계에서 실패를 알면 더 내려가지 않는다
- 공통점: 둘 다 넓게 보면 완전탐색 계열이다
배경 개념이 헷갈린다면 백트래킹이란 무엇인가와 DFS와 백트래킹 차이를 같이 보면 기준이 더 분명해집니다.
브루트포스와 백트래킹 차이를 탐색 트리로 보면
후보를 나무처럼 펼쳐 보면 차이가 더 잘 보입니다. 브루트포스는 보통 리프까지 내려가서 판정하고, 백트래킹은 중간 노드에서 이미 실패가 드러나면 그 아래 서브트리를 통째로 건너뜁니다.
부분합 예시로 보면 어디서 갈릴까
숫자 1, 2, 3, 4 중 일부를 골라 합이 5가 되는 조합을 찾는다고 해 보겠습니다. 브루트포스는 부분집합을 모두 만들어 본 뒤 합이 5인지 검사합니다. 백트래킹은 현재 합이 5를 넘는 순간 더 볼 필요가 없다고 판단하고 바로 return 합니다.
nums = [1, 2, 3, 4]
result = []
for mask in range(1 << len(nums)):
picked = []
total = 0
for i in range(len(nums)):
if mask & (1 << i):
picked.append(nums[i])
total += nums[i]
if total == 5:
result.append(picked)이 코드는 구현이 단순하지만, 이미 합이 너무 커진 후보도 끝까지 만들어 봅니다.
nums = [1, 2, 3, 4]
path = []
result = []
def backtrack(start, total):
if total == 5:
result.append(path[:])
return
if total > 5:
return
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, total + nums[i])
path.pop()
backtrack(0, 0)여기서는 if total > 5: return이 pruning입니다. 이 줄 하나 때문에 탐색 수가 크게 줄 수 있습니다.
언제 브루트포스로 충분하고 언제 백트래킹이 필요할까
- 입력이 작고 경우의 수가 관리 가능하면 브루트포스로 충분할 수 있다
- 부분 해만 보고도 실패를 빨리 판정할 수 있으면 백트래킹이 잘 맞는다
- 구현 단순성이 더 중요하면 브루트포스가 오히려 안전하다
- 순열, 조합, 배치, 제약 충족 문제는 백트래킹 신호가 강하다
즉 브루트포스는 무식한 실패작이 아니라 좋은 기준선입니다. 다만 문제에 reject 조건이 분명하다면 완전탐색을 줄이는 쪽이 훨씬 실전적일 수 있습니다.
시간 복잡도는 어떻게 이해해야 할까
백트래킹이 항상 다항 시간으로 바뀌는 것은 아닙니다. 최악의 경우에는 여전히 지수적인 많은 상태를 볼 수 있습니다. 다만 reject 조건이 강하면 실제 탐색 트리의 크기가 크게 줄어 체감 속도가 달라집니다.
조합 생성 관점에서는 cp-algorithms의 조합 생성 글처럼 유효한 후보만 직접 구성하는 방식이 전체 후보를 다 만든 뒤 거르는 방식보다 효율적일 수 있다는 설명도 함께 참고할 만합니다.
정리
브루트포스와 백트래킹 차이를 다시 줄이면, 브루트포스는 후보를 끝까지 다 확인하는 기준선이고 백트래킹은 중간에 실패를 알면 그 아래를 잘라내는 전략입니다. 둘 다 완전탐색 계열이지만, 문제에 부분 reject 조건이 있느냐가 실제 선택을 가릅니다.
공식 참고 자료로는 Brute-force search, Backtracking, cp-algorithms 조합 생성 글을 함께 보면 좋습니다.
