(2021.11.23) 알고리즘 수업들으면서 정리하기 21탄 w12-2 녹강, w12-3 녹강, w13-1 실강 maximum flow, network flow 내용이다. Flow network Maximum-flow problem : flow network G가 주어지고, source s, target t, capacity c 가 주어질 때, value가 최대인 flow를 찾는 문제 Max-flow min-cut theorem : max-flow의 값과 min-cut의 값이 같다. The Ford-Fulkerson method The Ford-Fulkerson method가 the maximum-flow problem을 해결한다. input: a flow network G, source s, targe..

(2021.11.17) 알고리즘 수업들으면서 정리하기 20탄 w11-2 녹화강의, w12-1 실강 minimum spanning tree와 prim algorithm 내용이다. Minimum Spanninng Tree 최소 신장 트리 --> 줄여서 MST input: 방향성 없는 연결 그래프 connected, undirected graph G=(V,E) (각 edge 들에 weigth가 있음) output: acyclic subset T of the edges of G (G의 모서리들의 cycle 없는 subset) Model은 undirected graph G=(V,E) 임 각 edge (u,v) ∈ E 에는 weight w(u,v) 가 있음 (u,v ⊂ V) acyclic T⊆E 에 대해서 모든 노..

(2021.11.12) 알고리즘 수업들으면서 정리하기 19탄 w10-3 녹화강의, w11-1 실강 BFS,DFS 내용이다. Network flow graph 알고리즘 - Breadth-first search - Depth-first search - Minimum spanning tree (Prim's algorithms) - Maximum flow (The Ford-Fulkerson method) graph G=(V,E) 로 표현한다. - V는 vertices 의 집합 (G.V) - E는 edges 의 집합 (G.E) G는 방향성일 수도 있고, 무방향성일 수도 있다. (directed, undirected) 보통 graph는 인접리스트나 인접행렬로 표현한다. BFS(Breadth-first search)..

(2021.11.08) 알고리즘 수업들으면서 정리하기 18탄 w10-2 녹화강의 huffman code 개념, 만드는 방법, greedy 알고리즘 Huffman codes each character를 binary charcter code로 디자인하는 것 optimal prefix code 라고도 한다. huffman code는 빈도수에 따라서 설정해준다. huffman code는 variable-length code이며, fixed-length code보다 효율적이다. (fixed-length code는 3비트로 표현한다--> 많은 저장용량을 차지한다.) prefix-free code (prefix code) huffman code의 가장 큰 특징은 prefix-free code(prefix code)이..

(2021.11.04) 알고리즘 수업들으면서 정리하기 17탄 w10-1 실시간 강의 greedy algorithm에 관한 내용과 huffman code 설명 조금(huffman은 다음 동영상정리에) activity selection 내용 전에 greedy 알고리즘 설명해주신 부분의 연장선 같음 Greedy algorithm greedy algorithm은 언제나 optimal solution을 도출해내는 것은 아니다. greedy algorithm으로 해결했을 때, 그 결과가 optimal solution이 아닐 수도 있다는 것이다. 어떠한 상황에서 greedy로 풀면 optimal한 결과가 나온다 라는 general한 접근법이 없기 때문에 greedy algorithm은 해봐야 알 수 있다. greed..

(2021.11.03) 알고리즘 수업들으면서 정리하기 16탄 w9-2 강의 activity selection을 greedy algorithm으로 푸는 방법을 배웠당 Activity Selection : greedy algorithm d.p는 subproblem이 두개가 나오지만, greedy algorithm은 subproblem이 하나만 나온다. aj와 am이 다른 경우에 Ak'를 정의하게 되는데 Ak'은 Ak에서 aj를 빼고, am을 넣은 것이라고 생각하면 된다. Ak'의 activity들이 서로 오버랩되지 않는다는 것이 중요하다. am은 Sk에서 가장 빨리 끝나는 activity이고, aj는 Ak에서 가장 빨리 끝나는 activity이다. 그렇기 때문에 am이 aj보다 빨리 끝날 것이다.(am이 더..

(2021.10.27) 알고리즘 수업들으면서 정리하기 15탄 Activity selection :공통의 자원에 대한 독점적인 사용을 필요로 하는 활동 N개가 있는데 이를 어떻게 스케줄링 할 것인가 하는 문제를 말한다. ex) 교실의 대한 사용을 스케줄링 하는 문제 Problem: 여러 competing activities 사이의 스케줄을 조정하는 것 ( 각 activity에 대해서 시작과 종료시간은 주어짐) Goal: nonoverlapping activities 의 largest possible set을 선택함 이를 이제 dynammic programming 기법으로 접근해보겠다 greedy algorithms으로 접근하는 건 다음 시간..

(2021.10.27) 알고리즘 수업들으면서 정리하기 14탄 greedy algorithms 개념 (생각보다 내용이 없다) Greedy algorithms : 탐욕 알고리즘 greedy algorithm은 dynamic algorithms과 마찬가지로 optimization에 쓰인다. greedy algorithm은 the activity selection problem에도 쓰인다. dynamic algorithms vs greedy algorithms - dynamic algorithms은 problem을 sub-problem으로 나누어서 sub-problem을 overlapping 하며 larger sub-problem으로 build up 해간다. - greedy algorithms은 problem을..

(2021.10.14) 알고리즘 수업들으면서 정리하기 13탄 7주차 보충강의내용- Knapsack problem (보충강의 있는지 모르고 실강 전에 안들었다..) Knapsack problem:dynamic programming 문제: item 여러개가 있는데, 그 item은 각각의 value와 weight를 가진다. knapsack은 W(kg)까지 수용할 수 있다. 이때, knapsack에 담을 수 있는 최대 value가 무엇인가?? 우선, 이 문제를 navie approach로 풀어본다면 각각의 item을 순서대로 넣을지 말지를 결정하기 때문에 2 x 2 x ... x 2=2^n 의 시간이 걸린다. --> O(n^2) Dynamic programming 의 4단계를 거쳐 문제를 풀어볼 수 있다. Ch..

(2021.10.14) 알고리즘 수업들으면서 정리하기 12탄 7주차 실강 내용- rod cutting problem (손글씨가 아닌 모든 첨부사진은 교수님 강의노트가 출처-알고리즘 교재) Rod cutting problem 설명하시기 전에 왜 dynamic programming인가?? 에 대한 수업을 하셨다 Why dynamic programming?? duplicate computation(반복적인 계산)이 많을 때, dynamic programming이 아주 효과적임! 예를 들어 생각하면 이해하기 쉽다. n개에서 k개를 고르는 이항정리 문제는 위와 같이 표현할 수 있다. 이것으로 코드를 만들어본 것이 아래다. C(n,k)=C(n-1,k-1)+C(n-1,k)에서 다시 C(n-1,k-1)과 C(n-1,k..

(2021.10.10) 알고리즘 수업들으면서 정리하기 11탄 6주차 내용- LCS optimal substructure 을 찾는 것에 중점을 두자 recurrence를 쓸 수 있어야 함 LCS(The longest common subsequence) Definition[subsequence] Definition[common subsequence] 만약 Z가 X의 subsequece 이면서, Y의 subsequence이면, Z는 X와 Y의 common subsequence라고 한다. Z는 consecutive(연속적) 일 필요는 없으나 in order (순서대로) 여야한다. Definition[Prefix of a subsequence] X= 이라는 sequence에 대해 prefix of X (for i..

(2021.10.10) 알고리즘 수업들으면서 정리하기 10탄 6주차 내용- 새로운 개념 등장 Dynamic programming Dynamic programming 의 개념 Dynamic programming 의 4단계

(2021.10.10) 알고리즘 수업들으면서 정리하기 9탄 5주차 내용-3 마지막!!! Binary search 주어진 배열에서 찾고자하는 값이 있는 인덱스를 찾는 problem 이다. Divide-and-conquer approach Divide A[1..n] into two parts A[1..mid-1] and A[mid+1..n] Conquer: if A[mid]=x, return mid if A[mid]x, return A[1..mid-1] for next iteration Combine: just return the result (key: can reduce the array to it's half for the next iteration) BINARY_SEARCH(A,low,high,key)..

(2021.10.09) 알고리즘 수업들으면서 정리하기 8탄 5주차 내용-2 Quick sort input: sequence of numbers output: permutation (오름차순) Divide-and-conquer approach Divide: Partiton the array into two subarrays(A[p..q-1] and A[q+1..r]) (A[p..q-1] ≤ A[q] < A[q+1..r]) Conquer: Sort the two A[p..q-1] and A[q+1..r] by recursive calls to quick sort Combine: no work is needed to combine them(subarrays are already sorted) a pivot x..

(2021.10.09) 알고리즘 수업들으면서 정리하기 7탄 5주차 내용인데 이해하는데 오래걸림.. Maximum-subarray problem