상위문서 : 자료구조
필수참고문서 :
목차
1. 개요
2. 예제
3.1. JAVA로 구현
3.2. C#으로 구현
3.2. C#으로 구현
1.개요
동적 프로그래밍은 어떤 답을 도출하기 위해 전에 구했던 답을 재활용하는 기법이다. 다음 동적 프로그래밍 실제 예제들을 모아보았다.
2. 예제
2.1.연쇄행렬 최소곱셈 문제
2.2. LCS 알고리즘
LCS는 최대 공통 부분 문자열(longest common subsequence)은 문자열 S가 주어졌을 경우 다른 문자 C와 비교하여 C에서 만들 수 있는 최대 길이의 부분 순열을 찾는 것이다.
문자열과 부분 문자열 그리고 부분 순열이 있는데 문자열에서 어떤 부분을 자르면 그것이 부분 문자열 부분 문자열에는 맞는 것이 없는데 글자의 순서 차례대로 있다면 부분 순열이다. 예를 들어 "살어리살어리랏다 청산에 살어리랏다 얄리얄리얄라셩 얄라리 얄라" 에서 "리얄리얄"은 부분 문자열이 되며 "살어얄리"는 부분 순열이 된다.
문자열과 부분 문자열 그리고 부분 순열이 있는데 문자열에서 어떤 부분을 자르면 그것이 부분 문자열 부분 문자열에는 맞는 것이 없는데 글자의 순서 차례대로 있다면 부분 순열이다. 예를 들어 "살어리살어리랏다 청산에 살어리랏다 얄리얄리얄라셩 얄라리 얄라" 에서 "리얄리얄"은 부분 문자열이 되며 "살어얄리"는 부분 순열이 된다.
