백준 10942번 : 팰린드롬? in Python
이 문제는 하나의 수열이 주어졌을 때 그 수열 내에서 특정 인덱스 두 개가 주어지면 각 인덱스를 시작과 끝으로 하는 부분수열이 팰린드롬, 즉 거꾸로 해도 같은 수열이 되는지를 알려주는 문제다.
만약 특정 인덱스 두 개를 한 번만 준다면 단순히 brute force 알고리즘으로 처음 인덱스를 증가시키고 끝 인덱스를 감소시키면서 인덱스에 해당하는 숫자가 같은지만 확인하면 쉽게 해결할 수 있다. 그러나 이 문제는 주어지는 인덱스 쌍이 최대 10^6개까지 주어져 이를 전부 brute force 알고리즘으로 구한다면 꽤나 오랜 시간이 걸릴 것이다.
그렇다면 인덱스 쌍이 주어졌을 때의 결과 반환 시간을 줄이는 게 이 문제의 핵심일 것일텐데, 어떻게 하면 이 시간을 줄일 수 있을까? 바로 답을 미리 구하는 것이다. 각 인덱스 쌍에 대해 팰린드롬인지 미리 판별해 둔다면 나중에 인덱스 쌍이 주어졌을 때 상수 시간 안에 바로 구할 수 있을 것이다. 이제 문제는 답을 어떻게 미리 구하냐는 것이다.
여기서 dynamic programming을 사용한다. 이는 주어진 부분수열이 팰린드롬인지 따지는데 그 수열의 부분수열이 팰린드롬인지를 미리 구해놓고 이를 따져서 O(1) 시간 안에 구할 수 있다는 점에 기인한다. 예를 하나 들자면 만약 '1 2 3 4 3 2 1'이 팰린드롬인지 판별할 때 처음과 끝이 같은지 보고, 그리고 처음과 끝을 제외한 부분수열인 '2 3 4 3 2'가 팰린드롬인지 판별한다. 이때 만약 부분수열의 길이가 작은 경우부터 큰 경우까지 올라오면서 차례대로 팰린드롬인지 판별한다면 '2 3 4 3 2'라는 부분수열이 팰린드롬인지를 미리 판별했을 것이고, 이 결과를 가지고 상수 시간 안에 전체 수열 '1 2 3 4 3 2 1'이 팰린드롬인지 판별할 수 있다.
이러한 방법으로 모든 인덱스 쌍에 대해 부분수열이 팰린드롬인지 따진다면 M개의 질문에 답하는데 걸리는 시간은 O(N^2 + M)일 것이다. 이전에 brute force로 문제를 풀 경우에는 O(MN)의 시간이 소요되는데, 특히 이 문제의 경우 N이 M보다 훨씬 작기 때문에 dynamic programming으로 문제를 풀 경우 시간을 훨씬 단축시킬 수 있다.
코드를 작성할 때에는 우선 dynamic programming을 적용할 행렬 dp를 만들고, (i, i) entry (0 <= i < N)의 값은 1로 설정한다. 왜냐하면 이 entry는 길이가 1인 부분수열이 팰린드롬인지를 나타내는데, 길이가 1인 경우는 항상 팰린드롬이 되기 때문이다. 길이가 짧은 경우부터 entry를 채워야 하므로 길이에 대한 for loop를 만들고 길이가 가질 수 있는 값은 2부터 N까지로 한다. 그리고 시작 index에 대해 for loop을 만들면 끝 index는 시작 index와 길이를 통해 유추할 수 있다.
이제 시작 index와 끝 index에 대해 부분수열이 팰린드롬인지를 판별하는데, 길이가 2인 경우는 시작 index에 해당하는 수와 끝 index에 해당하는 수가 같은지만 판별하면 되기 때문에 따로 판별하고, 나머지 경우에 대해서는 이전에 구했던 부분수열의 팰린드롬 여부와 시작 index와 끝 index에 해당하는 수의 일치 여부를 따져 현재 부분수열이 팰린드롬인지 판별한다.
이를 코드로 구현하면 다음과 같다.
import sys
input = sys.stdin.readline
N = int(input())
numbers = list(map(int, input().split()))
# dynamic programming을 구현하기 위한 행렬
dp = [[0]*N for _ in range(N)]
# 길이가 1인 부분수열은 항상 팰린드롬
for i in range(N):
dp[i][i] = 1
# 길이에 대한 for loop
for l in range(2, N+1):
# 시작 index에 대한 for loop
for i in range(N-l+1):
# 끝 index는 시작 index와 길이로 유추할 수 있다.
j = i+l-1
# 길이가 2인 경우 시작 index의 수와 끝 index의 수가 일치하는지만 판별하면 된다.
if l == 2 and numbers[i] == numbers[j]:
dp[i][j] = 1
# 시작 index의 수와 끝 index의 수가 일치하는지, 그리고 시작 index의 수와 끝 index의 수를 제외한
# 부분수열이 팰린드롬인지 판별한다.
elif dp[i+1][j-1] == 1 and numbers[i] == numbers[j]:
dp[i][j] = 1
M = int(input())
for _ in range(M):
start, end = map(int, input().split())
print(dp[start-1][end-1])