[완전 탐색]완전 탐색 레시피

2021. 7. 4. 22:48알고리즘 관련/[레시피]완전 탐색

 

1. 완전 탐색 가능 여부 확인 : 주어진 시간안에 모든 경우의 수 확인이 가능한지 체크.

 

2. 조각 내기 : 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눔.

(각 선택은 답의 후보를 만드는 과정의 한 조각.)

 

3. 부분 문제 해결 :  이 선택 중 한 조각을 선택해 답의 일부를 만들고, 나머지를 재귀 호출을 통해 완성.

 

4. 기저 사례 작성 : 조각이 하나 또는 하나도 남지 않은 경우를 기저 사례로 선택해 처리.

 

 


 

 

 

ex) 보글 게임 문제 (https://algospot.com/judge/problem/read/BOGGLE)

 

1. 주어진 시간안에 모든 경우의 수 탐색 가능한가?

2. 조각 내기 & 답만들기, 재귀 호출 : 각 글자를 하나의 조각으로 만들기. 즉, 현재 글자 == 단어의 글자 ? 재귀 호출 : false.

3. 기저 사례: 위의 경우 + 글자가 한 글자만 남았을 경우 true.