내일은 알고리즘

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

LCS 2번을 풀어보겠습니다.

혹시 LCS에 대한 이해가 부족하시거나, LCS 1번 문제를 아직 풀지 않은 분은

https://nodingco.tistory.com/9

이 글을 확인해주시면 감사하겠습니다.

문제는 LCS 1번과 아주 유사합니다. 하지만 단순히 LCS의 길이를 구하는 것 뿐 아니라 LCS의 내용까지 구해야합니다.

쉽게 생각하면 그저 LCS를 구하는 기존의 과정에 더해 여태까지의 String을 저장해도 될 것 같지만, String이 메모리나 연산시간을 많이 잡아먹는걸 감안하면 살짝 위험해 보입니다.

그래서 LCS를 구했던 과정을 역산해서 LCS를 알아내 보겠습니다.

예제의 풀이과정이 기록되는 DP 배열을 실제 표로 나타내어 봅시다. (실제로는 계산의 편의를 위해 좌측과 상단에 0이 들어간 배열이 더 존재합니다.)

정답 LCS인 ACAK는 위와같은 과정을 통해 구해졌다는걸 알 수 있고

최종 정답이 위치한 DP[L2][L1]의 값부터 역순으로 찾아 가는 방법도 알 수 있습니다.

위, 좌측, 대각선 좌상방향 세개의 값을 비교하여

나와 같은 값이 있으면 그 쪽으로, 나와 값이 전부 다를땐 좌상방향으로 이동하면서

그때의 Character를 역순으로 담으면 자연스럽게 답이 찾아집니다.

Stack을 이용해 역순으로 저장하는 방법을 구현하면, 코드는 아래와 같아집니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		Stack<Character> stack = new Stack<Character>();

		char[] str1 = br.readLine().toCharArray();
		int l1 = str1.length;
		char[] str2 = br.readLine().toCharArray();
		int l2 = str2.length;

		int[][] dp = new int[l2 + 1][l1 + 1];

		for (int i = 1; i <= l2; i++) {
			char C = str2[i - 1];
			for (int j = 1; j <= l1; j++) {
				if (C == str1[j - 1]) {
					dp[i][j] = dp[i - 1][j - 1] + 1;
				} else {
					dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
				}
			}
		}
		sb.append(dp[l2][l1]).append("\n");

		int now = dp[l2][l1];
		int x = l2;
		int y = l1;

		while (isIn(x, y) && now > 0) {
			if (dp[x - 1][y] == now) {
				x--;
			} else if (dp[x][y - 1] == now) {
				y--;
			} else {
				x--;
				y--;
				now--;
				stack.push(str1[y]);
			}

		}

		while (!stack.isEmpty()) {
			sb.append(stack.pop());
		}

		System.out.println(sb);
	}

	static boolean isIn(int x, int y) {
		if (0 < x && 0 < y) {
			return true;
		}
		return false;
	}
}

주의)

LCS가 0일때 아무것도 출력하지 않아야합니다.

탐색 도중 x와 y가 ArrayIndex를 벗어나는걸 주의해주세요.

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

안녕하세요!

오늘부터 LCS(최장 공통부분 수열) 문제 3개를 연속으로 풀어보겠습니다!

부분 수열 문제지만 오늘 가져온 9251번 문제처럼 String을 찾는 유형으로도 나오는데요,

0-1 배낭 문제 (Knapsack Problem)과 더불어서 DP의 대표 유형 격인 문제입니다.

그럼 천천히 풀어보겠습니다.

예제를 기준으로 함께 풀어보겠습니다. 

DP의 풀이방법은 정말 다양하고, Dynamic Programming이란 말 그대로 모든 게 가능하기 때문에 딱 잡아 말할 순 없지만, 분할 정복과 유사하게 문제를 잘게 쪼개어 그 결과를 기억하고 이를 통해 답을 만들어낸다고 볼 수 있습니다.

LCS문제도 같습니다.

ACAYKP를 String1이라고 하고 이걸 기준으로 놓고 아래의 CAPCAK, String2 의 부분수열을 만들어서 비교해보면,

1. C 일때

A-> 0

AC -> 1

ACA-> 1

ACAY ->1

ACAYK ->1

ACAYKP ->1

String2가 C라고 가정했을 때 만들 수 있는 LCS는 길이가 1이라는 사실을 알 수 있습니다.

2. CA 일 때

A->1

AC -> 1   (A도 가능하지만 가독성과 이해를 위해 C를 bold 처리했습니다.)

ACA -> 2

ACAY ->2

ACAYK ->2

ACAYKP ->2 String2가 CA일때 만들 수 있는 LCS는 2의 길이라는 사실을 알 수 있습니다.

3. CAP 일때

A-> 1

AC -> 1

ACA-> 2

ACAY ->2

ACAYK ->2

ACAYKP ->3

두번째 String이 CAP일 때 LCS는 길이가 3입니다.

슬슬 규칙이 보이시나요? 비교하는 String이 길어질 때,

LCS의 값은 이전에 이 길이까지와 비교한 값과 같거나, 이번에 비교하면서 만들어진 현재의 LCS값이거나,

String1의 이번 Character와 String2에 방금 더해진 문자가 같을 때 1이 커집니다.

이걸 코드로 표현해 보면

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main{
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String str1 = br.readLine();
		int l1 = str1.length();
		String str2 = br.readLine();
		int l2 = str2.length();
		
		int[][] dp = new int[l2+1][l1+1];
		
		for(int i = 1; i <= l2; i++) {
			char C = str2.charAt(i-1);
			for(int j = 1; j <= l1; j++) {
				if(C == str1.charAt(j-1)) {
					dp[i][j] = dp[i-1][j-1] + 1;
				}else {
					dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
				}
			}
		}
		System.out.println(dp[l2][l1]);
	}
}

이렇게 나타낼 수 있을것 같네요.

위에서 설명한 것과 같이 String2의 길이를 1씩 늘려가면서 String1과 비교해주고

이번에 비교하는 문자가 같다면 LCS의 값은 이전 비교에서 1만큼 짧았을때의 최댓값 + 1

다르다면 이전 비교에서의 값과 이번 비교에서의 값 중에 큰 값으로 결정됩니다.

대부분의 DP문제는 아이디어를 끌어내기가 어렵지, 풀이 방법만 안다면 구현은 쉬운 경우가 많습니다.

DP를 잘 풀기 위해서는 역시 여러 유형을 경험해 익숙해지고 직접 그려가면서 규칙을 찾아내는 방법 뿐 입니다.

이어서 거의 비슷한 문제인 LCS2도 풀어보겠습니다.