[알고리즘] 완전탐색(Exhaustive search)이란?

완전탐색

완전탐색이란 이름 그대로 모든 것을 탐색

즉, "모든 경우의 수를 다 만들어 보는 방법"입니다.

 

만약 휴대폰 비밀번호 4자리의 핀 번호를 까먹어서 0000 ~ 9999 까지 모든 수를 도전 해본다면, 최대 10000번의 도전이 있을 것입니다.

 

이 처럼 완전 탐색은 무식하게 모든 경우의 수를 전부 탐색하기 때문에 시간 복잡도가 매우 커서 입력값의 크기가 작을 때 사용하기 좋습니다.

 

---

완전탐색 알고리즘

1. Brute Force 

단순한 반복문(for)과 조건문(if)으로 모든 경우의 수를 만들어 답을 구하는 방법입니다.

아주 기초적인 문제에 주로 나옵니다.

 

2. Bitmask (비트마스크)

2진수를 이용하는 컴퓨터의 연산을 이용하는 방식

나올 수 있는 모든 경우의 수가 "각각의 원소가 포함되거나, 포함되지 않는 두 가지 선택으로 구성되는 경우" 유용하게 사용가능합니다.

 

비트마스크의 예로, 원소가 n개인 집합의 모든 부분 집합을 구할 때 각 원소가 포함되는지 포함되지 않는지를 0, 1로 구분하여 체크하는 것이 있습니다.

 

원소가 5개인 집합이 [1, 2, 3, 4, 5] 일 때

[1,2,3,4,5] → 11111
[2,3,4,5]   → 11110
[1,2,5]     → 10011
[2]         → 00010

집합의 i번째 요소가 존재하면 1, 그렇지 않으면 0을 의미합니다.

 

3. 순열 (Permutation)

순열은 서로 다른 N개를 일렬로 나열하는 경우의 수를 말합니다.

순열의 경우의 수는 N!으로 완전 탐색을 이용하기 위해서는 N이 한자리 수는 되어야 합니다.

순열에 원소를 하나씩 채워가는 방식이며 재귀 함수를 이용할 수 있습니다.

 

만약 배열 [ 1, 2, 3, 4, 5, 6 ]이 주어진 다면 이 배열의 길이 6개중 5개를 뽑았을 때의 경우의 수 총 6개로 다음과 같습니다.

1 2 3 4 5 
1 2 3 4 6 
1 2 3 5 6 
1 2 4 5 6 
1 3 4 5 6 
2 3 4 5 6

 

4. 재귀 함수

비트마스크와 마찬가지로 주로 각 원소가 포함되거나, 포함되지 않는 두 가지 선택을 가질 때 이용됩니다.

재귀 함수를 통해서 문제를 만족하는 경우들을 만들어가는 방식으로 대표적인 예로는 피보나치 수열이 있습니다.

 

 

5. DFS / BFS

• DFS(깊이 우선 탐색)

 그래프에서 깊은 부분을 우선적으로 탐색합니다.

 

• BFS(너비 우선 탐색)

그래프에서 가장 가까운 부분을 우선적으로 탐색합니다.

 

 

[알고리즘] 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)

 

---

 

프로그래머스 완전탐색 코딩 테스트 문제

[Java/자바] 프로그래머스 - 소수 찾기 (에라토스테네스의 체)