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

[알고리즘] 백트래킹(Backtracking) [알고리즘] 백트래킹(Backtracking) 백트래킹이란?모든 경우의 수를 검색하는 알고리즘'특정조건'을 만족하는 모든 경우의 수를 찾고 싶을 때 유용DFS(깊이 우선 탐색)을 기반으로 하는 알고리즘 후보해 집합에서 최적해 집합을 찾아내는 문제에 적용 가능!후보해 : 정답이 될 가능성이 있는 모든 조합최적해 : 문제의 답으로 기준을 만족하는 해 DFS는 Brute Force 알고리즘으로, 재귀함수를 통해 그냥 모두 다 검사해서 찾음 DFS와 백트래킹의 차이점은 '가지치기'가지치기를 이용하기 때문에 DFS처럼 모든 경우의 수를 확인하는 알고리즘은 아님! 가지치기는 어렵게 생각하지말고 반복문에서 break나 return에 해당한다고 생각하자 백트래킹 대표 문제..