알고리즘 문제 해결 전략을 읽고
(p.145 ~ p.173)
CH 06. 무식하게 풀기
6.1 도입
무식하게 푼다는 말은 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미한다. 이렇게 가능한 방법을 전부 만들어 보는 알고리즘을 흔히 완전 탐색이라고 부른다.
6.2 재귀 호출과 완전 탐색
재귀 함수란 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수이다. 이 재귀 호출은 완전 탐색을 구현할 유용한 도구이다.어떤 문제를 완전 탐색으로 해결하기 위해 필요한 과정은 다음과 같다.
- 최대 크기의 입력을 가정했을 때 답의 개수를 계산하고 이들을 모두 시간 안에 생성할 수 있을지 가늠하기 (계산할 수 없다면 설계 패러다임을 적용해야 한다.)
- 가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나누기 (각 선택은 답의 후보를 만드는 과정의 한 조각이 된다.)
- 그 중 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성하기
- 조각이 하나밖에 남지 않은 경우, 혹은 하나도 남지 않은 경우에는 답을 생성했으므로, 이것을 기저 사례로 선택해 처리하기
