Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

27. 동적 계획법과 최단거리 역추적

지금까지는 최솟값, 최댓값, 최단거리만 찾았습니다. 이번에는 실제 최적해와 최단경로를 찾아 봅시다.

Java / Python

4. LCS 2

9252번

LCS를 출력하는 문제

이번 문제는 LCS문제로, LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제입니다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 됩니다.

• Java

import java.io.*;
import java.util.*;

public class Main {  
	static char[] arr1, arr2;
	static int[][] dp;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); 
		StringBuilder sb = new StringBuilder();
        
		arr1 = br.readLine().toCharArray(); 
		arr2 = br.readLine().toCharArray(); 
        
		int len1 = arr1.length;
		int len2 = arr2.length;        
        
		dp = new int[len1 + 1][len2 + 1];
        
		for(int i = 0; i < len1; i++) {
			for(int j = 0; j < len2; j++){
				if(arr1[i] == arr2[j]) { 
					dp[i+1][j+1] = dp[i][j]+1;
				} else{ 
					dp[i+1][j+1] = Math.max(dp[i+1][j], dp[i][j+1]); 
				} 
			}
		}

		bw.write(dp[len1][len2] + "\n");  
		
		Stack<Character> stack = new Stack<>();
		while(len1 >= 1 && len2 >= 1) {
			if(dp[len1][len2] == dp[len1-1][len2]) { // 위
				len1--; 
			} else if(dp[len1][len2] == dp[len1][len2-1]) { // 왼 
				len2--; 
			} else { // 대각선
				stack.push(arr1[len1 - 1]);
				len1--;
				len2--;
			}
		}
        
		while(!stack.isEmpty()) {
			sb.append(stack.pop());
		}
        
		bw.write(sb.toString());        
		bw.flush();
		br.close();
		bw.close();
	}	
}

• Python

import sys
from bisect import bisect_left

arr1 = [0] + list(sys.stdin.readline().strip())
arr2 = [0] + list(sys.stdin.readline().strip())

len1 = len(arr1)
len2 = len(arr2)

dp = [[""] * len2 for _ in range(len1)]

for i in range(1, len1):
    for j in range(1, len2):
        if arr1[i] == arr2[j]:
            dp[i][j] = dp[i - 1][j - 1] + arr1[i]
        else:
            if len(dp[i - 1][j]) > len(dp[i][j - 1]):
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = dp[i][j - 1]

print(len(dp[len1 - 1][len2 - 1]))
print(dp[len1 - 1][len2 - 1])