알고리즘 - 완전 탐색

완전 탐색 알고리즘

---

완전 탐색 알고리즘은 모든 경우의 수를 시도하는 기법으로 가장 기본적이고 간단한 유형의 알고리즘이다.

될 수 있는 모든 조건 혹은 모든 조합을 다 대입해보며 해답을 찾는 알고리즘이다.

모든 경우의 수를 전부 탐색하기 때문에 100% 정확성을 보장하지만 반대로 높은 시간 복잡도를 가진다.

 

완전 탐색 알고리즘에는 선형 구조와 비선형 구조로 나눌 수 있다.

선형 구조

브루트 포스

모든 경우의 수를 다 검사하여 원하는 값을 탐색하는 방법

경우의 수가 적을 때 사용하는 것이 좋다.

비트마스크

이진수의 비트 연산을 통해 경우의 수를 줄여가며 탐색하는 방법

비트 마스크를 사용하여 하나의 변수에 여러 개의 상태 정보를 저장할 수 있으며 이를 통해 복잡한 조건문을 간단하게 처리할 수 있다. 경우의 수가 많을 경우에 유리하다.

백트래킹

해결책을 찾아가 도중에 막히게 되면 다시 돌아가서 다른 경로로 탐색을 하여 모든 가능한 경우의 수를 탐색하여 해결책을 찾아가는 방식이다.

순열 탐색

순열을 이용하여 모든 경우의 수를 탐색하는 방법이다. 쉽게 구현할 수 있지만 큰 데이터에서는 비효율적일 수도 있다.

재귀

자기 자신을 호출하며 모든 가능한 경우를 체크하면서 최적의 해답을 찾는 방법이다. 

 

비선형 구조

DFS & BFS 

DFS와 BFS는 그래프 탐색 기법으로 특정 데이터부터 시작하여 다음 데이터 혹은 인접한 데이터를 탐색하는 방법이다.

비선형 구조로 되어 있는 문제에서 완전 탐색을 하기 위해 사용되는 기법이다.

 

완전 탐색 알고리즘의 장단점

완전 탐색 알고리즘의 장점

간단한 구현

완전 탐색 알고리즘에서 가장 큰 장점은 다른 복잡한 알고리즘보다 구현이 훨씬 쉽다는 점이다. 문제가 간단하고 데이터의 크기가 크지 않다면 쉽게 적용할 수 있는 알고리즘이다.

 

완전 탐색 알고리즘의 단점

느린 성능

완전 탐색 알고리즘에서 가장 큰 단점으로는 느린 성능이다. 말 그대로 주어진 데이터를 빠짐없이 모두 탐색하기 때문에 다른 효율적인 알고리즘에 비해서 느린 시간 복잡도와 공간 복잡도를 가지고 있다.

제한적인 활용 범위

앞서 언급한 단점으로 인해 완전 탐색 알고리즘을 적용할 수 있는 범위가 제한적이다. 데이터의 크기가 큰 경우 조금 복잡해지더라도 다른 효율적인 알고리즘을 적용하는 것이 더 좋다.