[알고리즘] 완전탐색

완전탐색 알고리즘은 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다. 일반적으로 완전 탐색 알고리즘은 비효율적인 시간 복잡도를 갖고 있어 데이터 개수가 큰 경우에 정상적으로 동작하지 않을 수 있다. 그래서 일반적으로 알고리즘 문제를 풀 때는 확인(탐색)해야 할 전체 데이터의 개수가 100만 개 이하일 때 완전 탐색을 하면 적절하다. 

완전탐색 알고리즘을 활용하는 방법

완전탐색 알고리즘으로 문제를 풀기 위해서는 다음과 같이 고려해서 수행한다.

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

 

여기서 2)의 모든 방법에는 다음과 같은 방법 등이 있다.

① Brute Force 기법 - 반복 / 조건문을 활용해 모두 테스트하는 방법
② 순열(Permutation) - n개의 원소 중 r개의 원소를 중복 허용 없이 나열하는 방법
③ 재귀 호출
④ 비트마스크 - 2진수 표현 기법을 활용하는 방법
⑤ BFS, DFS를 활용하는 방법

Reference: https://hongjw1938.tistory.com/78