posts/algo-23/

[utterances-bot]

알고리즘 - 백트래킹(Backtracking)의 정의 및 예시문제 | ChanBLOG

이번에 살펴볼 개념은 백트래킹에 관한 내용입니다.

https://chanhuiseok.github.io/posts/algo-23/

[haeni0117]

선생님 ! 블로그 글 너무 잘봤습니다. 그런데 제가 헷갈리는 부분이 있어서 여쭤보고 싶습니다. 다른 블로그에서는 <그 노드를 포함한 경로가 해답이 될 수 없으면 그 노드는 유망하지 않다고 하며, >라고 되어있는데 선생님 블로그에서는 <해가 될 가능성이 있으면 유망하다>라고 되어있습니다. 유망하다(promising)라는 표현이 정확히 어떤 뜻인지 설명해주실 수 있을까요? 전체 알고리즘의 효율성측면에서 긍정적인 표현인건지, 부정적인 표현인건지 잘 모르겠습니다!

[ChanhuiSeok]

@haeni0117 안녕하세요 :) 보통 유망하다(promising)는 표현은 코드를 통해 이해하면 더 와닿을 수 있을 것 같습니다.

위의 N-queen 문제(https://chanhuiseok.github.io/posts/baek-1/) 를 예로 들어 보면, 유망함의 판단 조건이 '퀸이 놓였을 때 퀸 자신을 기준으로 일직선상(가로 및 세로)과 대각선 방향에는 아무것도 놓여있으면 안 된다' 입니다. 퀸을 놓을 때 위 조건에 어긋나면, 거기에는 퀸을 놓지 않고 다른 경로를 다시 탐색하는데요. 이 때 조건에 어긋났던 그 길은 해답이 될 수 없으므로 유망하지 않다고 말할 수 있습니다. 반대로 위 조건에 어긋나지 않다면 해가 될 가능성이 있으므로 유망하기(promising) 때문에 그 자리에 퀸을 놓을 수 있습니다.

조건에 어긋나서(유망하지 않아서) 그 경로로 갈 시도를 하지 않는 것을 가지치기라고 합니다. 이렇듯 모든 경로를 다 탐색하지 않기 때문에 효율성을 높일 수 있는 것입니다!

[Denia-park]

덕분에 좋은 내용 잘 보고 갑니다. 정말 감사합니다.