[알고리즘] 백트래킹(Backtracking)
·
CS/알고리즘
"답이 아닌 것 같으면 즉시 돌아가서 다른 길을 탐색하는 스마트한 완전 탐색" 백트래킹이란?백트래킹(Backtracking)은모든 경우를 시도하되,"이 경로는 답이 될 수 없다"라고 판단되면바로 중간에 포기하고 되돌아가는(Back) 알고리즘입니다.브루트포스(완전 탐색)를 더 효율적으로 개선한 형태라고 볼 수 있습니다.일단 가능한 선택을 따라 내려가면서 탐색합니다.중간에 잘못된 선택이라고 판단되면, 다시 이전 상태로 돌아갑니다.돌아가면서 다른 선택을 다시 탐색합니다.주요 키워드"선택(Choice)""탐색(Explore)""포기(Abandon)""되돌아가기(Backtrack)"백트래킹이 필요한 이유완전 탐색(Brute Force)은 단순하지만, 가능한 모든 경우를 끝까지 가보려 합니다.하지만 경우의 수가 너..