완전 탐색 알고리즘에 대하여

김대일·2021년 5월 24일

TIL

완전 탐색 알고리즘이란

완전 탐색이란 가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법
이 방법은 무식하게 한다는 의미인 "Brute Force" 라고 하기도 한다. 보기엔 아주 직관적이라 이해 하기가 쉽고 정확한 답을 얻어내기엔 좋다.
예를들어, 6자리 금고의 비밀번호를 맞춰야 할때 000000~999999까지 모든 경우의 수를 반복문을 이용해 찾아내는 것이 완전 탐색 알고리즘이라고 할수가 있다.

하지만,

Computer Science 에서 문제 해결에 사용되는 원칙엔 2가지가 있다고한다.

사용된 알고리즘이 적절한가? ( 문제를 해결 할수 있는가 )
사용된 알고리즘이 효율적으로 작동하는가 ?

즉 , 완전 탐색 알고리즘은 문제를 정확히 해결하긴 하지만 효율적인 동작 코드라고 할순 없겠다.

반복문으로 사용해야하는 시간 복잡도가 큰 문제일수록 완전 탐색 알고리즘을 사용하여 문제를 해결 하는것은 최선의 방법이 아닐수도 있다는것이다.

결국, 완전 탐색 알고리즘을 사용할때에는 그 문제에 대한 확실한 파악이 필요하다.

완전 탐색 알고리즘 사용방법

완전 탐색 알고리즘을 사용해 문제를 풀기전에 다음 세가지를 고려해보자.

해결 하고자 하는 문제의 가능한 경우의 수를 대략적으로 계산한다.
가능한 모든 방법을 다 고려한다.
실제 답을 구할수 있는지 적용해본다.

2. 가능한 모든 방법을 고려 하는데 쓰이는 방법들

Brute Force 기법
순열 (permutation )
재귀호출
비트마스크
BFS, DFS

Brute Force 기법이란?

기본적으로 알고 있는 반복문과 조건문을 이용하여 답을 찾는 아주 무식한(?) 방법 이라고 할수 있다.

순열 ( permutation ) 이란?

순열이란, 임의의 수열이 주어졌을때, 그것을 다른 순서로 연산하는 방법이라고 한다.

만약, [1,2,3] 의 수열이 주어졌다면, [3,2,1] 등 순서를 바꾸어서 연산하는 방법이다.

순서를 바꿔서 접근하면 원하는 답에 훨씬 빠르게 접근할수 있는 경우도 있다.

재귀 (Recursive)

재귀는 말 그대로 자기 자신을 호출한다는 의미이다.

재귀 함수를 사용할때에는 중요한 것 세가지가 있다.

재귀를 탈출 하기 위한 탈출 조건이 필요하다
현재 함수의 상태를 저장하는 parameter가 필요하다
return 문을 신경을 잘 써줄것.

완전탐색 재귀와 Dynamic Programming 과 매우 흡사한 점이 있는데,Dynamic Programming 또한 Top - Down 을 사용시 재귀를 사용하게 되는데 기저 사례를 통해 탈출 조건을 만들고, 현재 함수의 상태를 전달하는 parameter 를 전달한다.

또한, return 을 통해 필요한 값을 반환하여 정답을 구하는 연산시 사용하게 되는것 또한 아주 비슷하다.

완전 탐색의 재귀와 Dynamic Programming 의 차이점은 DP는 작은 문제가 큰 문제와 동일한 구조를 가져 큰 문제의 답을 구할 시에 작은 문제의 결과를 기억한 뒤 그대로 사용하여 수행 속도를 빠르게 한다는 것이다.

그에 반해 완전 탐색의 재귀는 크고 작은 문제의 구조가 다를수 있고, 이전 결과를 반드시 기억하는것이 아니라 해결 가능한 모든 방법을 탐색한다는 차이점이 있다.