시간복잡도 정리 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유망함을 점검하고 유망한 노드만 그..
Algorithm
3. Branch&Bound 분기한정법 State Space Tree활용 최적해 구하기에 적용 가능. Backtracking보다는 최적해를 구하기 위해 모든 해의 한계값(직접x)을 계산해 고려함. 각 노드에 대한 한계값bound을 계산함. 해당 노드는 bound보다 큰 값을 가질 확률이 없음. bound값이 지금까지의 최적해보다 좋은가?로 최적해 값을 업데이트하고 노드의 promising여부를 판단함. promising하지 않은 노드의 자식노드는 탐색하지 않음. 0-1 Knapsack 문제 state space tree : 왼쪽으로 가면 현재 아이템을 담지 않는 걸로, 오른쪽으로 가면 현재 아이템을 담는 걸로 함. 루트에서 리프노드까지의 모든 경로가 해답후보임 최적해를 찾는 문제이므로 전체를 다 탐색하기..
순차검색 2. 분할정복 이분검색 합병정렬 : 다 하나짜리로 쪼개고 하나씩 합치며 정렬 QuickSort 빠른정렬. 분할 교환 정렬 : 기준값(pivot, 보통 맨 첫번째 값)을 정함. 남은 것들 양쪽ij인덱스로 좁히면서 기준값보다 큰거작은거 자리바꾸고 마지막에 j랑 기준값이랑 자리바꿈 3. Greedy 알고리즘 순서 선정 selection 적정성 점검 feasibility check : 조건에 만족하는가 해답 점검 solution check : 최적의 해인가 - 증명은 어려워도 반례가 없는지 마지막에 확인해보는 절차 권장 Fractional Knapsack problem : 단위무게당 profit이 큰 것 부터 넣는 것이 최적 0-1 Knapsack problem Two-way Optimal Merge ..
