[코딩테스트][알고리즘] 2. Backtracking(빽트레킹)

Backtracking 이란 알고리즘은 거창하게 보이지만 사실 별거 없다. 하지만 backtracking 알고리즘이 사용되는 문제는 몇 문제를 제외하고는 난이도가 엄청 높다고 한다. 

 

Backtracking은 완전탐색을 진행하다가 조건에 맞지 않는 경우 탐색을 중단하고 이전 단계로 돌아가는 방법이다.

 

빽트레킹의 경우에 시간복잡도를 계산하기는 힘든 경우가 많다.

 

얼마나 많은 조건을 추가하느냐에 따라서 실행속도가 달라진다.

 

추천문제 : 

1. https://www.acmicpc.net/problem/15655

2. https://www.acmicpc.net/problem/9663

3. https://www.acmicpc.net/problem/2580

4. https://www.acmicpc.net/problem/1987