이 레슨과 관련된 학습 키워드
컴퓨터 과학 & 프로그래밍 — 문제 해결의 도구 → 알고리즘 — 문제 해결의 체계적 접근 → 알고리즘 — 문제 해결의 체계적 접근 → 문제 해결
Learn backtracking: N-Queens, permutations, combinations, subsets, pruning strategies, Sudoku solver.
{백트래킹→백트래킹}은 모든 가능성을 탐색하되 유망하지 않은 경로를 일찍 포기하는 기법이에요.
쉽게 말하면 미로에서 막다른 길을 만나면 뒤로 돌아가는 것과 같아요.
결정을 하나씩 내려가면서 해를 트리 형태로 만들어 가는 거예요.
그런데 중간에 조건에 맞지 않으면 즉시 되돌아가요.
이걸 {pruning→프루닝}, 즉 가지치기라고 부르죠.
왼쪽 트리를 보세요. {brute force→브루트 포스}, 완전 탐색은 모든 16개 노드를 빠짐없이 확인해요.
A, B, C 세 가지에서 각각 또 세 가지로 뻗어나가니까 기하급수적이죠.
반면 오른쪽 {backtracking→백트래킹} 트리를 보세요.
C 가지는 아예 잘라버렸어요. 유망하지 않다고 판단한 거예요.
A에서도 A2가 조건에 안 맞으니까 더 깊이 들어가지 않아요.
결과적으로 탐색 노드가 16개에서 8개로 절반이나 줄었어요.
4-{Queens→퀸즈} 문제를 예로 들면 완전 탐색은 256가지를 확인하지만 {backtracking→백트래킹}은 겨우 16개만 봐요.
{backtracking→백트래킹}의 핵심 구조는 네 단계예요.
첫째, 가능한 옵션 중 하나를 선택해요.
둘째, 그 선택이 제약 조건을 만족하는지 확인해요.
셋째, 해를 찾았는지 목표를 확인해요.
넷째, 선택을 취소하고 다음 옵션을 시도하는 되돌림이에요.
이 레슨에서는 엔퀸즈, 순열, 조합, 부분집합, 스도쿠까지 다양한 문제를 다뤄볼 거예요.
하단의 파란 박스를 보세요. 선택, 검증, 되돌림의 반복이 {backtracking→백트래킹}의 전부예요.
이 패턴만 잘 익히면 어떤 탐색 문제도 체계적으로 풀 수 있어요.
선생님: {백트래킹→백트래킹}과 완전 탐색의 가장 큰 차이가 뭘까요?
학생: {백트래킹→백트래킹}은 중간에 유망하지 않으면 더 이상 탐색하지 않는 거요?
선생님: 정확해요! 가지치기를 통해 불필요한 탐색을 줄이는 거죠. 오른쪽 트리에서 C가 잘린 걸 보셨죠?
학생: 그럼 {백트래킹→백트래킹}은 항상 완전 탐색보다 빠른 건가요?
선생님: 최악의 경우는 같지만 실제로는 {pruning→프루닝}이 효과적이라 훨씬 빨라요.
학생: 되돌림이 없으면 어떻게 되나요?
선생님: 상태가 오염돼서 다른 가지 탐색이 엉망이 돼요. 되돌림은 {backtracking→백트래킹}의 생명이에요.