동적계획법
-
[동적계획법/Dynamic Programming]LCS 문제(최장 공통 부분 수열) 파이썬 코드알고리즘 2020. 12. 20. 21:28
동적 계획법에 대한 자세한 내용 : 2020/12/13 - [알고리즘] - Dynamic Programming (동적 계획법) what ia LCS? Longest Common Subsequence 는 의 subsequence이다. 는 와 의 common subsequence이다. Longest common subsequence? common subsequence들 중 가장 긴것. 는 와 의 LCS이다. 1. optimal substructure x=, yj=, LCS z에 대해서 마지막 부분에 대응하는 값을 떼고 생각할 수 있다. 이런식으로 작은 문제로 쪼갤 수 있다. 2. recursive x1 x2 ... xi-1 xi y1 y2 y3 ... yj-1 yj case1. xi=yi 이므로 그 이전 문..
-
Dynamic Programming (동적 계획법)알고리즘 2020. 12. 13. 00:55
문제 해결 방법의 종류 brute-force approach : 모든 경우에 대해서 다 계산하고 가장 좋은것을 택하는 방법. n이 커지면 너무 오래걸려 실행 불가능하다. divide and conquer approach dynamic programming approach greedy approach Dynamic Programming(DP) 주어진 문제를 하위문제로 나누어서 해결한다. 하위 문제가 서로 연관이 있을 때 사용 (divide and conquer은 서로 연관이 없을 때 사용) optimization problem(최적해를 구할 때) 를 풀 때 사용 (최적화문제 : 답이 여러개인 문제에서 가장 좋은 답을 찾는 문제 ex. 최단경로 문제) 모든 하위 문제를 풀고 그 결과를 저장해두어 그 결과를 ..