[코딩 테스트 합격자 되기] 백트래킹

[인프런] 코딩 테스트 합격자 되기 C++

강의 링크 : https://www.youtube.com/watch?v=VvcEx75Bgvk&t=1s

---

[백트래킹의 개념]

• 가장 최근에 방문했던 노드로 다시 돌아감
• 완전 탘색하지 말고, 내가 찾는 답일 가능성이 있는 경우에만 탐색

[백트래킹을 푸는 과정] [c++ 코드]

• 상태 정의 : 문제의 각 단계에서 가능한 상태를 정의
• 유망 함수 (isPromising) : 현재 상태가 유망한지 판단, 유망하지 않으면 더 이상 탐색 X
• 해결책 확인 (isSolution) : 현재 상태가 문제의 해결책인지 판단
• 재귀 호출 : 유망한 상태로 이동하면서 문제 해결

[예제]

1. 부분합
2. N-Queen

---

추천 문제
https://school.programmers.co.kr/learn/courses/30/lessons/87946
https://school.programmers.co.kr/learn/courses/30/lessons/12952
https://school.programmers.co.kr/learn/courses/30/lessons/92342