수정입니다

Fibonacci1) iterationf2 = f1+f0f3 = f2+f1f4 = f3+f2f5 = f4+f3=> 밑에서부터 순차적으로 중복 없이 계산 => T(n) = O(n) ==> 더 효율적이다 2) recursionf5 = f4+f3f4 = f3+f2f3 = f2+f1 ....f5를 구하려면 T(2^n/2) 만큼의 시간이 소요 => subproblem overlapping => 비효율적Sequential search[1,2,3,4,5,6,7,8,9]=> 앞에서부터 순차 탐색 ==> iteration 방식=> worst case T(n)만큼 소요 => O(n)Binary search[1,2,3,4,5,6,7,8,9]=> 반씩 나눠서 탐색(정렬필수)Bin_sea..

보호되어 있는 글입니다.

Greedy Algorithms Design : BF -> D&C -> DP -> Greedy DP : optimal solution -> O(n^3) : NOT practical in fields Design Naming >> BF. D&C. DP(=mathematical programming) >> Greedy의 의미는 무엇인가요? * Greedy algorithm: sprit - 학생들마다 greedy 설계는 달라질 수 있다. * Real-life problems: mostly optimization problems. If we assume, "local optimal --> global optimal" "Greedy" Greedy Algorithm: Grabs data items in sequen..

Dijkstra Algorithm. => 가장 대표적인 Greedy problem. shortest path problem - part 1. single-source == 출발점이 정해짐 Single-Source Shortest Paths Problem 1. Problem: find a SP from A to B 2. Model : a weighted graph G=(V,E) -> function f : E(sequence of edges) -> R. -> find the mininum R(total cost = min weight) -> SSSP: G given, S(starting vertex) given -> find SPs from S to v in V: delta(S,v) 3. Solution ..

Kruskal Algorithm - Part 1. Kruskal_MST(input G) : edge-based approach ----------------------------------- Sort Edge set 'E' : my ranking/scoring function. while NOT solved yet{ select next edge 'e' : from sorted list 'E' if (cycle check) remove/pass else add 'e' if (stop condition) stop } ==> Edge들을 정렬해서 자료구조에 넣어놓음 (weight가 같은 edge는 random으로 선택해도 무방) ==> 이런식으로 vertex에 정렬된 edge들을 순서대로 추가해나감 ==> ..

Prim Algorithm - Part 1. Prim's Algorithm: node(vertex)-based approach(ranking) F = empty set // ouput => 조건에 맞는 edge들을 추가해감 Y = {v1} ==> start edge while NOT solved yet{ select v in V-Y nearest to Y # selection feasibility test (cycle?) # 불필요 # => 이미 가지고 있는 node에서 짧게 연결되는 노드를 가져옴 => cycle이 생길 수가 없음 (가지고 있는 노드는 다음 loop에서 제외되니까 그런듯?) ADD v to Y if V == Y stop/exit. } 1. Time complexity T(n) => Gr..

Floyd Algorithm - Part 1. All Pair Shortest Path(APSP) Problem => 한 노드에서 다른 모든 노드까지 가는 최단거리의 모든 조합을 다 구하는거 Floyd-Warshal algorithm (DP) APSP def. Problem : Given any pair (u,v) find a SP from u to v. Model : on graph. Solution Algo: Design -> Analysis -> Best algorithm? 1) Brute-force, enumeration: O(n!) 2) Divide and Conq(나눈 subproblem 간의 독립이 아닌 간섭이 있을 수 있음): think?! 3) Dynamic prog: O(n^3) -> ..

DP : Binomial Design - Part 1 이항계수 ( n개 중 k개를 뽑는 조합 ) (n,k) = (n-1, k-1) + (n-1, k) 0 D&C_Bin_left(n-1, k-1) D&C_Bin_right(n-1, k) step 3 ==> return left + right } D&C 방법 B[5,3] = B[4,2] +B[4,3] B[4,2] = B[3,1] + B[3,2] B[4,3] = B[3,2] + B[3,3] --> linear recurrence가 발생함 ( 세부 문제로 쪼개는데 크게크게 쪼개지지 않음) --> multi-dimensional recurrence. --> observe 'subproblem overlapping' => 왼/오 가 독립이 안됨(문제 사이즈가 크게 ..

Divide - and - Conquer ==> Top - down approach binary search merge 과정이 필요 없는 가장 간단한 D&C recursion으로 구현할 수도 있는데, iteration으로 구현할 수도 있음 tail - recursion (끝에서 계속 재귀호출) => stack overflow.. ==> iteration 버전을 쓰자. merge sort quick sort Divide and Conquer - Design Ex 흑석동 중앙대학교 --> 부산대병원 응급실 가기 ==> Question : find the best path. ==> A problem ==> various solution approaches -->중앙대 --> 서울역 ktx --> 부산역 -->..

An algorithm is a step-by-step procedure used to solve a problem. ------- The Importance of Developing Efficient Algorithms Sequential Search array의 첫번째부터, item을 찾을 때까지 쭉 각각의 value를 살펴보는 방식 Binary Search array의 middle 포인트를 잡아서 찾는 item의 위치에 따라 반을 버려가면서 찾음(정렬 필수) Sequential Search vs Binary Search n번의 탐색을 하는 sequential search보다, 조사할 array를 반으로 줄여주는 binary search가 더 효율적이다. O(n) vs O(logn) ==> O(log..