제약만족1 알고리즘 - 백트래킹, N-Queens 백트래킹 (N-Queens, 가지치기, DFS)분할 정복·DP·그리디가 모두 효율적인 알고리즘 패러다임이었다면, 백트래킹(Backtracking)은 본질적으로 모든 가능한 답을 시도해 보는 완전 탐색의 정교한 변형이다. "일단 한 길로 가 보고, 막히면 되돌아 와 다른 길을 시도하는" 사고방식이며, N-Queens·미로 찾기·스도쿠·조합 생성처럼 답의 후보가 트리 구조로 자라는 문제에 강력하다. 핵심 기교는 가지치기(Pruning) — 명백히 답이 될 수 없는 경로를 미리 잘라 내는 일이며, 가지치기 없는 백트래킹은 단순 완전 탐색일 뿐이다. 본 글은 백트래킹의 정의·DFS와의 관계·N-Queens 고전 풀이·가지치기 전략을 세심하게 정리한다(출처: CLRS — Introduction to Algorit.. 2026. 5. 19. 이전 1 다음