완전탐색(exhaustive search)
① 완전탐색이란?
▷ '무식하게 푼다(brute-force)'는 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미. 이렇게 가능한 방법을 전부 만들어 보는 알고리즘을 뜻한다.
▷ 완전 탐색은 컴퓨터의 빠른 계산 속도를 잘 이용하는 방법이다.
▷ (예제) n개의 원소 중 m개를 고르는 모든 조합을 출력하는 코드
완전 탐색 방법
1. Brute Force : for문과 if문을 이용하여 처음부터 끝까지 탐색하는 방법
2. 비트마스크
3. 순열 : 순열의 시간 복잡도는 O(N!)
4. 백트래킹
5. BFS
① Brute Force 기법 - 반복 / 조건문을 활용해 모두 테스트하는 방법 ② 순열(Permutation) - n개의 원소 중 r개의 원소를 중복 허용 없이 나열하는 방법 ③ 재귀 호출 ④ 비트마스크 - 2진수 표현 기법을 활용하는 방법 ⑤ BFS, DFS를 활용하는 방법
④ 비트마스크(Bitmask)
비트마스크란 비트(bit) 연산을 통해서 부분 집합을 표현하는 방법을 의미한다.
비트 연산이란 다음과 같은 것들이 있다.
And 연산(&) : 둘 다 1이면 1 OR 연산(|) : 둘 중 1개만 1이면 1 NOT 연산(~) : 1이면 0, 0이면 1 XOR 연산(^) : 둘의 관계가 다르면 1, 같으면 0 Shift 연산(<<, >>) : A << B라고 한다면 A를 좌측으로 B 비트만큼 미는 것이다.
⑤ BFS, DFS 사용하기
이는 그래프 자료 구조에서 모든 정점을 탐색하기 위한 방법이다.
BFS는 너비 우선 탐색으로 현재 정점과 인접한 정점을 우선으로 탐색하고 DFS는 깊이 우선 탐색으로 현재 인접한 정점을 탐색 후 그 다음 인접한 정점을 탐색하여 끝까지 탐색하는 방식이다.
