브루트포스, 백트래킹

브루트포스

• 무식한 힘
• 가능한 모든 경우에 대해 탐색
• 구현이 쉽고, 해가 존재한다면 무조건 답을 찾을 수 있음
• 그러나, 모든 경우에 대해 탐색하기 때문에 시간 복잡도 효율성 낮음 → 메모리 사용량 많음
• 장단점이 명확 ⇒ 사용해야할 문제와 그렇지 않은 문제도 확실
• 가장 기본적인 알고리즘. 이를 바탕으로 다른 알고리즘으로의 확장

 

예를 들어, 비밀번호가 4자리이고, 숫자로만 이루어져 있다면 비밀번호를 풀기 위해서 0000부터 9999까지 다 입력해보면 된다. 경우의 수가 10000가지 이므로 이는 컴퓨터에서 충분히 빠른 처리가 가능한 연산이다.

하지만 비밀번호가 12자리라면 범위가 000000000000부터 999999999999이므로 경우의 수가 1000000000000가지이다.python의 경우 1억 개의 case계산이 1초이므로 1000000000000가지는 컴퓨터에서도 시간이 오래 걸리는 작업이다.이러한 경우 브루트 포스는 좋은 방법이 아니다.

 

브루트 포스의 시간복잡도는 보통 O(경우의 수 * 방법 1개를 시도해보는데 걸리는 시간 복잡도)이다.

브루트포스 사용하면 좋은 문제

 

<종류>

• 선형 구조 - 순차 탐색
• 비선형 구조 - 백트래킹, DFS, BFS

일반적으로 브루트포스라고 하면 선형 구조인 순차 탐색을 일컫는 말이나,

백트래킹, DFS, BFS도 비선형 구조인 브루트포스에 해당됨. (특히나 그래프 문제에서 유용하게 쓰이기 때문에 따로 다루는 경우가 많음)

선형 구조 브루트포스 풀이 방법

• 선형 구조로 구조화
• 구조화된 문제를 조건에 따른 해가 무엇인지 파악
• 파악된 해 정리

 

백트래킹

 

백트래킹은 보통 (브루트포스 + 특정 조건)으로 이루어져 있는데 모든 경우를 탐색하다가 중간에 조건을 만족하지 못하면 즉시 다른 노드로 넘어가는 방법이다

• 해를 찾는 도중 해가 아님을 판단하면, 되돌아가서 다시 해를 찾아가는 방법
• 현재 상태에서 가능한 모둔 후보군을 따라 들어가며 탐색하는 알고리즘
• 가지치기 - 불필요한 부분을 쳐내고 최대한 되돌아가는 것을 피하도록 하는 것이 관건 → 이에 따라 시간복잡도 결정
• 즉, 모든 가능한 경우의 수 중 특정한 조건을 만족하는 경우만 살펴보는 것과 동일
• 해가 되기 위한 여러 조건들을 살펴보면서 해가 될 수 있는지 탐색(모든 경우) 중 만족하지 않은 조건이 있으면 가지치기(특정한 조건을 만족하는 경우만 살펴봄)
• N-queen 문제가 대표적인 백트래킹 문제 → 문제 설명 + 코드 제공

 

<비선형 구조인 다른 DFS와의 차이점?>

백트래킹은 해를 찾는 도중 해가 아님을 판단하면 더이상 탐색하지 않고 되돌아감. 그러나 DFS는 끝까지 탐색!