[백준]30805 - 사전 순 최대 공통 부분 수열 (#파이썬 #후보 범위를 넓게 하는 그리디)

부분 수열 후보군의 '범위'를 최대한 넓게 갖도록 욕심부리는 문제이다.

 

30805번: 사전 순 최대 공통 부분 수열

 

문제 요약

수열 A와 수열 B가 공통으로 갖는 부분 수열들 중 사전 순으로 가장 나중인 것을 구하여야 한다. 여기서 사전 순에 대한 정의는 문제에서 내린다. 정리하면, 여러 부분 수열들 중에서 1️⃣ 가장 index가 낮은 수가 큰 것이 사전 순으로 나중이다. 만약 이 값이 같다면 2️⃣ 그 다음 index 값을 순서대로 비교하여 큰 수가 사전 순으로 나중이다. 마지막으로 3️⃣ 부분 수열의 길이가 더 긴 것이 사전 순으로 나중이다.

요약하면 부분 수열 중에서 큰 수가 많은 것이 사전 순으로 나중이다! 문제를 풀 때도 이 관점에서 생각해보면 큰 수부터 찾아야 한다는 감이 온다.

 

시간 복잡도를 계산해본다

두 수열에서 가장 큰 수를 찾는 시간 복잡도는 O(N*M)이다. N, M <= 100 범위이므로 가장 큰 수 하나 찾는 것에는 시간 복잡도에서 문제가 없다. 위 문제 요약에 따르면 '여러 번 반복해서' 큰 수를 찾아서 부분수열을 만들어야 한다. 완전탐색으로 모든 경우를 찾는 경우 시간복잡도는 O(N*M + (N-1)*M + (N-2)*M) + ... + 1*M)이고 대략 O(N*N*M)으로 나타낼 수 있다. N, M이 100이므로 이 경우 충분히 연산 가능하다.

💡 '가장 큰 것 찾고, 두 번째로 큰 것 찾고, 세 번째로 큰 것 찾고, .... 반복'으로 부분 수열을 구하면 된다!

 

한 번 순회에 수열 각각의 '한계 index'가 결정된다

가장 큰 것을 찾고 난 후에는 한계 index가 생긴다. 이에 대해서 생각해보면 다음과 같다.

seq_a = [1, 2, 9, 4, 8, 9, 5]
seq_b = [1, 2, 9, 8, 9, 6, 5]

• 가장 큰 것은 '9'로 수열 A에서는 index 2, 5에 위치하고,
• 수열 B에서는 2, 4에 위치한다.

문제에서는 수열 A와 B의 부분수열을 구하고 있으므로 큰 수로 선택된 Index 이전의 값은 논외가 된다. 그 이전의 값이 선택되면 부분 수열이 아니게 되기 때문이다. 이로 인해 한계 index가 생긴다. 비교적 앞에 위치한 '9'를 선택하면 한계 index는 수열 A에 2, 수열 B에 2가 되고 비교적 뒤에 위치한 '9'를 선택하면 한계 index는 수열 A에 5, 수열 B에 4가 된다. 어떤 '9'를 부분 수열의 원소로 선택해야할까?

 

그리디!

사전 순으로 가장 나중임을 판단하는 데 부분 수열의 길이가 영향을 끼친다. 즉, 부분 수열을 가장 길게 만들 수 있도록 후보 군이 많도록 '9'(= 가장 큰 것)를 선택해야 하는 것이다! 이를 이해하고 나면 해당 문제는 다 푼 것이나 다름 없다 😆.

비교적 뒤에 위치한 '9'를 선택하면 부분 수열은 {9, 5}가 된다. 앞에 위치한 '9'를 선택하면 {9, 8, 9, 5}가 된다. '5'와 '8'의 비교에서 후자가 더 나중인 부분수열이다. 이처럼 가급적 앞에 위치한 '가장 큰 수'를 선택하여야 더 많은 부분 수열 경우의 수를 고려할 수 있다!

 

개인적으로 어려웠던 부분

맞.왜.틀....

그리디임을 반견하는 것이었다..! 이로 인해 한 번 순회에 한 개의 한계 index가 하나 결정된다는 사실을 뒤늦게 발견했다. 한 번 순회에 한 개의 한계 index가 결정되는 것을 확인한 후에 '후보 범위를 넓게 하는 그리디'임을 파악하고 Accepted 될 수 있었다 😅. 그리디 문제는 풀고 나면 쉬운데, 숨은 그리디 요소를 발견하는 것이 어렵다..

 

📁 코드 전문