LCS(Longest Common Subsequence), 최장 공통 부분 수열

LCS는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 알고리즘이다. 예를들어 ABAB와 AAB에서 답은 AAB인 3이되고, ABCD와 DBCA에서 답은 BC인 2가 된다.

아래는 자바로 작성된 LCS알고리즘이다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.OutputStreamWriter; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new Output...