(23.03.31) algorithms S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2008) 책 읽고 정리하기 http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf 정리한 내용 6.5 chain matrix multiplication chain matrix muliplication - 행렬 곱셈 연산에서 곱셈 순서를 다르게 하면, 곱셈 cost도 달라지는데 최소의 cost로 곱셈 연산을 할 수 있도록 하는 방법을 dynamic programming 알고리즘을 통해서 알아낼 수 있다. - 아래와 같이 A, B, C, D 행렬의 곱셈 순서를 다르게 하면 cost가 다르다. - T..
(23.03.30) algorithms S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2008) 책 읽고 정리하기 http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf 정리한 내용 6.4 Knapsack 예전에 수업들으면서 정리했던 내용: https://hey-stranger.tistory.com/140 Knapsack - 최대 무게가 정해져있는 배낭 안에 value가 최대가 되도록 물건을 담는 방법을 찾는 문제이다. - knapsack은 중복을 허용하여 물건을 선택하는 경우와 중복을 허용하지 않고 물건을 선택하는 경우로 나누어 생각해 볼 수 있다. knapsack with re..
(23.03.29) algorithms S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2008) 책 읽고 정리하기 http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf 정리한 내용 6.3 Edit distance Edit distance - edit distance: 어떤 두 단어(문자열)가 같아지도록 하기 위해 수행해야하는 연산의 수 (minimum number of edits) - 예를 들어 edit distance를 해결한 예시를 살펴보면 아래와 같다. - edit distance by dynamic programming - edit distance algorithm by ..
(23.03.29) algorithms S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2008) 책 읽고 정리하기 http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf 정리한 내용 6.1 Shortest paths in dags, revisited 6.2 longest increasing subsequences Dynamic Programming - dynammic programming의 핵심은 문제를 한 번만 풀도록 하는 것이다. - 하나의 problem을 sub-problem으로 계속해서 쪼개고, 가장 작은 sub-problem부터 해결함으로써 더 큰 sub-problem을 ..
(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.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단계