Jin의 일상

이번 글은 여기를 참고하여 작성하였습니다.

따라서 해당 블로그에서의 설명을 바탕으로 알고리즘 원리만 적도록 하겠습니다.

(코드는 해당 블로그를 참고 바랍니다.)

www.acmicpc.net/problem/9251

문제 내용

두 문자열이 주어졌을 때, 공통된 수열의 최장 길이를 구하는 문제다.

즉, DBBE, BDBE 가 주어졌을 때 공통 수열이 될 수 있는 것은 "D, DB, DBE"와 "B, BB, BBE"등이 있다.

그 중 가장 긴 수열은 DBE와 BBE이므로, 답으로 3을 리턴하면 된다.

알고리즘 구상

DBBE와 BDBE를 하나씩 비교하며 공통되는 부분 수열을 구해보자.

1. D와 B      : { }

2. D와 BD    : {D}

3. D와 BDB  : {D}

4. D와 BDBE : {D}

5. DB와 B    : {B}

6. DB와 BD  : {B}, {D}

7. DB와 BDB : {D}, {B}, {D, B}

8. DB와 BDBE : {D}, {B}, {D, B}

9. DBB와 B    : {B}

10. DBB와 BD : {D}, {B}

11. DBB와 BDB : {D}, {B}, {B}, {D, B}, {B, B}

12. DBB와 BDBE : {D}, {B}, {B}, {D, B}, {B, B}

13. DBBE와 B    : {B}

14. DBBE와 BD : {D}, {B}

15. DBBE와 BDB : {B}, {D}, {B}, {D, B}

16. DBBE와 BDBE : {D}, {B}, {B}, {E}, {D, B}, {D, B, E}, {B, B, E}

이러한 과정은 Matrix를 통해 표현될 수 있다.

매트릭스 설명

1. 매트릭의 가장자리는 0으로 덮여있습니다.

2. 세로 축의 DBBE는 첫 번째로 인풋된 데이터를 의미합니다.

3. 가로 축의 BDBE는 두 번째로 인풋된 데이터를 의미합니다.

4. 알고리즘 코드는 맨 위에서부터 가로로 한 줄씩 진행됩니다.

 - 가로 축과 세로 축의 값이 같으면, 왼쪽 대각선 위의 값에서 1을 더해줍니다.

 - 가로 축과 세로 축의 값이 다르면, 왼쪽 또는 위의 값 중 큰 것을 받아옵니다.

위의 매트릭스를 분석해보자

각 칸은 왼쪽과 위측, 왼쪽 대각선 위로부터의 진행 방향을 갖는다.

가로 축과 세로 축의 값이 다르면, 왼쪽 또는 위측이 가진 최장 길이를 그대로 받아오면 된다.

왼쪽 대각선 위의 값을 받아오지 않는 이유는, 알고리즘이 맨 위부터 가로로 한 줄씩 진행됐기 때문이다.

만약 가로 축과 세로 축의 값이 같다면, 왼쪽 대각선 위의 값에서 1을 더해서 가져와야 한다.

왼쪽이나 위쪽에서 값을 가져와서 1을 더한다면, 세로 축(DB)와 가로 축(BDB)의 경우 2가 된다.

(이 경우에는 2가 맞긴 하다. 어쨌든 설명을 더 들어보자)

여기서 나타낸 DB와 BDB의 최장 길이의 공통 수열로 {D, B}를 나타낸 것이지만, 동시에 {B, B}를 의미하게 되고 반례에 해당한다.

코드

밑의 블로그를 참고하길 바랍니다.

suri78.tistory.com/11