백 트레킹 알고리즘

🤔 넌 뭐냐?

먼저 사전적인 정의는

해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다.

🙋 어라? DFS 아닌가요???

네 저도 처음 봤을 때 그냥 DFS 인줄 알았습니다. 그러나 둘은 큰 차이점이 있는데요.

• DFS : 가능한 모든 경로 탐색 O(N)!
  -백트래킹 : 해를 찾다가 '이 경로로는 안나오겠는데...?' 그러면 그 경로로 더 가지 않고 돌아감.

예시를 들어볼게요, 만약에 관악산을 등산하려고 합니다. 당연히 목표는 최단 시간 돌파입니다! DFS는 모든 등산루트를 다 돌아보게 됩니다. 그러나 백 트레킹은 등산 코스 지도를 보고 🗺

백트레킹 : 아...이거 너무 빙 돌아가네... 오래걸리겠다.. 이 코스는 버리고 다른 코스로 가야지 ㅎㅎ!

이렇게 하는 친구입니다. 이걸 개발자답게 바꾸면, 특정한 조건을 만족하는 경우만 살펴보는 것 입니다.

🙋 그러면 어떻게 이친구가 간?을 보는 건가요?

이 친구는 세이브 포인트가 있어서 망한거 같다 싶으면 그 세이브 포인트로 돌아가서 다른 루트를 시행하게 됩니다. ( 부럽다.. )

즉, 해를 찾을 수 있을지 판단하고 아무래도 아닌거 같다 싶으면 이전 부모 노드로 돌아가 다른 자식 노드로 갑니다. 이것을 가지치기 라고 하고 이 요건에 따라 성능이 천차만별로 바뀔 수 있습니다!

그래서 특정한 알고리즘 코드가 있다기 보다는 DFS + DP + 조건 느낌의 알고리즘 입니다. 그렇기 때문에 연습 문제들을 참고하며 체화 시키도록 하겠습니다.

감소하는 수