•
생각해 볼 문제
PPAAP 와 PPPA가 주어져 있다고 한다면,
P P A A P
0 0 0 0 0 0
P 0
P 0
P 0
A 0
먼저 벡터의 모든 값을 0으로 초기화 합니다. 문자열의 크기보다 1만큼 행과 열이 큰 이유는 예외없이 일관성 있는 논리를 적용하기 위해서 입니다.
→ 1 round
(round란 PPPA를 순서대로 PPAAP에서 LCS 조사한 순서. 따라서 round 4까지 있음 (PPPA의 길이))
P P A A P
0 0 0 0 0 0
P 0 1 1 1 1 1
P 0
P 0
A 0
1 round에서는 PPPA 중에 첫 번째 P를 PPAAP 내에서 계산합니다. 계산한다는 의미는 LCS(최장 공통 부분 수열)를 구하기 위해 메모리에 저장해 놓은 값을 이용하여 현재 자신의 위치에서의 LCS를 구하는 것을 의미합니다. PPAAP에서 P를 조사하는데, 현재 조사중인 P와 똑같은 P를 만난 순간 그 자리의 값을 어떤 값으로 바꿀지가 문제입니다. 1 round에서는 직관적이지 않으므로, 2 round로 넘어갑니다.
→ 2 round
2 round에서는 PPPA중에 두 번째 자리에 있는 P를 가지고 PPAAP에서 LCS를 계산합니다. 이미 첫 번째 P를 가지고 구해놓은 값이 이전 라운드에 저장해 놓았기 때문에 그 값을 이용하면 된다는 생각이 듭니다. 1 round에서 말씀드렸듯이 똑같은 P를 만난 순간 그 자리의 값을 어떤 값으로 바꿀지가 문제인데, 이전에 계산해온 값에 +1 을 해준 값으로 바꿔 주면 된다는 생각이 듭니다. 그것을 표현 하면 다음과 같습니다.
P P A A P
0 0 0 0 0 0
P 0 1 1 1 1 1
P 0 2 2 2 2 2
P 0
A 0
하지만 , PP와 P의 LCS는 1이므로 위의 그림에서의 2는 옳지 않습니다. 그럼 어떻게 P와 PP의 LCS를 표현할 수 있을지 생각해보기 위해서 PP와 PP의 LCS를 구해보도록 합니다. 그 값은 바로 P와 P의 LCS에 1을 더한 값 입니다. 다시 말하자면 이전 라운드에서의 바로 이전 값 + 1 이 현재 구하고자 하는 두 문자열의 끝 값이 같을때의 LCS라는 것입니다. 식으로 표현하면 다음과 같습니다.
if (a[i] == b[j])
LCS[i][j] = LCS[i - 1][j - 1] + 1;
위의 식을 적용하면 ,
P P A A P
0 0 0 0 0 0
P 0 1 1 1 1 1
P 0 1 2 2 2 2
P 0
A 0
다음으로 PP와 PPA를 보겠습니다.
이전 라운드에서 계산한 값에 +1을 해주고 같은 값이 아닌 경우에는 앞에서 계산한 값이 확실하므로 그대로 넣어 줘야할 것 같습니다. (예를 들면 PPA 와 PP를 생각해보면 P와 A는 다르므로 LCS에 포함되지 않기 때문에 그 이전에 계산한 최대값인 바로 이전에 구한 값이 됩니다. 따라서 PP에 구해놓은 값이 그대로 들어갑니다.)
하지만 실제로는 그대로 넣으면 안되고, 바로 전에 구한 값과 이전 라운드에서 구한 값의 최대값을 넣어줘야 한다는 것이 느껴집니다. 실제로 예외를 생각해보면, BAKC와 BAOC를 생각해보면, 바로 전에 구한 값은 0이지만 이전 라운드에서 구한 값은 2이기 때문에 이전에 라운드에서 구한 값이 더 크기 때문에 그 값을 넣어주어야 합니다. (실제로 저 둘의 LCS는 2 입니다.)
