(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.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..