완전탐색이란?

완전탐색이란?

컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미.

이렇게 가능한 방법을 전부 만들어 보는 알고리즘을 일컫는다. 그리고 컴퓨터의 빠른 계산  속도를 잘 이용하는 방법이다.

알고리즘이라고 부르기보단, 문제 푸는 방법이라고 이해하면 좋을 거다.

 

Ex. 알고리즘을 모르는 상태에서, 문제를 풀 때, 가능한 모든 경우의 수를 확인해서 답을 찾아낸다. 이 과정이 완전 탐색이다. 

-> 이럴 경우, 수열의 수가 적을 경우에는 충분히 빠르게 해결하겠지만, 수열의 수가 억 단위일 경우에는 시간복잡도 문제가 생긴다.

따라서, 가능한 경우의 수가 많은 경우에는 이용하기 어려우므로 완전 탐색을 이용할 수 있는지 ? 잘 파악하는게 중요하다.

탐색해야 할 개수가 100만 개 이하일 경우에 사용하면 적절하다.

 

 

완전 탐색 방법 ?

- Brute Force 

- 비트 마스크 (Bitmask)

- 순열 (Permutation)

- 백트래킹

- BFS(너비 우선 탐색) / DFS(깊이 우선 탐색)

 

 

1. 브루트 포스 ( Brute-Force )

: 단순히 for 와 if 를 이용해 문제를 풀어가는 방식이다.

Boj - 유레카 이론(10448), 숫자 야구(2503), 가르침(1062), 사탕게임(3085), 분해합(2231), 일곱 난쟁이(2309), 숫자판 점프(2210)

 

2. 비트마스크 ( Bitemask )

: 2진수(AND, OR, XOR, SHIFT, NOT)를 이용하는 컴퓨터 연산을 이용하는 방식이다.

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

비트 마스크를 사용하는 이유는, 정수로 집합을 나타낼 수 있다는 점이다.

Boj - 집합(11723), 해멍 거리(3449), 이진수 연산(12813), 데스스타(11811), 외판원 순회(2098), 중복제거(13701)

 

3. 순열 ( Permutation )

: 서로 다른 n 개 중 r 개를 골라 순서를 고려해 나열한 경우의 수를 말한다.

Ex. 집합의 원소가 { A, B, C } 일 때, 3개의 원소를 모두 사용하여 순서를 고려해 나열하는 경우의 수는?

-> ABC, ACB, BAC, BCA, CBA, CAB, 총 6 경우,

Boj - N과 M(15649~15666), 1,2,3 더하기 2(12101)

 

4. 백트래킹 

: 분할정복을 이용한 기법. 재귀함수를 설계할 때, 고려해야 할 아주 중요한 개념입니다. 

해를 찾아가는 도중에 해가 될 것 같지 않은 경로가 있다면? 더 이상 가지않고 'BACK' 을 합니다.

Boj - 부분 수열의 합(1182), 암호 만들기(1759), 좋은 수열(2661), 미친로봇(1405)

5. BFS / DFS

: 그래프 탐색 방법의 대표적인 두 알고리즘이다 .

BFS - 가까운 노드부터 검색

- 큐 자료구조에 기초(선입선출)

- 시간복잡도 O(N) - 실제 수행시간은 DFS보다 좋은 편 

Boj - 경로 찾기(2479), 섬의 개수(4963), 양(3184), 바이러스(2606), 영역구하기(2583), 단지 번호 붙이기(2667), 탈출(3055), 게리맨더링(17471), 연결요소의 개수(11724), DFS와 BFS(1260), 숨바꼭질(1697), 숨바꼭질2(12851), 상범빌딩(6593), 물탱크(15972), 성곽(2234), 버스 갈아타기(2536), 물통(14867), 미로만들기(2665)

DFS - 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로를 탐색

- 스택 자료구조에 기초(선입후출)

- 스택을 이용한 알고리즘이기 때문에, 실제 구현은 재귀함수를 이용 했을 때 간결해진다.

- 시간 복잡도 O(N)

Boj - 숫자 고르기(2668), 벽장문의 이동(2666), 하노이 탑(1914), 미로탐색(1912), 루빅의 사각형(2549), 텀 프로젝트(9466), 순열 사이클(10451), N-Queen(9663), 적록색약(10026), 빙산(2573), 부등호(2529)