백준 9252, LCS 2 - DP

김은성·2022년 4월 22일
1

알고리즘

목록 보기
104/104

https://www.acmicpc.net/problem/9252





이전 시리즈 문제 - 백준 9251, LCS

  • 본 문제는 이전 문제 LCS에 출력 값 LCS 문자열 자체를 구하는 과정이 추가됨
    • 이전 문제 LCS: 최대 LCS의 문자열 길이(정수 값)만을 출력

  • 본 문제 의도 - 점화식에 따라 채워진 DP 배열에서,
    "DP 배열을 채우는 역과정을 수행하여 목표 값을 찾아라."

  • 백준 9251, LCS 해설



오답 발생한 풀이 - DP 배열 메모리 초과

1. 아이디어

1) DP 배열 정의: String[][] dp

  • dp[i][j]: str1[i] 문자까지와 str2[j] 문자까지에 대한 LCS 문자열
  • 출력, LCS 문자열: dp[str1.length()][str2.lenength()]

2) 규칙 및 점화식

  • 2중 for문으로 str1의 각 문자, str2의 각 문자 확인 비교

str1[i] 문자 != str2[j] 문자인 경우

  • dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    => 윗 칸 or 왼쪽 칸 중, 길이가 더 큰 문자열

str1[i] 문자 == str2[j] 문자인 경우

  • dp[i][j] = dp[i-1][j-1] + str1[i]
    => dp[i-1][j-1]의 문자열에 동일 문자 str1[i] 추가



2. 자료구조

  • String[][] dp: DP 배열

메모리 확인

  • 대략 최대 (str1 최대 길이) x (str2 최대 길이) x (LCS 문자열 최대 길이) byte
    => 10^3 x 10^3 x 10^3 byte = 10^9 byte = 10^3 MB >> 256 MB
    => 메모리 초과 !!!



3. 시간 복잡도

  • DP 배열 채우기: O(len1 x len2) (두 문자열 길이의 곱)
    => 문자열 길이 최대값 대입: (10^3)^2 = 10^6 << 1억



코드

import java.io.*;

public class Main_Memory_Over {
	static String str1, str2;
	static String LCS;
	static String[][] dp;

	static void solution() {
		for (int i = 1; i <= str1.length(); i++) {
			for (int j = 1; j <= str2.length(); j++) {
				// str1[i] 문자와 str2[j] 문자가 같은 경우
				if (str1.charAt(i-1) == str2.charAt(j-1)) {
					if (dp[i-1][j-1] != null)
						 dp[i][j] = dp[i-1][j-1] + str1.charAt(i-1);
					else
						dp[i][j] = String.valueOf(str1.charAt(i-1));
				}
				// str1[i] 문자와 str2[j] 문자가 다른 경우
				else {
					dp[i][j] = getMaxString(dp[i-1][j], dp[i][j-1]);
				}
			}
		}

		LCS = dp[str1.length()][str2.length()];
	}

	static String getMaxString(String s1, String s2) {
		if (s1 == null)
			return s2;
		else if (s2 == null)
			return s1;

		return s1.length() > s2.length() ? s1 : s2;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in)
		);

		str1 = br.readLine();
		str2 = br.readLine();

		// [0]행 [0]열은 패딩, [1][1] ~ [len1][len2] 사용
		dp = new String[str1.length() + 1][str2.length() + 1];
		solution();

		StringBuilder sb = new StringBuilder();
		if (LCS != null) {
			sb.append(LCS.length()).append("\n")
					.append(LCS);
		}
		else {
			sb.append("0");
		}
		System.out.println(sb);
	}
}





정답 풀이

1. 아이디어

1) DP 배열 정의: int[][] dp

  • dp[i][j]: str1[i] 문자까지와 str2[j] 문자까지에 대한 LCS 길이
  • 출력, 최종 LCS 길이: dp[len1][len2]

2) 규칙 및 점화식

  • 2중 for문으로 str1의 각 문자, str2의 각 문자 확인 비교

str1[i] 문자 != str2[j] 문자인 경우

  • dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    => 윗 칸 or 왼쪽 칸 중, 더 긴 LCS 길이

str1[i] 문자 == str2[j] 문자인 경우

  • dp[i][j] = dp[i-1][j-1] + 1
    => dp[i-1][j-1]의 문자열에 동일 문자 str1[i] 추가
    => 추가된 동일 문자로 인해, LCS 길이 + 1 늘어남

최종 LCS 문자열 구하기

  • DP 배열(각 상태에서의 LCS 길이)을 채운 순서의 역순으로 추적
    => LCS 문자열이 역순으로 저장됨 (결과 값을 역순으로 출력)

  • 마지막 칸 dp[len1][len2]에서 시작하여, 거슬러 올라가면서 확인

① 현재 칸과 윗 칸 or 왼쪽 칸이 LCS 길이 같은 경우

  • 해당 윗 칸 or 왼쪽 칸으로 이동

DP 배열을 채우는 과정에서,
"LCS 길이에 변화가 없다" == "LCS 문자열에 추가된 동일 문자가 없다"

② 현재 칸과 윗 칸, 왼쪽 칸이 LCS 길이 다른 경우 (LCS 길이 감소하는 경우)

  • 현재 칸에 해당하는 문자를 추가하고, 왼쪽 위 대각선 칸으로 이동

"현재 칸에 비해 윗 칸, 왼쪽 칸의 LCS 길이가 줄어들었다"
== DP 배열을 채우는 과정에서, "이전 윗 칸 or 왼쪽 칸으로부터 LCS 문자열에 추가된 동일 문자가 있다"



2. 자료구조

  • int[][] dp: DP 배열
    ① 자료형: dp 배열 원소 최대값 10^3 << 21억 이므로, int 가능
    ② 메모리: 최대 4 x 10^3 x 10^3 byte = 4 x 10^6 byte = 4 MB



3. 시간 복잡도

  • DP 배열 채우기: O(len1 x len2) (두 문자열 길이의 곱)
    => 문자열 길이 최대값 대입: (10^3)^2 = 10^6 << 1억



코드

import java.io.*;

public class Main {
	static String str1, str2;
	static int maxLength;			// 출력, LCS 최대 길이
	static StringBuilder LCS = new StringBuilder();	// 출력, LCS 문자열
	static int[][] dp;

	static void solution() {
		// 1. DP 배열 채우기
		for (int i = 1; i <= str1.length(); i++) {
			for (int j = 1; j <= str2.length(); j++) {
				// str1[i] 문자 == str2[j] 문자인 경우
				if (str1.charAt(i-1) == str2.charAt(j-1))
					dp[i][j] = dp[i-1][j-1] + 1;
				// str1[i] 문자 != str2[j] 문자인 경우
				else
					dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
			}
		}

		maxLength = dp[str1.length()][str2.length()];

		if (maxLength == 0)
			return;

		// 2. DP 배열(각 LCS 길이)에서 최종 LCS 구하기
		// 마지막 칸 dp[len1][len2]에서 시작하여, 거슬러 올라가면서 확인
		int i = str1.length();
		int j = str2.length();

		while (i != 0 && j != 0) {
			// 현재 칸과 윗 칸 or 왼쪽 칸이 LCS 길이 같은 경우
			if (dp[i][j] == dp[i-1][j])
				i--;
			else if (dp[i][j] == dp[i][j-1])
				j--;
			// 현재 칸과 윗 칸, 왼쪽 칸이 LCS 길이 다른 경우 (LCS 길이 감소하는 경우)
			else {
				LCS.append(str1.charAt(i-1));
				i--;
				j--;
			}
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in)
		);

		str1 = br.readLine();
		str2 = br.readLine();

		// [0]행 [0]열은 패딩, [1][1] ~ [len1][len2] 사용
		dp = new int[str1.length() + 1][str2.length() + 1];
		solution();

		System.out.println(maxLength);
		if (maxLength > 0)
			System.out.println(LCS.reverse());		// 역순
	}
}
profile
Silver Star

0개의 댓글