[완전 탐색]완전 탐색 레시피
2021. 7. 4. 22:48ㆍ알고리즘 관련/[레시피]완전 탐색
1. 완전 탐색 가능 여부 확인 : 주어진 시간안에 모든 경우의 수 확인이 가능한지 체크.
2. 조각 내기 : 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눔.
(각 선택은 답의 후보를 만드는 과정의 한 조각.)
3. 부분 문제 해결 : 이 선택 중 한 조각을 선택해 답의 일부를 만들고, 나머지를 재귀 호출을 통해 완성.
4. 기저 사례 작성 : 조각이 하나 또는 하나도 남지 않은 경우를 기저 사례로 선택해 처리.
ex) 보글 게임 문제 (https://algospot.com/judge/problem/read/BOGGLE)
1. 주어진 시간안에 모든 경우의 수 탐색 가능한가?
2. 조각 내기 & 답만들기, 재귀 호출 : 각 글자를 하나의 조각으로 만들기. 즉, 현재 글자 == 단어의 글자 ? 재귀 호출 : false.
3. 기저 사례: 위의 경우 + 글자가 한 글자만 남았을 경우 true.