[PS] 1509) 펠린드롬분할

https://www.acmicpc.net/problem/1509

1509번: 팰린드롬 분할

Gold1) 1509.펠린드롬분할

 

• 다이나믹 프로그래밍

다이나믹 프로그래밍으로 작성해서 AC를 받았다.

시간복잡도를 대충 계산해봤는데 펠린드롬 분할 확인에서 O(N^2), 문자열의 분할 수 최소값을 구할 때도 O(N^2)의 시간이 소요된다.

문제에서 주어진 요구사항은 문자열의 길이가 최대 2500으로 약 6만번의 루프가 수행된다.

 

검색해보니 펠린드롬 판별 알고리즘인 Manacher's Algorithm이 있다는데, 다음에 비슷한 문제를 만나면 저 알고리즘을 사용해보려고 한다. 해당 알고리즘은 O(N)의 시간복잡도로 펠린드롬을 판별할 수 있다고 한다.

 

다이나믹 프로그램으로 해결한 방법은 다음과 같다.

펠린드롬 판별 알고리즘에서는 이중배열을 선언한다. dp[i][j], 해당 dp배열은 i부터 j까지의 문자열이 펠린드롬이면 1을 아니면 0을 저장한다.

핵심 점화식은 i+1부터 j-1까지 문자열과 i부터 j까지 문자열의 관계이다.

만약 dp[i+1][j-1] 이 펠린드롬이고 i와 j의 문자가 같다면 dp[i][j]도 펠린드롬이 된다.

이를 사용하여 짠 코드는 다음과 같다.

# dp 배열 생성
    dp = list(list(0 for _ in range(n)) for _ in range(n))
    # dp 배열 초기화 -> 이중배열 dp[i][j]는 i번째 문자부터 j번째 문자까지 펠린드롬인지
    # i부터 i까지, 즉 자기 자신은 스스로 펠린드롬 만족
    # if문은 본인과 바로 다음 문자 비교해서 같은 문자면 펠린드롬
    for i in range(n) :
        dp[i][i] = 1
        if i!=n-1 and board[i] == board[i+1] :
            dp[i][i+1] = 1
    # 이후 나머지 배열을 채우기 위한 과정
    # 다이나믹 프로그래밍 -> 점화식
    # i+1부터 j-1이 펠린드롬 & i와 j의 문자가 같으면 i부터 j도 펠린드롬임
    # 각 문자 자리에서 바로 다음 문자(2의 크기를 갖는)까지는 체크된 상태
    # 3의 크기를 갖는 부분 문자열 계산
    # jump를 2부터 n-1까지 -> left는 0부터 n-jump까지
    for jump in range(2,n) :
        for left in range(n-jump) :
            right = left + jump
            if board[left] == board[right] and dp[left+1][right-1] == 1:
                dp[left][right] = 1

코드에서 이해를 돕기 위해 left와 right로 변수를 선언하고 jump는 모든 간격의 dp를 계산하기 위한 for문의 변수이다.

이후 생성한 dp를 확인하면 펠린드롬 문자열이 판별되는 i와  j 위치에 1이 찍혀있는 것을 확인할 수 있다.

 

문제에서 구하는 것은 문자열에서 펠린드롬 문자열로 분할할 때, 나눌 수 있는 분할의 최소를 출력하는 것이다.

이때에도 다이나믹 프로그래밍을 사용하여 해결할 수 있다.

이번에는 각 자리에서 최소 분할수를 저장하기 때문에 일차원 배열 dp2[n]로 선언하고 각 자리는 스스스 펠린드롬이기 때문에 문자열의 크기와 같은 값을 갖도록 배열을 초기화했다.

여기서 핵심 점화식은 dp2[i]를 구할때, i부터 작은 인덱스로 진행하면서 펠린드롬 분할이 판별되는 곳에 주목하는 것이다.

만약 i-jump부터 i까지 펠린드롬을 만족한다면 dp[i-jump] ( i-jump크기의 문자열까지 분할수 최소 ) + 1 (i-jump부터 i까지 펠린드롬 이기 때문에) 로 최소 분할 수를 정할 있을 것이다.

해당 코드는 다음과 같다.

# 펠린드롬 분할의 최소값을 구하는 과정
    # 다이나믹 프로그래밍 -> 점화식
    # dp2[i] -> i번째까지의 펠린드롬 분할 최소값
    # dp2[0] -> 1 이것의 의미는 0번부터 0번까지 펠린드롬 분할은 1개라는 뜻
    # dp2[1] -> min(dp2[0]+1, dp[2]) 이것은 1번 문자 하나 자체로 펠린드롬이기 때문에 1번 문자 제외
    # 이전문자들에서 펠린드롬 분할 최소 + 1 이 최소가 될 수 있고, 또는 1번문자를 포함한 문자열에서 펠린드롬 분할 수가 최소가 될 수
    # 있다는 뜻
    # 결과적으로 dp2[n] = min(dp2[n-tmp]+1,dp2[n]) 여기서 n-tmp 다음부터 n까지 펠린드롬 분할일 경우이고
    # 이 경우 n-tmp까지 최소 분할수 + 1 이나 전체의 최소 분할 수 중 작은 값을 선택
    dp2 = list(i+1 for i in range(n))
    for right in range(n) :
        for left in range(right,-1,-1) :
            if dp[left][right] == 1:
                if left == 0 :
                    dp2[right] = 1
                    continue
                dp2[right] = min(dp2[left-1]+1,dp2[right])

코드는 길지 않지만 다이나믹 프로그래밍 자체가 점화식을 끌어내야 풀이를 시작할 수 있기 때문에 비슷한 유형의 문제를 많이 풀어보면 좋을 것 같다.

다이나믹 프로그래밍을 사용할 수 있다는 확신이 든다면 주저하지 않고 배열을 어떻게 선언하고, 점화식을 어떻게 이끌어낼 것인지부터 고민한 다음 풀이에 들어간다면 조금 더 쉽게 정답에 도달할 수 있을 것이다.