완전탐색

수 빈·2022년 4월 16일

알고리즘 이론

알고리즘과 자료구조

목록 보기

10/12

📍 완전탐색 (≒Brute Force)

완전탐색은 컴퓨터의 빠른 계산 성능을 활용하여 가능한 모든 경우의 수를 탐색하는 방법
'무식하게 푼다'의 의미인 Brute Force 라고도 부름

모든 경우의 수를 탐색하기에 정확성은 100%, 효율성은 꽝
따라서 주어진 N의 크기가 작을 때 사용하는 것이 좋음

'알고리즘' 이라기보다는 문제를 푸는 방법!!

💡 완전탐색의 5가지 방법

완전탐색 기법으로 문제를 해결하기 위해선 아래와 같이 고려해보고 수행함
1. 해결하고자 하는 문제의 가능한 경우의 수를 대략적으로 계산
2. 가능한 모든 방법을 다 고려
3. 실제 답을 구할 수 있는지 적용

위의 2에서 말한 "모든 방법" 5가지
1. 단순 Brute Force
2. 순열
3. 재귀 호출
4. 비트마스크
5. BFS, DFS

🔹 단순 Brute Force

반복문, 조건문을 활용하여 단순하게 모든 방법을 찾는 방법
ex) 자물쇠 암호를 찾는 경우 (0000 ~ 9999 모든 경우를 확인)

🔹 BFS, DFS 활용

그래프 자료구조에서 모든 정점을 탐색하기 위한 방법
ex) 단순히 길을 찾는 문제 => BFS, DFS // 장애물, 목적지 추가 등 추가적인 작업 필요한 문제 => 완전 탐색 + BFS, DFS

🔹 순열

임의의 수열이 있을 때, 그것을 다른 순서로 연산하는 방법인 순열을 활용하는 방법
서로 다른 N개를 일렬로 나열하는 순열의 경우의 수 = N! // N이 한 자릿수 정도..
완전탐색의 대표적인 유형
ex) n개의 숫자로 가능한 모든 순열을 만들어 경우의 수 확인

🔸 재귀 호출

재귀 함수를 통해 해결하는 방법
ex) 부분집합 문제, 만들고자 하는 부분 집합 S'일 때, S' = { }이며 각 원소에 대해 해당 원소가 포함되면 S'에 넣고 재귀 함수 호출, 포함되지 않으면 S'을 그대로 재귀 함수에 넣어주는 방식

🔸 비트마스크

비트(bit) 연산을 통해 부분 집합을 표현하는 방법
ex) 위의 재귀 호출과 마찬가지로 주로 각 원소가 포함되거나, 포함되지 않는 두 가지 선택으로 구성되는 경우에 사용

⭐ 파이썬에서의 완전탐색

조합형 이터레이터: product, permutations, combinations, conbinations_with_replacement

import itertools

# product, 곱집합
# product(p, q, … [repeat=1])
a = [1, 2, 3, 4]
aa = list(itertools.product(a, a))
print(aa) # [(1, 1), (1, 2), (1, 3), (1, 4), ... , (4, 1), (4, 2), (4, 3), (4, 4)]

b = list(itertools.product('1234', repeat=2))
print(b) # [('1', '1'), ('1', '2'), ('1', '3'), ... , ('4', '2'), ('4', '3'), ('4', '4')]

# permutations, 순열
# permutations(p[, r])
# 가능한 모든 순서를 반환, 반복되는 요소 없음
permutations_a = list(itertools.permutations(a))
print(permutations_a) # [(1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4, 2), (1, 4, 2, 3), (1, 4, 3, 2), (2, 1, 3, 4), (2, 1, 4, 3), (2, 3, 1, 4), (2, 3, 4, 1), (2, 4, 1, 3), (2, 4, 3, 1), (3, 1, 2, 4), (3, 1, 4, 2), (3, 2, 1, 4), (3, 2, 4, 1), (3, 4, 1, 2), (3, 4, 2, 1), (4, 1, 2, 3), (4, 1, 3, 2), (4, 2, 1, 3), (4, 2, 3, 1), (4, 3, 1, 2), (4, 3, 2, 1)]

permutations_a = list(itertools.permutations(a, 2))
print(permutations_a) # [(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3)]

permutations_a = list(itertools.permutations(a, 3))
print(permutations_a) # [(1, 2, 3), (1, 2, 4), (1, 3, 2), (1, 3, 4), (1, 4, 2), (1, 4, 3), (2, 1, 3), (2, 1, 4), (2, 3, 1), (2, 3, 4), (2, 4, 1), (2, 4, 3), (3, 1, 2), (3, 1, 4), (3, 2, 1), (3, 2, 4), (3, 4, 1), (3, 4, 2), (4, 1, 2), (4, 1, 3), (4, 2, 1), (4, 2, 3), (4, 3, 1), (4, 3, 2)]

# combinations, 조합
# combinatinos(p, r)
# 반복되는 요소가 없는 정렬된 순서
combinations_a = list(itertools.combinations(a, 2))
print(combinations_a) # [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

combinations_a = list(itertools.combinations(a, 3))
print(combinations_a) # [(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]

# combinations_with_replacement, 중복이 가능한 조합
# combinations_with_replacement(p, r)
# 조합에서 개별 요소마다 두 번 이상 반복할 수 있음
combinations_with_replacement_a = list(itertools.combinations_with_replacement(a, 2))
print(combinations_with_replacement_a) # [(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)]

combinations_with_replacement_a = list(itertools.combinations_with_replacement(a, 3))
print(combinations_with_replacement_a) # [(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4), (1, 2, 2), (1, 2, 3), (1, 2, 4), (1, 3, 3), (1, 3, 4), (1, 4, 4), (2, 2, 2), (2, 2, 3), (2, 2, 4), (2, 3, 3), (2, 3, 4), (2, 4, 4), (3, 3, 3), (3, 3, 4), (3, 4, 4), (4, 4, 4)]

✅ 완전탐색은 언제 사용하면 좋을까?

보통 완전탐색 문제는 for문과 if문을 활용하거나, BFS/DFS를 활용하는 경우가 대부분
추가로 순열을 활용해 완전탐색 문제를 푸는 방법도 자주 나옴!

입력으로 주어지는 데이터(N)의 크기가 매우 작을 때
대부분의 경우 완전탐색 문제는 N의 크기가 매우 작음
완전탐색으로 문제를 푼다면 시간 복잡도가 기본적으로 O(2^N)이나, O(N!)이므로 당연히 N의 크기가 매우 작아야 함
답의 범위가 작고, 임의의 답을 하나 선택했을 때 문제 조건을 만족하는지 역추적할 수 있을 때
답의 범위가 아주 제한적인 경우, 임의로 답을 고정시켜놓고 주어진 조건들이 답에 적합한지 역으로 확인해보는 방법을 이용해보자 (가능한 답을 모두 확인하는 과정에서 완전탐색이 이용됨)