Algorithms과 자료구조/동적 프로그래밍, 그리디 알고리즘2 LCS(Longest Common Subsequence) 최장 공통 부분 수열 최장 공통 부분 수열 (Longest Common Subsequence) 문제란? 주어진 여러개의 수열 모두 부분수열이 되는 수열중 가장 긴 것을 찾는 문제이다. 이 문제와 아래 최장공통 부분 문자열 문제와 혼동하면 안된다. 최장 공통 부분 문자열(Longest Common Substring) 문제란? 주어진 여러개의 문자열 모두 부분수열이 되는 문자열 중 가장 긴 문자열을 찾는 문제 예시 가나다라마바사 가하나카마바사 LCSubsequence 가나다라마바사 가하나카마바사 LCSubstring 가나다라마바사 가하나카마바사 LCS 문제는 더 작은 '부분문제'로 나뉠 수 있고 이것을 반복해 더 간단한 부분문제로 쪼갤 수 있다. 즉 동적 프로그래밍 문제풀이기법으로 접근될 수 있다. 부분문제는 수열이 짧아질 수록.. 2021. 11. 26. DP( Dynamic Programing) 동적프로그래밍 DP 큰 문제를 한번에 해결하기 힘들 때 작은 여러 개의 문제로 나누어서 푸는 기법으로 작은 문제들을 매번 재계산 하지 않고 값을 저장해두었다가 재사용하는 기법이다. 조건 Problem이 더 작은 Subproblem으로 쪼개질 수 있어야 한다. Subproblem 의 솔루션으로 더 큰 Subproblem의 솔루션을 구할 수 있어야 한다. Subproblem이 겹칠때(memorization을 통해 필요한 계산수를 줄일 수 있다) 백준 피보나치 수열 2 #bottom up방식 fib_array = [0, 1] def fib_dp(n): if n==0: return 0 elif n==1: return 1 for i in range(2, n+1): num = fib_array[i-2]+fib_ar.. 2021. 11. 25. 이전 1 다음
