[PS] BOJ_9251

BOJ_9251

💡 생각하자

Dynamic Programming(동적 계획법)의 개발절차
1. 재귀 관계식(recursive property) 세우기
2. 상향식 방법(bottom-up)으로 답 구하기

주어진 두 문자열을 X = $x_{1}x_{2}⋯x_{n}$, Y = $y_{1}y_{2}⋯y_{m}$으로 둔다.
LCS(i, j)는 X$_{i}$ = $x_{1}x_{2}⋯x_{i}$와 Y$_{j}$ = $y_{1}y_{2}⋯y_{j}$ 사이의 LCS 길이 값을 의미한다.
(1<=i<=n, 1<=j<=m)

다음으로, 두 문자열의 마지막 문자에 대해 생각해보면, 2가지 경우의 수가 존재한다.

1. x$_{i}$ = y$_{j}$

마지막 문자가 서로 같으므로, LCS에 포함시켜야 한다.
-> LCS(i, j) = LCS(i-1, j-1) + 1

2. x$_{i}$ ≠ y$_{j}$

이때는 또 2가지 경우로 나눌 수 있다.

2-1) x$_{i}$는 포함, y$_{j}$는 제외
-> LCS(i, j) = LCS(i, j-1)

2-2) x$_{i}$는 제외, y$_{j}$는 포함
-> LCS(i, j) = LCS(i-1, j)

그러므로 2-1, 2-2 중에서 큰 값을 LCS(i, j)에 저장해주면 된다.

재귀 관계식
LCS(i, j) = LCS(i-1, j-1) +1 (x$_{i}$ = y$_{j}$)
LCS(i, j) = maximum(LCS(i, j-1), LCS(i-1, j)) (x$_{i}$ ≠ y$_{j}$)

💻 구현하자

• LCS를 계산하는 함수

void calLCS() {
	for (int i = 1;i <= strlen(s1);i++) {
		for (int j = 1;j <= strlen(s2);j++) {
			if (s1[i-1] == s2[j-1])
				LCS[i][j] = LCS[i - 1][j - 1] + 1;
			else
				LCS[i][j] = maximum(LCS[i - 1][j], LCS[i][j - 1]);
		}
	}
}

• 초기 호출문

// init
for (int i = 0;i <= len1;i++)
	LCS[i][0] = 0;

for (int i = 0;i <= len2;i++)
	LCS[0][i] = 0;

calLCS(); 

💥 발전하자

• 에러 및 해결

1. 처음에는 문자열의 최대 길이가 1000이라는 조건을 보고 #define MAX 1000 을 해주었다.
   하지만, fgets()는 개행문자('\n')에 도달할 때 까지 문자를 읽기 때문에, s1의 경우 'string\n\0'의 형태로 구성된다.
   그래서 문자열의 최대 길이를 1000+2를 해주어야 최대길이 문자열을 받을 때 오류가 발생하지 않는다.

📌 참고하자

나의 코드(Github)
한국외대 신찬수 교수님의 LCS 강의영상