[알고리즘 공부] 완저탐색기법 - 비트마스크, 순열 ,재귀

---

참고

완전탐색기법

---

완전 탐색 자체가 알고리즘은 아니기 때문에 완전 탐새 방법을 이용하기 위해서 다양한 알고리즘 기법이 이용됨.

1. 단순 Brute-Force
2. 비트 마스크(Bitmask)
3. 재귀 함수
4. 순열 (Permutation)
5. BFS/DFS

1. 단순 Brute-Force

단순히 반복문과 조건문으로 모든 경우를 만들어 답을 구하는 방법.
이방법만을 사용하는 문제는 거의 나오지 않음.

2. 비트마스크(Bitmask)

나올 수 있는 모든 경우의 수가 각각의 원소가 포함되거나, 포함되지 않는 두가지 선택으로 구성되는 경우 유용하게 사용
ex ) 원소가 N개인 집합의 모든 부분집합을 구한다면, 각 원소가 포함되는지 포함되지 않는지를 0,1 로 구분하여 배열에 저장해 둘 수 있음.

3. 재귀함수

비트마스크와 마찬가지로 각 원소가 두가지 선택지를 가질 때 유용하게 사용.
포함이 되면 해당 원소를 넣어 함수를 호출하고, 포함되지 않으면 그 상태에서 함수를 호출하는 등의 식.

• ex)피보나치 수열
• 시간복잡도 O(N)

3. 순열

순열(permutation)은 서로 다른 N개를 일렬로 나열하는 방법(경우의 수)를 말함.
순열의 경우의 수는 N!으로 완전 탐색을 이용하기 위해서는 N이 한자리 수는 되어야 함.

• 순열에 원소를 하나씩 채워가는 방식.
• 시간복잡도 O(N!)

4. 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)

너비우선탐색(Breadth-First Search, BFS)는 하나의 요소를 방문하고 그 요소에 인접한 모든 요소를 우선 방문하는 방식
깊이우선탐색(Depth-First Search, DFS)는 트리의 한 요소(노드)와 다음 수준(level)의 자식 노드를 따라가는 방향으로 탐색하는 방식
길 찾기 등에 주로 쓰이는 알고리즘
: 단순 길찾기에는 BFS/DFS만 써도 무방하지만,
장애물이 존재하는 등 추가적 연산이 필요할 때 완전탐색 병용하기도 함.