코테/Dynamic Programming
-
최장 공통 부분수열 (LCS)코테/Dynamic Programming 2022. 6. 22. 19:57
LCS( Longest Common Subsequence) LCS란 가장 긴 공통의 부분집합을 말한다. 예를 들어 x = "ECADADABRBCRDARA" Y = "ABRACADABRA"라는 변수가 있다면 x와 y의 LCS는 다음과 같다. 부분 수열이기 때문에 문자 사이를 건너뛰어 공통되면서 가장 긴 부분 문자열을 찾으면 된다. 어떤 문자열 X와 Y가 있다고 할 때 Xn = X1X2 . . . Xn(길이를 n으로 갖는 문자열 Xn) Ym = Y1Y2 ... Ym(길이를 m으로 갖는 문자열 Ym) 이라고 하면 우리가 구하고자 하는 것은 X와 Y의 LCS이므로 LCS(Xn,Ym) := (X[0..n]와 Y[0..m]를 사용하여 만들 수 있는 LCS의 길이)의 점화식을 세우면 된다. LCS(n,m)의 경우를 ..
-
동적 계획법(Dynamic Programming)코테/Dynamic Programming 2022. 3. 24. 16:58
Dynamic Programming(동적 계획법) 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상하는 방법 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운, 보텀업)으로 구성됨 Dynamic Programming의 조건 1. 최적 부분 구조(Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 2. 중복되는 부분 문제(Overlapping Subproblem) 동일한 작은 문제를 반복적으로 해결해야 한다. 피보나치수열은 다음과 같은 형태의 수열이며, 다이나믹 프로그래밍으로 효과적으로 계산할 수 ..