백트래킹

백트래킹?

백트래킹은 현재 상태에서 가능한 모든 후보군을 따라 들어가며 해결책에 대한 후보를 구축해 나아가다 가능성이 없다가 판단되면 즉시 후보를 포기하면서 정답을 찾아가는 범용적인 알고리즘이다.

• 제약 충족 문제를 풀 때 주로 쓰인다.

• 가능성이 없는 후보를 가지치기 한다고 생각해도 된다.

• 즉, 한마디로 현재 상태에서 가능한 모든 선택지로 다 가보면서 가능성이 없다면 선택지를 포기하는 알고리즘이다.

대표적인 백트래킹 문제

1. N과 M(1) (🔗 풀이)

2. N-Queen (🔗 풀이)

3. 부분 수열의 합 (🔗 풀이)