Archived(CSE)/알고리즘 (4) 썸네일형 리스트형 기말 정리 Chap 4. • Greedy Approach vs Dynamic Programming • Scheduling(GA로 해결 가능) 정렬 후 넣기 • Knapsack PB(GA는 fractional 만 가능), (DP를 써야 01 문제 해결가능)O(nW, 2^n) Chap 5. Backtracking • DFS 활용(promising 통해 안되는 곳 안들어가기) • N Queens (함수 들어올때 promising 일단 넣고 같은 행, 같은 열, 대각선 체크 후 통과하면 true) • Monte Carlo Alg 난수로 들어가기 • Sum of Subset(knapsack 동일) • Graph Coloring(연결 되어있고 색깔같으면 false) • Hamilton circuit(노드 한번만 방문), 하나.. Chap 4. Greedy Approach - Greedy Approach 는 말 뜻 그대로, 욕심이 많다. 미래를 생각하지 않고 현재만 생각(Locally optimal) - ex) 우리나라 동전은 Greedy Approach로 큰 화폐 단위로부터 locally optimal하게 고르면 잘 골라짐 - MST는 minimum Spanning Tree의 약자로, 최소 weight로 모든 node를 연결하는 트리 형성하기 (참고로 Spanning tree는 1) Sub graph, 2) Cover vertex, 3) Tree 의 조건을 만족해야함) - MST를 만드는 대표적인 두 가지 방법 Prim 알고리즘, Kruskal 알고리즘 - Prim's Alg 는 출발 노드(1)로 부터 가장 작은 값을 고르고, 또 연결된 노드를 포함하여 연결되있는 edg.. Chap 3. Dynamic Programming - Merge sort를 접근하는 데 있어 Divide and Conquer는 적절하다, recursive도 맞을 수 있지만 overlapping이 문제가 되기에 bottom up으로 올라가는 게 맞을 수 있다 - XX로 시작되지 않는 문자열 나열하기는 Qk = 2Qk-1(Y~,Z~) + 2Qk-2(XY~, XZ~) - Binomial coefficient 조합값 찾기 nCk = n-1Ck-1 + n-1Ck - Floyd's Algorithm은 AFSP(All Fair Shortest Path) 찾기 문제이다. - 기본적인 접근법은 Dynamic Programming, 핵심 아이디어는 K를 거치느냐 안거치느냐 - Dk[i,j] (i~j로 가는 경로 중 k 이하 node를 거치는 경로) 를 다음과 같은 경.. Chap 2. Divide and Conquer - Divide and Conquer의 기본은 Binary search를 예로 들 수 있다(시간복잡도와 call-by-value) - Merge sort 또한 Divide and conquer(계속 반으로 갈라서 한 개가 되면 크기 비교하며 합치기) - online은 실시간으로 넣는것(hash), offline은 input 다 넣고 처리 - inplace sort는 배열 제자리에서 처리하는가, stable은 같은 값들을 위치 조정하지 않는가 - stable은 특히 주의 깊게 보기(stable이 좋긴 하지만 실제 제약과 소모값이 있어서 unstable이 빠르긴함) - quick sort 또한 Divide and conquer(pivot 기준으로 ++와 -- 하면서 비교하기) - quick sort가 빠른 .. 이전 1 다음
