가지치기
-
백트래킹 알고리즘 — 재귀로 경우의 수를 탐색하고 불필요한 경로를 잘라내는 핵심 원리
“모든 경우를 다 뒤지면 너무 느린데, 어떻게 하면 빠르게 답을 찾을 수 있을까?” 코딩 테스트에서 순열·조합·N-Queen·스도쿠 같은 문제를 만났을 때 떠오르는 질문입니다. 백트래킹 알고리즘 가지치기는 바로 이 질문의 답입니다. 완전 탐색(Brute Force)처럼 모든 경우를 시도하되, 현재 경로가 답이 될 수 없다고 판단되는 순간 더 깊이…