[백준 9251][DP] LCS

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 출처: https://www.acmicpc.net/problem/9251    점화식 dp[i][j]: 수열1 i까지, 그리고 수열 j 까지 최장 공통 부분 수열 길이   수열 ACAYKP, CAPCAK에 대해 점화식을 2차원 배열로 표현하면 다음과 같다. 원소 하나에 대해 3가지 방향으로부터 영향을 받아 값이 정해진다.  특징LCS 기본 문제 점화식 루프를 돌때 배열의 범위를 벗어나지 않게 조심해야 한다. 따라서 i 또는 j가 0인 경우는 따로 로직으로 처리해줄 수..
CS/알고리즘 풀이 2024. 6. 27. 16:23
1