dynamic

시간복잡도 정리 Dynamic 최단경로 : n^3 0-1배낭 : min(2^n, nW) 최적이진탐색트리OBST : n^3 Backtracking 그래프 색칠 노드의 수 : m^n Branch and Bound 0-1배낭 : 2^n 방법 핵심 정리 Dynamic: 작은 부분들부터 계산해서 Bottom-up으로 올라가며 작은 부분들의 결과를 이용해 다음 단계 결과를 계한하는 것. 의존적. 한번 계산한 값은 바뀌지 않음 principle of optimality 최적성원칙을 만족해야 함 - 큰 문제의 최적해는 최적의 작은 문제 해들로 구성되어야 함 최적화 문제 Backtracking : state space tree를 사용해 bound를 만족하는 노드에 대해 promising유망함을 점검하고 유망한 노드만 그..