파이썬으로 푸는 단어 분할(Word Break) 문제 – 동적 계획법 완벽 정리

비어 있지 않은 문자열 s와 비어 있지 않은 단어들로 이루어진 사전 wordDict가 주어졌을 때, 문자열 s를 하나 이상의 사전 단어들을 공백으로 구분한 시퀀스로 분할할 수 있는지 판단하는 문제입니다.

문제 조건

• 분할 과정에서 사전에 있는 같은 단어를 여러 번 재사용할 수 있습니다.
• 사전에는 중복된 단어가 없다고 가정합니다.

예시

문자열 s = "applepenapple", 사전 wordDict = ["apple", "pen"]이라고 가정해 보겠습니다. 이 경우 출력은 true입니다. 문자열 s를 "apple pen apple"처럼 공백으로 구분된 형태로 분할할 수 있기 때문입니다. 여기서 "apple"이라는 단어가 두 번 사용되었는데, 문제 조건상 같은 단어의 재사용이 허용되므로 유효한 분할입니다.

풀이 접근 방식 (동적 계획법)

이 문제는 2차원 DP 테이블을 활용해 해결할 수 있습니다. 각 칸 dp[j][k]는 "부분 문자열 s[j..k]가 사전의 단어들로 분할 가능한가?"를 의미합니다.

알고리즘 단계

1. n x n 크기의 DP 행렬을 정의합니다(n은 문자열 s의 길이)하고, 모든 값을 False로 초기화합니다.
2. i를 1부터 s의 길이까지 반복합니다.
   • j를 0부터 (s의 길이 - i)까지 반복합니다.
     • 부분 문자열 s[j : j+i]가 사전에 존재하면 dp[j][j+i-1]을 True로 설정합니다.
     • 그렇지 않다면 k를 j+1부터 j+i까지 반복하면서, dp[j][k-1]과 dp[k][j+i-1]이 모두 True인 경우 dp[j][j+i-1]을 True로 설정합니다. 즉, 부분 문자열을 두 조각으로 나누었을 때 양쪽 모두 분할 가능하면 전체도 분할 가능하다는 원리를 이용합니다.
3. 최종적으로 DP[0][s의 길이 - 1] 값을 반환합니다. 이 값이 곧 전체 문자열의 분할 가능 여부입니다.

파이썬 구현 예제

class Solution(object):
    def wordBreak(self, s, wordDict):
        dp = [[False for i in range(len(s))] for x in range(len(s))]
        for i in range(1, len(s)+1):
            for j in range(len(s)-i+1):
                if s[j:j+i] in wordDict:
                    dp[j][j+i-1] = True
                else:
                    for k in range(j+1, j+i):
                        if dp[j][k-1] and dp[k][j+i-1]:
                            dp[j][j+i-1] = True
        return dp[0][len(s) - 1]

ob1 = Solution()
print(ob1.wordBreak("applepenapple", ["apple", "pen"]))

입력

"applepenapple"
["apple", "pen"]

출력

true

복잡도 분석

• 시간 복잡도: O(n³) — 세 개의 중첩 반복문(i, j, k)을 사용하기 때문입니다.
• 공간 복잡도: O(n²) — n x n 크기의 2차원 DP 테이블을 저장해야 하기 때문입니다.

참고로, 실무에서는 1차원 DP 배열(dp[i] = s[0:i]가 분할 가능한지 여부)을 사용하면 O(n²) 시간과 O(n) 공간으로 최적화할 수도 있습니다. 다만 위의 2차원 접근법은 구간별 분할 가능성을 직관적으로 파악하기 좋아 학습 목적에 적합합니다.