LCS (1) 썸네일형 리스트형 [Baekjoon] 백준 9251번: LCS (JAVA) 문제 9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net [ 문제 풀이 ] LCS는 DP를 활용하여 풀 수 있습니다. DP의 가장 큰 특징은 DP 배열의 값들이 모두 답이어야 한다는 것입니다. 즉, 미리 구해둔 답을 이용해서 다음에 올 답을 계산하는 것입니다. 이 문제에서 각 문자열의 길이를 구하여 dp[][] 이차원 배열을 만들면, 아래 그림과 같습니다. 위의 2차원 배열을 순회하면서 각 위치에서 문자를 비교하여 최대로 겹치는 순열을 찾아 개수를 넣어주면 됩.. 이전 1 다음
