[Gold V] LCS - 9251문제 링크분류다이나믹 프로그래밍, 문자열문제 설명LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.입력첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.출력첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다. 풀이 및 코드풀이는 아래에 LCS 알고리즘과 함께 정리해두었습니다.[Computer Science/Algorithm] - 최장 공통 부분 수열 (LCS; Longest common subsequ..

최장 공통 부분 수열 (LCS; Longest common subsequence problem)부분 수열(subsequence)은 시퀀스의 원소를 순서를 유지한 채 몇 개를 골라낸 것을 말한다.최장 공통 부분 수열은 두 시퀀스(문자열 또는 배열)간 공통된 부분 수열 중 가장 긴 것을 찾아내는 문제이다. 예시) 문자열 `ABCBDAB`와 `BDCABA`의 LCS는 `BCBA`이다. 보통 LCS 문제를 해결하기 위해 주로 동적 계획법(DP;Dynamic Programming)을 사용한다.이 글에서도 DP를 이용한 LCS 알고리즘을 설명하고자 한다.  LCS 길이 구하기동작 원리동적 계획법은 문제를 작은 부분 문제로 나누고 그 해를 이용해서 전체 문제를 해결하는 방식이다.때문에 문제 정의와 점화식, 초기 조건..