공부/자료 구조 및 알고리즘
2019. 7. 19.
알고리즘 기법[전체 탐색] - 백트래킹(Backtracking)
백트래킹(Backtracking) 비선형으로 구성된 자료 구조를 깊이 우선으로 탐색할 때, 더 이상 나아갈 수 없는 상황에서 그 이전 단계로 복귀하는 과정을 말한다. -일반적으로 최적화 문제를 해결할 때 사용하는 방법이다. -문제를 비선형으로 구조화한 다음, 가능한 모든 상태를 깊이 우선으로 탐색해가며 해를 구성해 나간다. -이 과정에서 더 이상 탐색을 진행할 수 없으면 백트래킹하여 다시 다른 상태를 조사해 나간다. -모든 가능한 상태를 다 조사하며 이를 백트래킹 기법이라 한다. 문제해결 방법 ① 주어진 문제를 비선형 구조로 구조화한다. ② 구조화된 문제공간을 적절한 방법으로 해를 구성할 때까지 탐색한다. ③ 구성된 해를 정리한다. 예제 및 알고리즘 주어진 3 x 3 행렬에서 개의 원소를 서로 행과 열이..