15-01 동적 계획법

 

아래의 상기 내용은

"이것이 자료구조+알고리즘이다. With C언어"의 도서 내용과 인터넷의 내용을 실습 및 정리한 글입니다.

1.동적 계획법

 1)정의

 -어떤 문제가 여러 단계의 반복되는 부분 문제로 이루어졌을 때 각 단계에 있는 부분 문제의

답을 기반으로 전체 문제의 답을 구하는 방법.

-부분 문제의 답을 구하는 과정에서 별도의 테이블을 생성하고 부분문제를 다시 접하게 될 시

테이블에 꺼내서 활용한다.

 2)과정

 

2.최장 공통 부분 수열(LCS: Longest Common Subsequence)

 1)개요 및 정의

 -부분 수열(Subsequence)이란 수열에서 일부 요소를 제거 한 것을 뜻한다.

 -최장 공통 부분 수열은 두 문자열이 공통으로 가지는 부분 수열 중 길이가 가장 긴 수열을

뜻한다.

2)길이 구하는 점화식

 - 문자열 Xi[X1,X2* * * Xi,],Yj[Y1,Y2,* * *Yj]가  최장 공통 부분 수열의 길이를 구하는 경우 수가 세가지 존재한다.

 -첫째 i와 j중 하나라도 0일 때

 -둘째 xi.yj가 서로 같을 때

  -셋째 xi.y 같지 않고 둘 다 0보다 클 때

  -길이의 값을 테이블 TABLE로 나타낼 수 있고 아래와 같이 점화식이 된다.