[SW Expert Academy] 파이썬 SW문제해결 응용_구현 - 05 백트래킹

* 본 글은 SW Expert Academy에서 제공하는 강의를 요약한 것입니다. 백트래킹(Backtracking)은 '퇴각검색'으로도 불리며, 위키백과에서는 '한정 조건을 가진 문제를 푸는 전략'으로 정의하고 있다. 이 알고리즘은 선택지를 트리 구조로 표현하고, 이를 탐색하는 방식으로 해를 찾게 된다. 백트래킹을 통해 풀 수 있는 문제로는 최적화(Optimization), 결정(Decision) 문제가 있다. 최적화 문제는 주어진 조건 내에서 목표 값을 가장 좋게 만드는 해를 찾는 문제이며, 결정 문제는 해의 존재 여부가 해가 된다. 이 알고리즘을 통해 문제해결을 하기 위해 선택지를 트리 구조로 표현하게 되는데, 이 때 만들어진 트리를 '상태공간트리'라고 한다. 상태공간트리의 노드는 다음을 표현한다. ..

2020.05.24