[C++][BOJ 백준]9251_LCS
Algorithm/BaeKJoon

[C++][BOJ 백준]9251_LCS

문제 번호

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

 

9251번: LCS

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

www.acmicpc.net

 

 

알고리즘 분류

 DP

 

문제 풀이

 Int형 2차원 배열을 사용한 LCS 풀이이다.

2차원 배열의 0항은 첫번째 스트링, 0열은 두번째 스트링 이라고 본다.

 

  C A Y K P
C            
A            
P            
C            
A            
K            

이런 모양이다. 물론 2차원 배열에 실제로 저 값들이 들어가있는것은 아니다. 설명을 위해서 보여진 예시이다.

실제 2차원 배열은 아래와 같은 상태이다.

0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

 

 이후 2차원배열을 1,1(표에서 빨간색.) 부터 순회 하면서 값을 집어 넣어야 한다. 순회는 가로방향으로 진행하였다.

우리가 탐색할 부분은 표에서 초록색 부분이다.

 이때 값을 집어넣는 방법은 해당칸의 x좌표와 y좌표를 이용한다. 첫번째 표에서 보았듯, x좌표는 첫번째 스트링에 매칭되고, y좌표는 두번째 스트링에 매칭된다.

 즉, x가 3이라면 "ACAYKP"에서 3번 인덱스인 'Y' 를 가리키게 되는것이다.

마찬가지로 y가 2라면 "CAPCAK"에서 'P'를 가리키게 된다.

 우리는 이러한 사실을 이용하여 탐색하는 칸의 좌표를 확인하여 x좌표에 해당하는 알파벳과 y좌표에 해당하는 알파벳이 같으면 현재칸의 좌표의 왼쪽 대각선위( y-1, x-1) 에 해당하는 값에 1을 더한 값을 현재칸의 값으로 삼는다.

if (A[i - 1] == B[j - 1])
	LCS[i][j] = LCS[i - 1][j - 1] + 1;

 x좌표에 해당하는 알파벳과 y좌표에 해당하는 알파벳이 다르다면 현재 좌표의 윗칸과 왼쪽칸을 비교하여 더 큰값을 현재칸의 값으로 삼는다.

else
	LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1]);

 

전체 코드 : 

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int LCS[1001][1001];
string A, B;

void sol(int N, int M)
{
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			if (A[i - 1] == B[j - 1])
				LCS[i][j] = LCS[i - 1][j - 1] + 1;
			else
				LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1]);
		}
	}

	cout << LCS[N][M] << endl;
}

int main()
{
	 cin >> A >> B;
	 sol(A.length(), B.length());

	return 0;
}

특이사항

1. 서식 처음 적용해봄.

2. 표 처음 사용해봄.