[백준][C#] 9251 LCS - 골드5

문제 보기

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

9251번: LCS

 

문제                           

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

 

 

입력                          

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

 

 

출력                          

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

 

 

풀이방법                 

LCS 알고리즘을 찾아보고도 이해가 바로 되지 않아서 헤멨던 문제다.

복습할 겸 내가 이해한 LCS 알고리즘과 풀이방법을 정리해보겠다.

 

 

일단 풀이 자체는 놀랍도록 간단하니

걱정 할 필요는 없다.

 

for(int i = 0; i <= str1.Length; i++)
{
	for(int j = 0; j <= str2.Length; j++)
	{
		if(i == 0 || j == 0)
		{
			dp[i, j] = 0;
            		continue;
		}


		if(str1[i - 1] == str2[j - 1])
		{
			dp[i, j] = dp[i - 1, j - 1] + 1;
		}
		else
		{
			dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]);
		}
	}
}

 

그러나 정말 똑똑한 사람이 아닌 이상

코드를 보고 왜 이렇게 되는데? 라고

생각할 것이다. (내가 그랬다...)

 

이제 그 이유를 알아보자...

 

 

우선 최장 공통 부분 수열은 문자가 붙어있을 필요가 없다.

ACAYKP
CAPCAK

예제의 답 4는

ACAYKP
CAPCAK

 

이렇게 도출되었을 것이다.

 

이 문자열을 보기 좋게 표로 옮겨보자.

 

	A	C	A	Y	K	P
C
A
P
C
A
K

 

그저 문자열의 공통되는 부분을 표기해본 표이다.

 

다음은 이 표에 조금 다른 규칙을 적용하여 숫자로 채워보겠다.

 

예를 들어 위 표에서 맨 첫 번째로 색칠된 칸인 (A, A)의

가로 줄인 "A"와

세로 줄인 "CA"의

최장 공통 부분 수열의 길이가 얼마인지 나타내겠다는 것이다.

답은 1일 것이고,

다음으로 색칠된 칸인 (C,C)는 "AC"와 "CAPC"의 최장 공통 수열이니 2일 것이다.

 

 

	A	C	A	Y	K	P
C	0	1	1	1	1	1
A	1	1	2	2	2	2
P	1	1	2	2	2	3
C	1	2	2	2	2	3
A	1	2	3	3	3	3
K	1	2	3	3	4	4

 

이해가 잘 되지 않으면,

천천히 한 칸씩 문자열을 대조해보자.

 

자 이제 이 표에서 규칙을 찾아내면 dp로 문제를 풀이할 수 있다.

 

같은 문자가 만나는 칸에서 숫자가 더해지고

이후 칸(오른쪽, 아래쪽)으로 숫자가 유지되는 것이 보인다.

// 이번 칸에서 문자가 같으면
if(str1[i - 1] == str2[j - 1])
{
	// 왼쪽 윗 칸에서 1을 더하자.
	dp[i, j] = dp[i - 1, j - 1] + 1;
}
else
{
	// 다를 경우 왼쪽 칸이나 윗 칸에서 계승 (더 큰 쪽)
	dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]);
}

 

왜 dp[i, j] = dp[i - 1, j - 1] + 1인가?

왼쪽 칸이나

윗 칸에서 1을 더하면 안되는가?

 

반례는 아래와 같다.

ACC의 경우와

ABC의 경우...

 

	A	C	C
A	1	1	1
B	1	1	1
C	1	2	2

 

왼쪽 칸에서 1을 더해나갔다면 3이라는 오답이 나왔을 것.

 

"AC" 라는 문자열과 "AB"라는 문자열에서 서로 "C"라는 문자가 추가된 경우라고 이해하면 좋을 것 같다.

 

if(i == 0 || j == 0)
{
    dp[i, j] = 0;
    continue;
}

 

이 부분은 dp를 적용하기 위한 버퍼라고 볼 수 있다.

 

 

 

 

아래 게시글이 LCS 알고리즘을 이해하는 데에 도움이 제일 많이 되었다.

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

 

 

전체 코드

using System;

namespace BackjoonCodingTest
{
    internal class Program
    {
        static void Main(string[] args)
        {
            using var reader = new System.IO.StreamReader(Console.OpenStandardInput());
            using var print = new System.IO.StreamWriter(Console.OpenStandardOutput());

            string str1 = reader.ReadLine();
            string str2 = reader.ReadLine();

            int[,] dp = new int[str1.Length + 1, str2.Length + 1];
            
            for(int i = 0; i <= str1.Length; i++)
            {
                for(int j = 0; j <= str2.Length; j++)
                {
                    if(i == 0 || j == 0)
                    {
                        dp[i, j] = 0;
                        continue;
                    }


                    if(str1[i - 1] == str2[j - 1])
                    {
                        dp[i, j] = dp[i - 1, j - 1] + 1;
                    }
                    else
                    {
                        dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]);
                    }
                }
            }

            print.WriteLine(dp[str1.Length, str2.Length]);

            reader.Close();
            print.Close();
        }
    }
}