시간복잡도 정리 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유망함을 점검하고 유망한 노드만 그..
DSA/Concepts of Algorithm
3. Branch&Bound 분기한정법 State Space Tree활용 최적해 구하기에 적용 가능. Backtracking보다는 최적해를 구하기 위해 모든 해의 한계값(직접x)을 계산해 고려함. 각 노드에 대한 한계값bound을 계산함. 해당 노드는 bound보다 큰 값을 가질 확률이 없음. bound값이 지금까지의 최적해보다 좋은가?로 최적해 값을 업데이트하고 노드의 promising여부를 판단함. promising하지 않은 노드의 자식노드는 탐색하지 않음. 0-1 Knapsack 문제 state space tree : 왼쪽으로 가면 현재 아이템을 담지 않는 걸로, 오른쪽으로 가면 현재 아이템을 담는 걸로 함. 루트에서 리프노드까지의 모든 경로가 해답후보임 최적해를 찾는 문제이므로 전체를 다 탐색하기..
2. BackTracking 백트래킹(되추적) 막히면 왔던 길을 되돌아가서 다시 찾는다 최적화 문제와 결정 문제(yes/no) 해결 우리가 해줄 것은 해가 만족해야 하는 조건bound정하기! State Space Tree 활용으로 promising여부 확인(bound) n-Queens문제 n개의 Queen을 한 체스판에 가로세로대각선 방향으로 위치가 겹치지 않도록 배치하는 문제. State Space Tree 상태공간트리 : 문제해결의 중간 사태를 각 노드로 나타낸 트리 루트에서 리프노드까지의 모든 경로가 해답의 후보이며 그 중 답이 되는 경로를 Answer States라 함 답이 나올 가능성이 전혀 없는 노드를 유망하지 않은non-promising 노드, 그렇지 않은 노드를 유망한promising 노드..
미쳐 복습해 기억안나 1. Dynamic Programming 동적 프로그래밍 작은 부분문제들부터 모두 해결한 후 부분 문제들의 해를 이용해 큰 문제를 해결하는 방법(부분 문제들 사이에 의존적) Bottom-up 한 번 구한 값은 절대 바뀌지 않고, 여러번 사용될수 있음 최적성원칙 Principle of Optimality : 최종해는 최적의 부분해들로 이루어져 있어서 최종해 안에 최적의 부분해들이 포함됨 최적성원칙 Principle of Optimality 를 만족하는 문제에서만 동적 프로그래밍 사용 가능 최적화 문제 : 주어진 문제에 대하여 가장 최적인 해답을 찾는 문제 shortest path문제 - all pairs shortest paths 문제(alll to all 알고리즘) 각 정점에서 다른..
순차검색 2. 분할정복 이분검색 합병정렬 : 다 하나짜리로 쪼개고 하나씩 합치며 정렬 QuickSort 빠른정렬. 분할 교환 정렬 : 기준값(pivot, 보통 맨 첫번째 값)을 정함. 남은 것들 양쪽ij인덱스로 좁히면서 기준값보다 큰거작은거 자리바꾸고 마지막에 j랑 기준값이랑 자리바꿈 3. Greedy 알고리즘 순서 선정 selection 적정성 점검 feasibility check : 조건에 만족하는가 해답 점검 solution check : 최적의 해인가 - 증명은 어려워도 반례가 없는지 마지막에 확인해보는 절차 권장 Fractional Knapsack problem : 단위무게당 profit이 큰 것 부터 넣는 것이 최적 0-1 Knapsack problem Two-way Optimal Merge ..
