완전탐색
- 완전탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법이다.
- 파이썬은 데이터 처리량이 많을 때 꼭 메모리 제한을 고려해야 한다.
완전탐색 알고리즘 동작 과정
1) 해결하고자 하는 문제의 가능한 경우의 수를 대략적으로 계산한다.
2) 가능한 모든 방법을 다 고려한다.
3) 실제 답을 구할 수 있는지 적용한다.
완전탐색의 종류
1) Brute Force 기법
2) 백트래킹(Backtracking)
3) 순열(Permutation)
4) 재귀함수
5) 비트 마스크(Bit Mask)
6) DFS/ BFS
1) Brute Force 기법
Brute Force 기법은 무식하게 가능한 것을 다 해보겠다는 의미를 가지며, 반복문이나 조건문을 통해 가능한 모든 방법을 단순히 찾는 경우를 말한다.
사용 예시
0~9의 숫자를 가진 네자리 자물쇠를 풀기 위해서는 최악의 경우 반복문을
10×10×10×10=10,000회 돌리면서 답이 되는지 확인해야 한다.2) 백트래킹(Backtracking)
백트래킹(Backtracking)은 DFS를 사용하여 해를 찾는 도중 해가 될 것 같지 않은 경로가 있다면 더 이상 가지 않고 되돌아가서 다시 해를 찾아가는 기법을 말한다.
사용 예시
DFS는 깊이 우선 탐색으로 그래프의 깊은 부분부터 탐색을 한다.
깊은 노드로 가면서 특정 조건에 부합하지 않으면 그 아래의 노드들은 확인하지 않는다.
따라서 Brute Force보다 시간, 공간 측면에서 단축될 것이다.3) 순열(Permutation)
순열(Permutation)은 임의의 수열이 주어졌을 때 그것을 다른 순서로 연산하는 방법이다. 같은 데이터가 입력되었지만 그 순서에 따라 의미가 있을 때 사용한다. 파이썬의 itertools의 permutation를 이용한다.
사용 예시
문제에서 순열에 대한 조건이 있을 때(ex : N개 중 M개를 골라 탐색) 순열을 사용하고
완전탐색을 진행한다.4) 재귀 함수
재귀 함수를 통해서 문제를 만족하는 경우들을 만들어가는 방식이다. 재귀 함수를 활용할 때는 다음의 것들을 신경 써주어야 한다.
(1) 재귀를 탈출하기 위한 탈출 조건이 필요
조건을 만족했을 때 재귀를 탈출하지 않는다면 배열에 범위 초과가 나거나 무한 루프가 발생할 수 있다.
(2) 현재 함수의 상태를 저장하는 parameter가 필요
현재 함수의 상태를 저장하지 않는다면 현재 함수의 상태를 저장할 수 없어 재귀 탈출 조건을 만들 수 없게 되거나 잘못된 결과를 출력하게 된다.
(3) return문 신경 쓸 것
재귀를 통해 이후의 연산 결과를 반환 후 이전 결과에 추가 연산을 수행하는 경우가 있다. 이 경우 return문에 신경써야 한다.
사용 예시
N개의 숫자 중 M개를 고르는 경우 다중 반복문으로 해결할 수 있다.
하지만 N과 M이 매우 큰 숫자라면 반복문을 수백, 수천개를 써야할 수도 있다.
이 때 재귀 함수를 활용한다면 자기 자신을 호출함으로써 다음 숫자를 선택할 수 있도록 해
전체 코드를 짧게 줄일 수 있다.5) 비트 마스크(Bit Mask)
비트 마스크(Bit Mask)는 이진수를 이용하는 컴퓨터의 연산(AND, OR, XOR, SHIFT, NOT 등)을 이용하는 방식이다. 완전 탐색 문제에서는 모든 경우의 수가 각각의 원소가 포함되거나, 포함되지 않는 두 가지 선택으로 구성되는 경우에 유용하게 사용된다.
사용 예시
원소가 4개인 집합의 모든 부분집합을 구하는 경우, 어떤 집합의 부분집합은 집합의 각 원소가
해당 부분집합에 포함되거나 포함되지 않는 두 가지 경우만 존재한다.
따라서 4자리 이진수로 각 원소의 포함 여부를 체크할 수 있다.6) DFS/BFS
완전탐색과 DFS/BFS를 함께 사용하는 유형으로 많이 나온다.
사용 예시
단순히 길을 찾는 문제라면 DFS/BFS만 이용해도 충분하지만, 주어진 도로에 장애물을 설치하거나
목적지를 추가하는 등 추가적인 작업이 필요한 경우 이를 완전탐색으로 해결하고 DFS/BFS를
이용해야 한다.