브루트 포스
• 브루트 포스(Brute Force)는 모든 경우의 수를 다 해보는 기법이다.
예를 들어, 비밀번호가 4자리이고, 숫자로만 이루어져 있다면 비밀번호를 풀기 위해서 0000부터 9999까지 다 입력해보면 된다. 경우의 수가 10000가지 이므로 이는 컴퓨터에서 충분히 빠른 처리가 가능한 연산이다.
하지만 비밀번호가 12자리라면 범위가 000000000000부터 999999999999이므로 경우의 수가 1000000000000가지이다.
python의 경우 1억 개의 case계산이 1초이므로 1000000000000가지는 컴퓨터에서도 시간이 오래 걸리는 작업이다.
이러한 경우 브루트 포스는 좋은 방법이 아니다.
따라서 문제의 제한 시간 내에 먼저 브루트 포스로 문제를 풀 수 있는지 대략적인 틀을 파악하는 것이 중요하다.
브루트 포스의 시간복잡도는 보통 O(경우의 수 * 방법 1개를 시도해보는데 걸리는 시간 복잡도)이다.
브루트 포스 사용법
브루트 포스로 문제를 풀기 위해서는 다음과 같은 3가지 단계를 생각해볼 수 있다.
- 문제의 가능한 경우의 수를 계산해본다.
- 가능한 모든 방법을 다 만들어본다.
- 각각의 방법을 이용해 답을 구해본다.
(1) 문제의 가능한 경우의 수를 계산해본다.
이는 빅오로 대충 어림잡아 계산할 수 있고, 대부분 손으로 계산 할 수 있다.
시간복잡도와 공간복잡도가 제한을 넘지 않는지 추정 가능하다.
(2) 가능한 모든 방법을 다 만들어본다.
하나도 빠짐 없이 만들어야 한다.
대표적으로 그냥 다 해보는 방법, 순열 , 재귀 호출, 비트마스크가 있다.
특히 재귀 호출을 자주 사용하는데 재귀 호출 코드 작성시 반드시 넣어야 하는 코드 블록이 있다.
- 정답을 찾은 경우
이 코드가 없으면 영원히 재귀 호출 하다가 컴퓨터가 터져버린다.
반드시 재귀 호출을 끝내는 코드가 있어야 한다. - 불가능한 경우
이 코드도 마찬가지로 재귀 호출을 끝내는 코드인데 정답과 동떨어진 경우이다. 잘못된 경로로 재귀 호출을 하더라도 언젠가는 재귀 호출을 끝내야 하기 때문에 이 코드가 필요하다. - 다음 경우
그 다음 재귀 호출을 불러오는 코드도 필요하다.
이 코드가 없으면 재귀 호출이 아니다.
def go(s):
if cnt == 10: # 1. 정답을 찾은 경우
return True
if index == n: # 2. 불가능한 경우
return
go(s-1) # 3. 다음 경우
(3) 각각의 방법을 이용해 답을 구해본다.
답을 구하자.
백트래킹(Back Tracking)
• 백트래킹은 보통 (브루트포스 + 특정 조건)으로 이루어져 있는데 모든 경우를 탐색하다가 중간에 조건을 만족하지 못하면 즉시 다른 노드로 넘어가는 방법이다
• DFS와 혼동하는 경우가 있는데 DFSD와 백트래킹은 다음과 같은 차이점이 있다.
백트래킹 : 해를 찾는 도중 현재 선택한 루트가 해와 관련이 없다는 것을 알게되면 중단하고 다른 루트를 탐색
DFS : 깊이 우선 탐색을 이용하여 하나의 루트를 완전히 탐색하고 다음 루트로 넘어감
