[알고리즘]백트래킹 개념

백트래킹의 개념 원하는 답을 찾는 방법은 여러가지가 있습니다. 주어진 데이터를 전부 확인하는 방법이 있습니다. 가장 쉽게 떠올릴수 있는 방법이고 답을 찾는게 보장되는 확실한 알고리즘 입니다. 하지만 어떤 문제에서는, 모든 경우를 전부 탐색하는 것은 비효율적인 경우가 많습니다. 예를 들어 출근하면서 집에다 시계를 놓고온 경우에, 내가 사는 아파트를 전부 뒤지는 경우는 없을 겁니다. 보통의 경우에는 본인의 집에서 시계를 찾을 것입니다. 왜냐하면 시계가 내 집에 있는건 확실하니까요. 백트래킹Backtracking도 이와 비슷한 알고리즘 입니다. 내가 원하는 답을 찾을때, 전체탐색을 하지 않고 답이 존재할 가능성이 있는 경우만 탐색을 진행합니다. 이것을 그림으로 나타내면 아래와 같습니다. 백트래킹 동작의 예시 전체탐색의 경우엔 옆집도 보고, 내집도 보는 탐색방법이라고 보시면 됩니다. 백트래킹을 할경우, 옆집은 탐색대상이 아니기 때문에, 더이상 탐색을 진행하지 않고, 내집만 탐색합니다. 이때...

원문링크 : [알고리즘]백트래킹 개념