backtracking (1) 썸네일형 리스트형 23. Backtracking 퇴각 검색(백트래킹, Backtracking)은 문제의 답이 될 수 있는 경우를 단계별로 확인하면서 가능한 답이나 최적해를 구하는 방법이다. 만약 어떤 단계에서 답이 될 수 없다는 것이 확인되었다면 이전 단계로 돌아간다. 이렇게 이전 단계로 돌아가는 것을 가지치기(Pruning)라고 한다. 백트래킹 역시 명확하게 설명하기 쉬운 개념은 아니기 때문에 예제를 보면서 이해하는 것이 도움이 될 것이다. BOJ 15649. N과 M (1) (Silver III) 기본적인 백트래킹 문제이다. 함수 $f(k)$가 $k$개의 수를 고른 상태에서 호출된다고 하면, 남아 있는 $(n-k)$개의 수 중 하나를 고르고 $f(k+1)$을 호출한다. 만약 $k = m$일 경우 지금까지 고른 $m$개의 수들을 출력하고 이전 단계로.. 이전 1 다음
