유튜브의 Chan-Su Shin 교수님 강의중 알고리즘 - 동적계획법 - LCS 문제 영상을 보고 정리한 내용입니다.
이해가 어려웠던 분들은 꼭 참고해보세요
LCS 백준 문제의 풀이를 봤을 때 이해하기 어려웠던 부분
(1) 2차원 테이블 정의도 이해하기 어려웠고
(2) [i-1][j-1] 부분도 이해하기가 어려웠다.
2차원 배열
LCS 데이터를 표현할 수 있는 방법이 2차원 배열이었다.
 |
0 | B | D | C | A | B | A |
| 0 | |||||||
| A | |||||||
| B | |||||||
| C | |||||||
| B | |||||||
| D | |||||||
| A | |||||||
| B |
위 표는 문자열 2가지를 나타내는 2차원 배열이다.
여기서 반드시 짚고 넘어가야 할 부분!
1. 위의 표에서 각 문자 1개는 가장 마지막 문자를 나타낸다.
2. 그리고 채워야 하는 빈 칸은, 해당 문자까지의 문자열 LCS를 의미한다.
예를 들어, ABCBDA와 BDCABA의 LCS를 비교해야 한다.
이때, C 의 의미는 가장 마지막 문자가 C 라는 것을 의미하며, 그 아래 빈 영역이 BDC까지의 문자열 LCS를 나타낸다.
표에서도 알 수 있듯, 가장 마지막 문자가 비교의 기준이 된다는 것을 반드시 기억해야 한다.
이를 일반화하면 다음과 같이 나타낼 수 있다.
ABCBDA와 BDCABA의 LCS를 비교
ABCBDA를 X(i) BDCABA를 Y(j)라고 하면, X(n)과 Y(m)은 각각 연속된 문자열을 의미한다.
ABCBDA중 A는 X(1)이고, BDCABA중 B는 Y(1)이며
ABCBDA중 AB는 X(2)이고, BDCABA중 BD는 Y(2)를 의미한다.
...
ABCBDA중 ABCBD는 X(5)이고, BDCABA중 BDCA는 Y(4)를 의미한다.
그렇다면, X(0)과 Y(1)은?
ABCBDA중 아무것도 비교 대상으로 두지 않는 것이 X(0)이고, BDCABA중 B가 Y(1)을 의미한다.
빈 문자열과 B.
즉 비교대상이 없기 때문에 X(0)과 Y(1), X(0)과 Y(2), ..., X(0)과 Y(i)의 공통 부분이 전혀 없다. 따라서 0행과 0열은 모두 0으로 채워지게 되었던 것.
그러면 대략 테이블이 이해가 된다.
LCS(n, m)의 의미는 X(n)과 Y(m)의 LCS비교라는 것.
테이블만 놓고 보았을 때는 직관적으로 파악하기 어려웠는데, 이제 둘 간의 관계가 보이기 시작한다.
[i-1][j-1]
이제 점화식으로 넘어가는 부분인데
왜 [i-1][j-1]을 점화식에서 필요로 하는 걸까? (가장 궁금했었다)
그러나 이 내용은 부수적인 내용이기 때문에, 여기에 집중하지 말고
마지막 문자에 집중해야 한다.
크게 봤을때 X(n)과 Y(m)의 비교는
비교하려는 가장 마지막 문자가
(1) 서로 일치 하는가?
(2) 일치하지 않는가?
두 부분으로 나뉜다. 점화식을 구분하는 지점!
결국 둘중 하나이다. X(n)과 Y(m)의 가장 마지막 문자가 일치하는지 아닌지인데,
가장 마지막 문자가 일치하면, 가장 마지막 문자를 제외한 나머지 문자열의 LCS에 1을 더하면 되기 때문이다.
예를 들어,
ABCBDA와 BDCABA에서
ABCBD와 BD이면 마지막 D가 같다.
따라서 ABCB와 B에서의 LCS인 B 즉 1에 + 1을 해주면 되는 것. 1개(=B) + 1개(=D)
그렇다면 가장 마지막 문자가 일치하지 않는다면?
X(n-1)과 Y(m)을 비교한 LCS 값과, X(n)과 Y(m-1)을 비교한 LCS값 중 큰 값을 선택하면 된다.
예를 들어,
ABCBDA와 BDCABA에서
ABCB와 BDC이면 마지막 문자가 각각 B와 C로 다르다.
따라서
ABCB와 BD에서 LCS인 B 즉 1개,
ABC와 BDC에서 LCS인 BC 즉 2개를 비교하면
B와 BC중 BC가 2개로 더 길기 때문에 2를 선택하면 된다.
위의 점화식 내용을 식으로 나타내면 다음과 같다.
LCS[i,j] = LCS[i-1][j-1] +1 (가장 마지막 문자가 같은 경우)
max(LCS[i][j-1], LCS[i-1][j]) (가장 마지막 문자가 다른 경우)
이를 2차원 배열로 빠르게 본다면 다음과 같다.
비교하려는 문자가 빨간색으로 색칠된 영역[i,j]
(1) 비교하려는 문자가 빨간색으로 색칠된 영역[i,j]이 일치 한다면, 파란색 영역[i-1][j-1]에 있는 값 +1
(2) 비교하려는 문자가 빨간색으로 색칠된 영역[i,j]이 불일치 한다면, 연두색 영역 두개인 [i][j-1] 와 [i-1][j] 중 큰 값을 선택
LCS는 2차원 배열로 접근하고, 가장 마지막 문자인 [i][j] 그리고 그 직전 LCS인 [i-1][j-1] [i-1][j] [i][j-1]과의 관계를 생각해야 했다.