[백준] 9251번 - LCS (C++)

9251번: LCS

문제

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

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

 

입력

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

 

 

출력

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

풀이과정

이 알고리즘 문제에 경우에는 LCS(Longest Common Subsequence, 최장 공통 부분 수열) 라고 불리는 알고리즘 개념을 알고
다이나믹 프로그래밍으로 접근을 해야 문제를 해결 할 수 있는 문제였었다.

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

그래서 위와 같은 글을 참고하여 문제풀이를 진행하게 되었다.

LCS 알고리즘의 기본 개념은 

if ( a[i] == b[i] )
	alpha[i][j] = alpha[i-1][j-1] + 1;
else
	alpha[i][j] = std::max(alpha[i - 1][j], alpha[i][j - 1]);

위와 같은 식으로 진행이된다.

1. a와 b의 알파벳을 서로 비교한다.
2. 비교한 값이 서로 같다면 해온 과정중에 가장 큰 값에 + 1 해준다.
3. 비교한 값이 서로 다르다면 다른 대조군 중 가장 큰값을 가져온다.

위와 같은 식의 알고리즘 풀이과정을 반복하면 LSC 알고리즘 형식이 된다고 생각을하면 된다. ( 자세한 내용은 위에 링크 확인 )

code

#include <iostream>
#include <algorithm>
#include <string>

int		alpha[1001][1001];

int		main(void)
{
	std::string	a, b;
	int		aLen = 0, bLen = 0;

	std::cin >> a >> b;
	aLen = a.length();
	bLen = b.length();
	for (int i = 1; i <= aLen; i++) {
		for (int j = 1; j <= bLen; j++) {
			if (a[i - 1] == b[j - 1])
				alpha[i][j] = alpha[i - 1][j - 1] + 1;
			else
				alpha[i][j] = std::max(alpha[i - 1][j], alpha[i][j - 1]);
		}
	}
	std::cout << alpha[aLen][bLen];

	return (0);
}

 

후기

dp는 풀어도 풀어도 어렵다는 생각이 자꾸 든다.

볼때마다 새롭고 짜릿하다.