[알고리즘] 완전탐색이란?

 

• 완전탐색이란?
  • 문제를 해결할 수 있는 가장 naive한 방법
  • 완전탐색은 모든 가능한 경우에 대해서 탐색을 하는 것
  • 어떤 조건에 맞는 객체를 찾아내기 위해서 가능한 모든 객체를 탐색한다. 

 

• 언제 이 알고리즘을 사용해야 하는가?
  • 1. 더 효율적인 알고리즘 방법이 생각이 안날 때
  • 2. 기준(변수)을 잡고 그 기준에 따라 모든 경우의 수를 선택할 수 있을 때
  • 3. 시간 복잡도를 만족할 때

 

• 어떻게 사용해야 하는가?
  • 기준을 잡아야 함 -> 모든 객체를 선택할 수 있는 기준으로
  • 전체 객체를 빠짐없이 선택해야함
  • 선택한 개체가 조건에 맞는지 확인하기

 

• 완전탐색 구현 방법 
  • for문으로 구현
  • 재귀함수로 구현

 

• 코드트리 완전탐색 종류
  • 자리 수 단위로 완전탐색
  • 구간 단위로 완전탐색
  • 자리 마다 숫자를 정하는 완전탐색
  • 물체 단위로 완전탐색
  • 값을 기준으로 완전탐색
  • 격자 안에서의 완전탐색