[알고리즘] 백트래킹(Backtracking)

[알고리즘] 백트래킹(Backtracking)

 

백트래킹이란?

모든 경우의 수를 검색하는 알고리즘

'특정조건'을 만족하는 모든 경우의 수를 찾고 싶을 때 유용

DFS(깊이 우선 탐색)을 기반으로 하는 알고리즘

 

후보해 집합에서 최적해 집합을 찾아내는 문제에 적용 가능!

후보해 : 정답이 될 가능성이 있는 모든 조합

최적해 : 문제의 답으로 기준을 만족하는 해

 

DFS는 Brute Force 알고리즘으로, 재귀함수를 통해 그냥 모두 다 검사해서 찾음

 

DFS와 백트래킹의 차이점은 '가지치기'

가지치기를 이용하기 때문에 DFS처럼 모든 경우의 수를 확인하는 알고리즘은 아님!

 

가지치기는 어렵게 생각하지말고 반복문에서 break나 return에 해당한다고 생각하자

 

 

백트래킹 대표 문제

N-Queen