[알고리즘] 완전탐색 (Exhaustive Search)

- 완전탐색 알고리즘이란?

모든 가능한 경우를 일일이 다 탐색해보는 방법. 

직관적이어서 이해하기 쉽고 문제의 정확한 결과값을 얻어낼 수 있는 가장 확실하며 기초적인 방법이다.

하지만 당연히 시간은 최대로 들어간다.

 

*문제 해결 알고리즘을 사용할 때의 2가지 규칙

1. 사용된 알고리즘이 적절한가? (문제를 해결할 수 있는가)

2. 효율적으로 동작하는가?

완전탐색 알고리즘으로 문제를 해결한다면 1번은 만족할 수 있는 가장 확실한 방법이지만 대부분의 경우에 2번을 만족하지 못하기 때문에 이 방법을 사용하는데 제한이 따른다.

따라서 완전탐색 기법을 사용할 때는 그 문제에 대한 파악이 중요.

 

 

- 완전탐색의 종류

1.브루트 포스(Brute force) : 반복(for)/조건문을 활용해 처음부터 끝까지 탐색하는 방법

2.비트 마스크 : 이진수 표현을 자료구조로 쓰는 기법 ( AND, OR, XOR, SHIFT, NOT )

3.백트래킹 : 분할정복을 이용한 기법, 재귀함수를 이용, 해를 찾아가는 도중에 해가 될 것 같지 않은 경로가 있다면 더 이상 가지 않고 되돌아간다.

4.재귀호출 : 함수 내에서 함수 자기 자신을 계속해서 호출하는 것

5.순열 : 서로 다른 n개의 원소 중 r개의 원소를 중복 허용 없이 나열하는 방법

6.BFS(너비 우선 탐색),DFS(깊이 우선 탐색) 활용

 

- 관련 문제

완전탐색(재귀 + 순열) : 프로그래머스 소수 찾기 (programmers.co.kr/learn/courses/30/lessons/42839)

백준 2309번 : 일곱 난쟁이 (https://www.acmicpc.net/problem/2309)

백준 2231번 : 분해합 (https://www.acmicpc.net/problem/2231)

백준 3085번 : 사탕 게임 (https://www.acmicpc.net/problem/3085)

백준 10448번 : 유레카 이론 (https://www.acmicpc.net/problem/10448)

백준 2503번 : 숫자 야구 (https://www.acmicpc.net/problem/2503)

백준 1018번 : 체스판 다시 칠하기 (https://www.acmicpc.net/problem/1018)

백준 1182번(DFS,재귀호출) : 부분집합의 합 (https://www.acmicpc.net/problem/1182)