오늘은 알고리즘 중 하나인 완전 탐색 알고리즘에 대하여 알아보려고 한다.

완전 탐색(Exhaustive Search)이란?

완전 탐색이란, 가능한 경우의 수를 모두 구하여 답을 찾는 방법이다. 알고리즘이라고 하기 보단 답을 찾는 방법이라고 할 수 있다. 답을 찾는 방법이고 경우의 수가 너무나도 많아질 경우엔 모든 경우의 수를 확인하는 것은 너무 어렵기 때문에 완전 탐색에 주로 사용되는 알고리즘 기법들 또는 테크닉들이 있다.

사용되는 알고리즘 기법, 테크닉

완전 탐색의 경우 N의 크기가 작을 때, 시간 복잡도가 N의 지수승, 팩토리얼 꼴로 나올 때 많이 사용된다.

단순 탐색
알고리즘 기법을 사용하지 않고, 반복문과 조건문등을 이용하여 가능한 모든 경우를 만들어 답을 구하는 방법이다. 매우 비효율 적이기 때문에 가급적이면 쓰이지 않는다.

비트 마스크
비트란, 컴퓨터에서 사용되는 2진 숫자로 되어있는 최소 단위이다. 이러한 이진수를 기반으로 0이면 true 1이면 false 혹은 2진수를 십진수로 표한 하는 형태로 사용이 가능하다. 예를 들면, 배열이 있고 그 배열의 부분만 들어있는 배열이 있다고 해보면,

{1,2,3,4,5}
{1,2,3}, {2,4,5}, {1,2}, {4,5}

부분 집합의 배열을 전체 배열에 인덱스에 비교하여 boolean형태의 배열을 만들 수도 있다(ex.{1,2,3} => {1,1,1,0,0}). 하지만 이럴 경우 많은 메모리 사용과 오버헤드를 증가시킬 수 있다. 따라서, 비트마스크를 이용하여 정수형태로 나타낼 수 있다. {1,2,3,4,5} => 11111(2) => 31
{1,2,3} => 11100(2) => 28
{2,4,5} => 01011(2) => 11
{1,2} => 11000(2) => 24
{4,5} => 00011(2) => 3
이렇다고 한다면 {1,2,3}의 부분 집합의 배열은 28의 정수형태로 표현이 가능하다는 말이다.

재귀 함수
재귀 함수란 메소드에서 자기 자신을 다시 호출하여 작업을 수행하는 방식의 함수를 의미한다. 이렇듯, 같은 함수를 자기 자신이 계속해서 호출하여 모든 탐색을 진행할 수 있다는 것과 동일하다. 다만, 메모리를 많이 차지하기 때문에 성능이 반복문에 비하여 느리고, 적절히 빠져나오지 못하게 만든다면, 무한히 호출하기 때문에 코드를 짤 때 유의 해줘야한다.

순열
순열이란 서로 다른 n개의 집합에서 순서대로 늘어놓은 경우의 수를 얘기하며, 완전 탐색의 대표적인 유형이다. 또한, 재귀 함수를 이용하여 수를 채워나가지만, n이 커질 수록 처리시간이 길어지므로, n이 크기가 작아야한다.

BFS(너비 우선 탐색)/DFS(깊이 우선 탐색)알고리즘도 같이 사용되긴하지만, 따로 다룰 생각이므로 다음 포스팅에서 소개하려고 한다.