[파이썬] 백준 10942. 팰린드롬?

ShCho·2021년 5월 14일
4

1일 1DP

목록 보기
2/3

왜 DP?

개인적으로 왜 동적 프로그래밍 문제인지를 이해하는 것이 어려웠다. 하지만 왜 DP 문제인지만 이해하니 문제는 비교적 간단했던 것 같다.

위 그림처럼 start 부터 end까지의 문자열이 팰린드롬인지 확인하려고 할 때, 문자열 [start+1,end-1]이 팰린드롬이라는 사실을 이미 알고 있다면 문자열 전체를 검사할 필요 없이 앞 뒤 두 글자 start와 end만 비교해보면 된다.

즉, 어떤 문자열이 팰린드롬인지 확인하려면 양 끝의 문자가 같은지를 확인하고 양 끝단을 제외한 문자열이 팰린드롬인지 확인하면 된다.

따라서, 어떤 문자열이 팰린드롬인지를 판단하는 과정은 다음과 같다.

  • 양 끝의 문자가 다르면 -> 팰린드롬 아님
  • 양 끝의 문자가 같을 때, 가운데 문자열이
    - 팰린드롬이라면 -> 팰린드롬
    - 팰린드롬이 아니라면 -> 팰린드롬 아님
  • 가운데 문자열이 팰린드롬인지 아닌지 모른다면 알 때까지 문자열의 길이를 앞뒤로 하나씩 줄이면서 위의 과정을 반복한다.

가운데 문자열이 팰린드롬인지 아닌지 아는 문자열이 나올때까지 문자열의 범위를 줄여가면서 같은 과정을 계속 반복한다는 점에서 DP 문제라고 할 수 있다!

문제 접근하기

먼저 문자열에서 i 번째 글자부터 j번째 글자까지 떼어낸 부분문자열이 팰린드롬인지 아닌지를 저장하는 배열 dp[i][j] 를 만든다.

아래의 과정을 통해 dp 테이블을 채워 나간다.

  1. 문자열의 양끝을 비교한다.
    1.1 문자열의 양 끝이 같다면 가운데 문자열이 팰린드롬인지 확인한다.
    - 팰린드롬이라면 -> return True
    - 팰린드롬이 아니라면 -> return False
    1.2 문자열의 양 끝이 다르다면 --> return False

코드로 구현하기

import sys
input = sys.stdin.readline

n = int(input())
numbers = list(map(int, input().split()))
m = int(input())

#dp
dp = [[0] * n for _ in range(n)]


for num_len in range(n):
    for start in range(n - num_len):
        end = start + num_len
        
        # 시작점과 끝점이 같다면 글자수가 1개이므로 무조건 팰린드롬
        if start == end:
            dp[start][end] = 1
        # 시작점의 글자와 끝점의 글자가 같다면
        elif numbers[start] == numbers[end]:
        	# 두 글자짜리 문자열이라면 무조건 팰린드롬
            if start + 1 == end: dp[start][end] = 1
            # 가운데 문자열이 팰린드롬이라면 팰린드롬
            elif dp[start+1][end-1] == 1: dp[start][end] = 1
            

#정답출력하기
for question in range(m):
    s, e = map(int, input().split())
    print(dp[s-1][e-1])

    

for문의 범위 지정은 어떻게?

dp 테이블을 채우기 위해 2중 for 문을 그대로 돌렸더니 아래 그림 왼쪽과 같은 현상이 발생했다!

예) 문자열 [1,4]를 검사하기 위해서 문자열 [2,3]이 팰린드롬인지 확인해야 하는데, 아직 dp 테이블이 채워져 있지 않아서 제대로 된 결과를 얻을 수 없다.

따라서 dp 테이블을 채워나가는 순서를 오른쪽 그림과 같은 순서대로 채워나가야 한다. 이 같은 순서대로 테이블을 채워나가기 위한 2중 for 문은 아래와 같다.

for num_len in range(n):
    for start in range(n - num_len):
        end = start + num_len

더 나은 방법은 없을까?


참고한 블로그:
https://chocochip101.tistory.com/entry/백준-10942번-팰린드롬-파이썬


0개의 댓글