[알고리즘] 완전 탐색

포스팅 목적

알고리즘의 유형 중 완전 탐색 기법과 그 유형에는 어떤 것이 있는지 알아봅니다.

 

완전 탐색이란?

완전 탐색(Exhaustive Search)이란 가능한 경우의 수를 모두 확인하는 방법으로, 무식하게 푼다는 뜻의 Brute-Force 라고도 합니다.

 

완전 탐색 기법

완전 탐색 기법을 사용하기 위해서는 가능한 경우의 수를 중복 없이 모두 확인할 수 있는 순회 방법들을 사용합니다.

• 단순한 중첩 for 문
  : 순회하는데 별다른 기법 없이 모든 경우를 셀 수 있을 때 사용합니다.
• 재귀 함수
  : 순열 (permutation), 조합 (combination) 과 같이 반복적인 작업을 구현할 때 사용합니다.
• 2^n 경우의 수
  : 개수의 제한 없이 포함이나 선택 여부를 판단해야할 때 사용합니다.

 

완전 탐색 문제의 특징

중첩 되는 for문 마다 시간 복잡도가 n 승으로 증가하기 때문에 입력으로 주어지는 데이터가 작아야 하는 제한 조건이 있습니다.

 

참고 자료

• 완전 탐색 (Brute-Force Search / Exhaustive Search) 알고리즘
• JavaScript로 순열과 조합 알고리즘 구현하기
• 알고리즘 문제 해결 전략