2021.6.13 TIL : [알고리즘] 백트래킹 (BackTracking)
마지막 알고리즘 수업에서는 백트래킹과 NP-완전을 배웠다. 둘 다 조금은 이해하기 어렵다고 느껴져서 오늘은 이 내용을 정리해보고자 한다. 문제에서 어떤 해를 구할 때, 해의 형태가 n개의 원소로 이루어진 튜플인 경우가 있다. (이 때, 이 튜플 내의 각 원소를 x1, x2, x3, ... xn이라고 한다.) 해의 원소들(xi)은 유한 집합(Si)에서 선택된다. 백트래킹은 기준함수인 P를 최대화/최소화/만족하는 해를 구하는 문제를 해결하는데 적용하는 방법으로 효율적인 알고리즘이 존재하지 않을 경우에 사용한다. 모든 문제의 사례에 대해서 효율적이진 않지만 많은 문제 사례에서 효율적이다. mi를 Si의 크기, 즉 원소의 개수라고 하면, xi가 선택할 수 있는 해는 각각 m1, m2, m3, ..., mi, ...
2021. 6. 13.
