오늘 진행한 일들
- 알고리즘 강의 시청
- 알고리즘 코드 문제 풀이
백트래킹
백트래킹 개념
백트래킹은 주어진 문제를 해결하기 위해 후보해(candidate solution)을 구축해 나가다가, 현재 후보해가 문제의 제약 조건을 위반하는 것으로 판명되면 즉시 후보해를 버리고 백트랙(backtrack)하여 다른 후보해를 시도하는 방법이다. 이 과정은 재귀적으로 수행된다.
백트래킹의 특징
- 탐색 트리(Search Tree): 백트래킹은 탐색 트리를 기반으로 한다. 각 노드는 상태를 나타내며, 루트에서 시작하여 잎 노드까지 탐색한다.
- 상태 공간 트리(State Space Tree): 모든 가능한 상태를 트리 형태로 구성하여 탐색한다.
- 재귀적 접근(Recursive Approach): 재귀 호출을 사용하여 문제를 부분 문제로 나누어 해결한다.
- 제약 조건(Constraints): 후보해가 제약 조건을 만족하는지 확인하여 유효성을 검사한다.
- 가지치기(Pruning): 유망하지 않은 후보해를 미리 제외하여 탐색 공간을 줄인다.
