반응형 역추적1 Backtracking Algorithm Design Method (백트래킹 알고리즘) 이번에는 백트래킹 알고리즘에 대해 알아보자. 이 글에서 알아볼 것은 다음과 같다. 백트래킹 기술 설명 백트래킹 기법이 문제 해결에 적절한 접근 방식인지 판단 주어진 문제에 대한 상태 공간 트리 정의 주어진 문제에 대한 상태 공간 트리의 노드가 유망(promising)하거나 비유망(non-promising)한 경우 정의 상태 공간 트리를 제거하는 알고리즘 생성 주어진 문제를 해결하기 위해 백트래킹 기법을 적용하는 알고리즘 생성 여기서 상태 공간 트리(state-space-tree)란 문제 해결의 중간 상태를 각각 한 노드로 나타낸 트리이다. ※ P, NP Problem 백트래킹을 살펴보기 전에 P, NP에 대해 간단히 짚고 넘어가자. 이제 막 알고리즘에 대해 배우고 있는 입장에서 명확히 이해하기 어려운 개.. 2021. 11. 22. 이전 1 다음 반응형
