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