커리큘럼/페이즈 4 · 심화 알고리즘
23주차

트리 DP와 문자열 매칭

마지막 개념 주차예요. 모르면 아예 못 푸는 도구 두 가지.

개념

마지막 개념 주차예요. 여기 나오는 것들은 매번 쓰이지는 않지만, 필요한 순간에 모르면 아예 못 푸는 도구들이에요. 앞의 22주를 다 거쳤다면 둘 다 '이미 아는 것의 조합'으로 읽힐 거예요.

트리 DP

트리 DP는 이름 그대로 트리 위에서 하는 DP예요. 19~20주차 DP는 dp[i], dp[i][j] 처럼 배열 위에서 왼쪽에서 오른쪽으로 채웠어요. 트리에서는 자식의 답을 모아 부모의 답을 만들어요. 후위 순회(자식 먼저, 자기 나중) 순서로 채우는 거예요.왜 이게 성립하냐면, 트리에는 사이클이 없기 때문이에요. 어떤 정점의 답이 자기 서브트리에만 의존하므로 서로를 순환 참조하지 않아요. 14주차에서 트리 재귀를 쓸 때 이미 이 구조를 썼어요 — 최대 깊이는 1 + max(왼쪽 깊이, 오른쪽 깊이) 였고, 그게 가장 단순한 트리 DP예요.
구하려는 것상태전이
서브트리 크기size[v]1 + Σ size[child]
서브트리 최대 깊이depth[v]1 + max(depth[child])
트리의 지름각 정점에서 가장 깊은 자식 둘max(d1 + d2)
최대 독립 집합dp[v][0], dp[v][1]고르면 자식은 못 고름
최대 독립 집합이 트리 DP의 전형이에요. 서로 인접하지 않게 정점을 골라 가중치 합을 최대로 만드는 문제인데, 상태를 '이 정점을 골랐는가'로 하나 더 두면 풀려요. dp[v][1] 은 v를 골랐을 때이므로 자식은 반드시 안 고른 값 dp[child][0] 을 더하고, dp[v][0] 은 자식이 자유로우니 둘 중 큰 값을 더해요. 16주차 '도둑질'을 트리로 옮긴 것과 같아요.트리의 지름은 가장 먼 두 정점 사이의 거리예요. 각 정점을 최고점으로 삼는 경로만 생각하면, 그 정점에서 내려가는 가장 깊은 두 갈래를 더한 값이 후보예요. 모든 정점에서 이 후보를 구해 최댓값을 취하면 답이에요 — 후위 순회 한 번, O(n)이에요.

직접 채워 보기: 서브트리 크기

머릿속 그림은 이래요. 잎에서 시작해 뿌리 쪽으로 정보를 모아 올려요. 회사 조직도에서 '내 밑에 몇 명이 있나'를 세는 것과 똑같아요. 말단 직원은 자기 혼자니까 1명, 팀장은 '내 팀원들 각자의 인원 수를 다 더하고, 나 자신을 1 더한' 값이에요. 자식이 먼저 답을 알아야 부모가 더할 수 있으니, 순서는 늘 자식 먼저·부모 나중, 곧 후위 순회예요.작은 트리 하나로 손으로 채워 볼게요. 루트 0 아래에 자식 1과 2가 있고, 1 아래에 다시 자식 3과 4가 있어요. size[v] 는 'v를 포함한 서브트리의 정점 수'예요. 잎(자식이 없는 정점)은 자기 혼자니까 무조건 1로 시작하고, 부모는 1 + 자식들의 size 합 으로 올려요.
루트 0에서 후위 순회 — 잎에서 뿌리로 size를 모아 올리는 과정
트리 모양                 자식 목록
        0                 0 : 1, 2
       / \                1 : 3, 4
      1   2               2 : (없음, 잎)
     / \                  3 : (없음, 잎)
    3   4                 4 : (없음, 잎)
​
후위 순회 방문 순서 → 3  4  1  2  0
​
size[3] = 1                      잎이라 자기 혼자
size[4] = 1                      잎이라 자기 혼자
size[1] = 1 + size[3] + size[4]  = 1 + 1 + 1 = 3
size[2] = 1                      잎이라 자기 혼자
size[0] = 1 + size[1] + size[2]  = 1 + 3 + 1 = 5
​
v       0   1   2   3   4
size    5   3   1   1   1     → 답 size[0] = 5 (전체 정점 수)
핵심은 size[0] 을 구하려면 size[1], size[2] 가 먼저 채워져 있어야 하고, size[1] 을 구하려면 size[3], size[4] 가 먼저여야 한다는 점이에요. 그래서 방문 순서가 잎부터 시작해 뿌리에서 끝나요. 재귀로 짜면 이 순서가 저절로 지켜져요 — 자식 dfs 를 다 부른 다음에 내 값을 계산하니까요.

문자열 매칭 — KMP

긴 문자열에서 패턴을 찾을 때, 어긋날 때마다 처음부터 다시 비교하면 O(nm)이에요. KMP는 패턴 자신의 접두사-접미사 정보를 미리 계산해두어 어긋나도 본문 포인터를 되돌리지 않게 만들어 O(n+m)으로 줄여요.핵심은 실패 함수(부분 일치 테이블)예요. fail[i] 는 '패턴의 앞 i+1 글자 중, 접두사이면서 동시에 접미사인 가장 긴 것의 길이'예요. 어긋났을 때 이 길이만큼은 이미 맞춰져 있다는 뜻이므로, 패턴 포인터를 0이 아니라 fail[j-1] 로 되돌리면 돼요.직관을 먼저 잡아 볼게요. 본문에서 패턴을 맞춰 나가다 중간에 어긋났다고 해봐요. 순진하게 하면 본문을 한 칸 옆으로 밀고 처음부터 다시 비교하는데, 그건 이미 확인한 글자를 또 보는 낭비예요. KMP는 처음부터 다시 안 봐요. 대신 '지금까지 맞춘 부분 중에서, 앞부분(접두사)과 뒷부분(접미사)이 겹치는 만큼은 이미 맞춰진 셈'이라 그 길이만큼만 건너뛰고 이어서 비교해요. 그 '건너뛸 길이'를 미리 계산한 표가 실패 함수예요.

직접 채워 보기: 실패 함수

패턴 ababc 의 실패 함수를 한 칸씩 채워 볼게요. fail[i] 는 '앞 i+1 글자에서 접두사이면서 동시에 접미사인 가장 긴 조각의 길이'예요. j 는 '지금까지 이어 맞춘 접두사의 길이'를 들고 다니는 포인터예요. pattern[i] 와 pattern[j] 가 같으면 j 를 하나 늘려 fail[i] 에 적고, 다르면 j 를 fail[j-1] 로 되돌려 더 짧은 겹침을 시도해요.
패턴 ababc — fail 배열을 왼쪽부터 채우는 과정 (i는 1부터)
index   0   1   2   3   4
char    a   b   a   b   c
fail    0   .   .   .   .     ← fail[0]은 언제나 0
​
i=1  char b  vs pattern[j=0] a   다름 → fail[1] = 0,  j 그대로 0
i=2  char a  vs pattern[j=0] a   같음 → j=1, fail[2] = 1
i=3  char b  vs pattern[j=1] b   같음 → j=2, fail[3] = 2
i=4  char c  vs pattern[j=2] a   다름 → j = fail[1] = 0
     char c  vs pattern[j=0] a   또 다름 → fail[4] = 0
​
index   0   1   2   3   4
char    a   b   a   b   c
fail    0   0   1   2   0     → 완성
fail[3] = 2 의 뜻을 읽어 볼게요. 앞 4글자 abab 에서 접두사이자 접미사인 가장 긴 조각은 ab (길이 2)예요. 그래서 본문에서 abab 까지 맞추다 다음 글자가 어긋나면, 앞의 ab 는 그대로 맞춰져 있는 셈이라 j 를 0이 아니라 2에서 다시 이어 가요. 이게 '처음부터 다시 안 본다'의 정체예요.

팰린드롬 — 매내처

가장 긴 팰린드롬 부분 문자열은 각 위치를 중심으로 양옆으로 넓혀 보면 O(n²)에 풀려요. 대부분의 문제는 이걸로 통과해요. 매내처(Manacher)는 같은 답을 O(n)에 구해요. 이미 구한 팰린드롬 안쪽은 대칭이므로, 그 대칭성으로 반대편의 결과를 재사용해 중복 확장을 건너뛰어요.구현의 첫 관문은 홀짝이에요. aba 는 중심이 글자이고 abba 는 중심이 글자 사이라 처리가 갈려요. 문자 사이사이에 # 을 끼워 #a#b#b#a# 로 만들면 길이가 항상 홀수가 되어 경우가 하나로 합쳐져요. 이 변환 뒤 반지름 배열 p[i] 의 최댓값이 곧 원래 문자열에서의 팰린드롬 길이예요.매내처는 코딩 테스트에서 자주 나오지는 않아요. 다만 '이미 계산한 대칭 구조를 재사용한다'는 발상은 값어치가 있고, 중심 확장 O(n²) 이 시간 초과가 나는 제한(n ≥ 10만)에서는 이것 말고 선택지가 없어요.

패턴 코드

트리 DP — 최대 독립 집합dp[v][1]은 v를 고른 경우. 자식은 반드시 고르지 않은 값을 더해요.
javascript
// adj: 양방향 인접 리스트, weight: 정점 가중치
const dp = Array.from({ length: n }, () => [0, 0]);
​
function dfs(v, parent) {
  dp[v][0] = 0;
  dp[v][1] = weight[v];
  for (const next of adj[v]) {
    if (next === parent) continue;
    dfs(next, v);
    dp[v][0] += Math.max(dp[next][0], dp[next][1]);
    dp[v][1] += dp[next][0];
  }
}
​
dfs(0, -1);
const answer = Math.max(dp[0][0], dp[0][1]);
트리의 지름각 정점에서 내려가는 가장 깊은 두 갈래를 더한 값이 그 정점을 지나는 최장 경로예요.
javascript
let best = 0;
​
function depth(v, parent) {
  let first = 0;
  let second = 0;          // 가장 깊은 둘
  for (const next of adj[v]) {
    if (next === parent) continue;
    const d = depth(next, v) + 1;
    if (d > first) [first, second] = [d, first];
    else if (d > second) second = d;
  }
  best = Math.max(best, first + second);
  return first;
}
​
depth(0, -1);
KMP — 실패 함수와 검색본문 포인터 i는 절대 되돌아가지 않아요. 그래서 O(n+m)이에요.
javascript
function buildFail(pattern) {
  const fail = new Array(pattern.length).fill(0);
  let j = 0;
  for (let i = 1; i < pattern.length; i++) {
    while (j > 0 && pattern[i] !== pattern[j]) j = fail[j - 1];
    if (pattern[i] === pattern[j]) fail[i] = ++j;
  }
  return fail;
}
​
function search(text, pattern) {
  const fail = buildFail(pattern);
  const found = [];
  let j = 0;
  for (let i = 0; i < text.length; i++) {
    while (j > 0 && text[i] !== pattern[j]) j = fail[j - 1];
    if (text[i] === pattern[j]) {
      if (++j === pattern.length) {
        found.push(i - j + 1);
        j = fail[j - 1];
      }
    }
  }
  return found;
}
매내처 — 가장 긴 팰린드롬#을 끼워 길이를 홀수로 통일해요. p[i]가 곧 원래 문자열에서의 팰린드롬 길이예요.
javascript
function longestPalindrome(s) {
  const t = "#" + [...s].join("#") + "#";
  const p = new Array(t.length).fill(0);
  let center = 0;
  let right = 0;             // 현재 가장 오른쪽까지 뻗은 팰린드롬
​
  for (let i = 0; i < t.length; i++) {
    if (i < right) p[i] = Math.min(right - i, p[2 * center - i]);
    while (
      i - p[i] - 1 >= 0 &&
      i + p[i] + 1 < t.length &&
      t[i - p[i] - 1] === t[i + p[i] + 1]
    ) {
      p[i]++;
    }
    if (i + p[i] > right) [center, right] = [i, i + p[i]];
  }
​
  let best = 0;
  let at = 0;
  for (let i = 0; i < p.length; i++) {
    if (p[i] > best) [best, at] = [p[i], i];
  }
  const start = (at - best) / 2;
  return s.slice(start, start + best);
}

이번 주 문제

이번 주 진행0 / 4
주차 진행률

셀프 체크

다음 주로 넘어가기 전에 소리 내어 답해 보세요. 막히면 그 부분이 아직 덜 익은 개념이에요.
  1. 트리 DP를 후위 순회 순서로 채우는 이유는 무엇인가요?
  2. dp[v][1] 을 쓸 때 자식에서 dp[child][0] 만 더하는 이유는 무엇인가요?
  3. KMP의 실패 함수 fail[i] 는 정확히 무엇을 담고 있나요?
  4. KMP에서 글자가 어긋났을 때 j 를 0 이 아니라 fail[j-1] 로 되돌리는 이유는 무엇인가요?
← 22주차 · 유니온 파인드와 MST24주차 · 최종 모의고사와 실전 전략 →