Coding Interview Prep · 강의

단어 분할과 문자열 분할

Q: “단어 분할과 문자열 분할” 강의는 무료인가요?

네 — “단어 분할과 문자열 분할” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

Q: Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.

Q: “단어 분할과 문자열 분할” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

Q: 이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

1차원 DP 표로 문자열을 사전 단어로 분할할 수 있는지 판단하고, O(n²) 시간 복잡도와 트라이가 이를 빠르게 만드는 이유를 분석합니다.

단어 분할과 문자열 분할은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

단어 분할 문제

단어 분할(LeetCode 139)은 문자열 s와 단어 사전이 주어졌을 때, s를 하나 이상의 사전 단어로 이루어진 공백 구분 시퀀스로 분할할 수 있는지 묻습니다. 예를 들어 s = 'leetcode'이고 wordDict = ['leet', 'code']라면 'leet' + 'code' = 'leetcode'이므로 답은 True입니다. 이는 전형적인 1차원 DP 문제입니다.

s = 'leetcode'
word_set = {'leet', 'code'}
# Can we split 'leetcode' into words from word_set?
# 'leet' in set → yes, 'code' in set → yes
# So: 'leetcode' = 'leet' + 'code' → True

s2 = 'catsandog'
word_set2 = {'cats', 'dog', 'sand', 'and', 'cat'}
# No matter how we split, last part 'og' not in dict
print('Expected: True, False')

DP 정식화 및 상태

dp[i]를 부분 문자열 s[:i]를 사전을 사용해 분할할 수 있을 때 True가 되는 값으로 정의합니다. 기저 조건은 dp[0] = True입니다. 빈 문자열은 항상 분할할 수 있기 때문입니다. 각 위치 i에서 j < i인 모든 위치를 확인합니다. dp[j]가 True이고 s[j:i]가 사전에 있다면 dp[i] = True로 설정합니다. 최종 답은 dp[len(s)]입니다.

def word_break(s, word_dict):
    word_set = set(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True  # empty string
    
    for i in range(1, n + 1):
        for j in range(i):
            # If s[:j] is segmentable AND s[j:i] is a word
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break  # no need to check other j values
    return dp[n]

print(word_break('leetcode', ['leet', 'code']))        # True
print(word_break('catsandog', ['cats','dog','sand','and','cat']))  # False

DP 표 추적

s = 'leetcode'이고 사전이 {'leet', 'code'}인 경우를 보겠습니다. dp[0]=T입니다. i=4일 때 j=0이고, dp[0]=T이며 s[0:4]='leet'이 사전에 있으므로 dp[4]=T입니다. i=8일 때 j=4이고, dp[4]=T이며 s[4:8]='code'가 사전에 있으므로 dp[8]=T입니다. 단어가 끝나지 않는 다른 모든 위치는 거짓으로 남습니다. 답 dp[8]=True는 문자열을 분할할 수 있음을 확인해 줍니다.

def word_break_trace(s, word_dict):
    word_set = set(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                print(f'dp[{i}]=True via s[{j}:{i}]={repr(s[j:i])}')
                break
    print('dp table:', dp)
    return dp[n]

word_break_trace('leetcode', ['leet', 'code'])

시간 복잡도 분석

단순한 DP는 O(n²) 시간에 실행됩니다. 바깥 반복이 n번이고 안쪽 반복이 최대 n번이기 때문입니다. 하지만 s[j:i]를 자르는 작업에도 O(n)이 걸리므로 파이썬에서 실제 복잡도는 O(n³)입니다. 한 가지 최적화 방법은 사전의 단어를 순회하며 각 단어가 위치 i에서 끝나는지 확인하는 것입니다. 그러면 W가 사전 크기이고 L이 평균 단어 길이일 때 O(n × W × L)이 됩니다. 대부분의 면접 입력에서는 O(n²) 또는 O(n³)도 허용할 수 있습니다.

# Slightly faster: iterate over words rather than all j positions
def word_break_v2(s, word_dict):
    word_set = set(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for word in word_set:
            wl = len(word)
            # Does 'word' end exactly at position i?
            if i >= wl and dp[i - wl] and s[i - wl:i] == word:
                dp[i] = True
                break
    return dp[n]

print(word_break_v2('applepenapple', ['apple', 'pen']))  # True

메모이제이션을 사용한 재귀 대안

같은 문제를 메모이제이션을 사용하는 하향식 방식으로 해결할 수도 있습니다. 재귀 함수 can_break(start)를 정의하여 s[start:]를 분할할 수 있으면 True를 반환하도록 합니다. s[start:]의 접두사로 각 단어를 시도하고 나머지 부분에 대해 재귀 호출을 수행합니다. 같은 시작 위치를 여러 번 다시 탐색하지 않도록 결과를 저장합니다. 이는 상향식 DP와 동등하지만, 많은 위치를 일찍 가지치기할 수 있다면 실제로 더 빠를 수 있습니다.

from functools import lru_cache

def word_break_memo(s, word_dict):
    word_set = set(word_dict)
    
    @lru_cache(maxsize=None)
    def can_break(start):
        if start == len(s): return True
        for end in range(start + 1, len(s) + 1):
            if s[start:end] in word_set and can_break(end):
                return True
        return False
    
    return can_break(0)

print(word_break_memo('leetcode', ['leet', 'code']))  # True
print(word_break_memo('catsandog', ['cats','dog','sand','and','cat']))  # False

모든 유효한 분할 반환하기

단어 분할 II(LeetCode 140)는 가능한 모든 분할을 요구합니다. 방법은 메모이제이션을 사용하는 백트래킹입니다. 각 위치에서 재귀적으로 탐색하고, 단어가 일치하면 나머지 부분을 다시 탐색합니다. 모든 부분 결과를 문자열 목록으로 저장합니다. TLE를 방지하려면 각 시작 위치에서 만들 수 있는 문장 목록을 메모이제이션해야 합니다. 최악의 경우 문장 수는 지수적으로 늘어날 수 있지만, 메모이제이션이 중복 계산을 제거합니다.

from functools import lru_cache

def word_break_ii(s, word_dict):
    word_set = set(word_dict)
    
    @lru_cache(maxsize=None)
    def break_from(start):
        if start == len(s): return ['']
        results = []
        for end in range(start + 1, len(s) + 1):
            word = s[start:end]
            if word in word_set:
                for rest in break_from(end):
                    results.append(word if not rest else word + ' ' + rest)
        return results
    
    return break_from(0)

print(word_break_ii('catsanddog', ['cat','cats','and','sand','dog']))
# ['cat sand dog', 'cats and dog']

트라이 최적화

사전이 크거나 단어가 길면 파이썬 문자열 해싱 때문에 모든 j에 대해 s[j:i] in word_set를 확인하는 작업이 느립니다. 트라이를 사용하면 문자를 하나씩 따라가며 불가능한 경로를 일찍 가지칠 수 있습니다. O(n)의 모든 시작 위치를 확인하는 대신 트라이에 실제로 존재하는 경로만 따라갑니다. 유효한 단어로 이어지는 접두사가 적을 때 실제 실행 시간이 크게 줄어듭니다.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

def build_trie(words):
    root = TrieNode()
    for word in words:
        node = root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True
    return root

def word_break_trie(s, word_dict):
    root = build_trie(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(n):
        if not dp[i]: continue
        node = root
        for j in range(i, n):
            ch = s[j]
            if ch not in node.children: break
            node = node.children[ch]
            if node.is_end:
                dp[j + 1] = True
    return dp[n]

print(word_break_trie('leetcode', ['leet', 'code']))  # True

경계 사례 및 제약 조건

중요한 경계 사례는 다음과 같습니다. (1) 빈 문자열: 참을 반환합니다. 빈 문자열은 자명하게 분할할 수 있기 때문입니다. (2) 사전에 없는 단어: DP가 해당 위치를 참으로 설정하지 않으므로 거짓을 올바르게 반환합니다. (3) 겹치는 단어: 사전에 'a'와 'aa'가 있고 s='aaa'인 경우처럼, DP는 모든 j 값을 확인하여 이를 자연스럽게 처리합니다. (4) 반복되는 문자: s='aaaaab'이고 dict=['a','aa','aaa']인 경우 경로는 지수적으로 늘어나지만, 메모이제이션으로 O(n²)까지 제한됩니다.

def word_break(s, word_dict):
    word_set = set(word_dict)
    dp = [False] * (len(s) + 1)
    dp[0] = True
    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    return dp[len(s)]

# Edge cases
print(word_break('', ['hello']))          # True (empty string)
print(word_break('a', ['b']))             # False
print(word_break('aaa', ['a', 'aa']))     # True (many ways)

문자열 분할 일반화

단어 분할은 모든 문자열 분할 문제로 일반화할 수 있습니다. 문자열 s를 어떤 규칙에 따라 분할할 수 있는지 묻는 문제입니다. 사전 조회를 O(1) 또는 O(L) 검사로 대체하면 됩니다. 예를 들어 s를 회문으로 분할할 수 있는지 확인하려면 단어 집합 대신 미리 계산한 회문 표를 사용합니다. DP 구조는 동일하고 유효성 검사만 달라집니다.

def palindrome_partition_possible(s):
    '''Can s be partitioned into palindromes? (Always yes — single chars are palindromes)'''
    n = len(s)
    # Precompute palindrome table
    is_pal = [[False]*n for _ in range(n)]
    for i in range(n): is_pal[i][i] = True
    for i in range(n-1): is_pal[i][i+1] = (s[i]==s[i+1])
    for length in range(3, n+1):
        for i in range(n-length+1):
            j = i + length - 1
            is_pal[i][j] = s[i]==s[j] and is_pal[i+1][j-1]
    # DP similar to word break
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and is_pal[j][i-1]:
                dp[i] = True
                break
    return dp[n]

print(palindrome_partition_possible('aab'))  # True (a,a,b or aa,b)

DP와 BFS 방식

단어 분할은 BFS 최단 경로 문제로도 볼 수 있습니다. 문자열의 각 위치가 하나의 노드이고, s[j:i]가 사전에 있으면 j에서 i로 가는 간선이 존재합니다. 노드 0에서 BFS를 수행하면 노드 n에 도달할 수 있는지 확인하게 됩니다. BFS의 복잡도는 동일하게 O(n² × L)이지만, 면접에서 그래프 문제로 모델링하면 더 직관적으로 설명할 수 있습니다.

from collections import deque

def word_break_bfs(s, word_dict):
    word_set = set(word_dict)
    n = len(s)
    visited = set()
    queue = deque([0])
    while queue:
        start = queue.popleft()
        if start == n: return True
        for end in range(start + 1, n + 1):
            if end not in visited and s[start:end] in word_set:
                visited.add(end)
                queue.append(end)
    return False

print(word_break_bfs('leetcode', ['leet', 'code']))    # True
print(word_break_bfs('catsandog', ['cats','dog','and','sand','cat']))  # False

면접 설명 전략

면접에서는 다음과 같은 사고 과정을 설명해 보세요. (1) 각 위치의 선택이 이전에 도달할 수 있었던 위치에 의존한다는 점을 관찰합니다. 이는 DP를 사용해야 한다는 신호입니다. (2) 상태를 정의합니다. dp[i] = s[:i]를 분할할 수 있는가? (3) 코딩하기 전에 점화식과 기저 조건을 말합니다. (4) 먼저 O(n²) 해법을 구현한 다음, 후속 설명으로 트라이 최적화를 언급합니다. (5) 빈 문자열, 한 글자 문자열, 사전에 없는 단어 같은 경계 사례를 논의합니다.

# Clean final solution to present in interview
def word_break(s, word_dict):
    '''O(n^2 * L) time, O(n + W) space where W = total word length in dict'''
    word_set = set(word_dict)   # O(W) space
    n = len(s)
    dp = [False] * (n + 1)     # O(n) space
    dp[0] = True
    for i in range(1, n + 1):
        for j in range(i):     # try all split points
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    return dp[n]

# Time: O(n^2 * L) - n^2 pairs, each dict lookup is O(L)
# Space: O(n) for dp array, O(W) for word_set
print(word_break('applepenapple', ['apple', 'pen']))  # True

빠른 확인

이 단원에서 다룬 자료 구조 및 알고리즘 — 코딩 면접 준비 개념에 대한 이해도를 확인해 보세요.

단원 요약

이 단원에서는 dp[i]가 s[:i]를 사전 단어로 분할할 수 있는지를 나타낸다는 것, O(n²) 점화식이 dp[j]=True이고 s[j:i]가 단어 집합에 속하는 모든 분할 지점 j를 확인한다는 것, 트라이가 존재하지 않는 접두사를 일찍 가지쳐 내부 반복을 빠르게 할 수 있다는 것을 배웠습니다. 다음으로 또 하나의 피보나치와 유사한 1차원 DP 패턴인 디코딩 방법과 경로 수 세기를 살펴봅니다.

자주 묻는 질문