[알고리즘/자바] 백준 9252번 - LCS 2

9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 처음에 LCS를 푸는 알고리즘을 모르고 접근했다가 한참 고생했다. 아래는 처음에 접근한 방식. 입력으로 문자열 2개가 주어지는데 이를 n1, n2라고했다. n1의 첫번째 문자를 잡고 n2를 처음부터 순회한다. n2에 일치하는 문자가 있다면 정지하고 n1의 두번째 문자를 잡고 n2를 정지한 부분에서 부터 시작한다. 이 방식으로 n2도 똑같이 진행한다. 위에서 생각한 방식으로 구현한 소스코드. 2중 for문을 사용했다..

2021.01.28