완전탐색

완전탐색, Brute Force라고 부른다.

존나 쌔보이는 이름으로

소프트웨어 보단 하드웨어같다.

두둥 탁!

…

농담이다

개념

개무식하고 강한 방법이다.

맨땅에 헤딩 말이다.
가능한 모든 경우의 수를 맨발로 뛰어다니며
확인한다…

이것이 완전탐생이다.

구현도 쉽고 효과적이지만
값이 작을때만 그렇다.

값이 커져버리면
알래스카에서 김상덕씨 찾듯
존나게 오래 걸려버리니 주의하자

언제 쓰냐?

경우의 수가 적거나
답을 확실하게 찾고 싶을때,
문제에서 입력 조건이 작게 주어질 때 쓴다.
ex) 입력조건 : 최대 10개 이하

예시

숫자 맞추기 (비번 뚫기)

# 000~999까지 다 해보며 비밀번호 찾기
for i in range(1000):
    if is_password(i):   # 비밀번호 조건 함수
        print("정답:", i)
        break

2중 for문을 통한 모든 쌍 비교

arr = [1, 3, 5, 7]
for i in range(len(arr)):
    for j in range(i+1, len(arr)):
        print(arr[i], arr[j])   # 모든 쌍 출력

재귀로 모든 경우의 수 탐색

def dfs(level, path):
    if level == 3:
        print(path)
        return
    for i in range(2):  # 0, 1 두 가지 선택
        dfs(level+1, path+[i])

dfs(0, [])

장단점

장점	단점
단순하다, 구현 쉽다	느리다, 시간 오래 걸릴 수 있다
모든 경우를 보장해서 확실하다	입력이 크면 시간초과 발생
실수할 가능성이 적다	최적화 필요할 때 불리함

여담

N퀸 문제 등 꽤 자주 쓰인다.

이걸로 나중에 비번 뚫어보고 싶다.