풀 리퀘스트를 열면 리뷰 화면이 옛 파일과 새 파일을 나란히 비교한다. 지운 줄 앞에는 -, 더한 줄 앞에는 +가 붙고, 그대로인 줄은 표시 없이 남는다.
import { fetchUser } from './api'
- const user = await fetchUser(id)
+ const user = await fetchUser(id, { cache: 'no-store' })
render(user)좋은 diff는 짧다. 바뀌지 않은 줄을 최대한 많이 "그대로"로 남겨야 리뷰어가 읽을 줄이 줄어든다. 그러면 두 파일에서 순서를 지키며 공통으로 남길 수 있는 줄을 가장 많이 고르는 문제가 된다. 줄이 1,000개씩이면 고를 수 있는 조합은 2의 1,000제곱에 가깝다(줄마다 남긴다/뺀다 두 갈래라 2를 1,000번 곱한 수. 『개발 수학』 Unit 6). 모든 조합을 다 시험하지 않고 어떻게 답을 찾을까?
이 장의 도구는 동적 계획법(dynamic programming, DP)이다. 큰 문제를 작은 문제로 쪼개고, 작은 문제의 답을 표에 적어 두었다가 큰 답을 조립한다. 먼저 가장 작은 예인 피보나치에서 "왜 적어 둬야 하는지"를 보고, 같은 방법으로 diff를 만든다. 개념 정리는 동적 계획법과 재귀 노트에 있다.
같은 계산을 되풀이하는 재귀
피보나치 수는 앞의 두 수를 더한 수다. fib(0) = 0, fib(1) = 1이고, 그 뒤는 다. 정의를 그대로 옮기면 재귀(recursion) 함수 한 줄이다. 이렇게 아무 장치 없이 정의만 옮긴 재귀를 순진한 재귀(naive recursion)라고 부른다.
function fib(n: number): number { if (n <= 1) return n return fib(n - 1) + fib(n - 2)}
정의를 그대로 옮긴 재귀 함수로 fib(5)를 구한다. fib는 모두 몇 번 불릴까? (첫 호출 fib(5)도 센다)
선택지와 해설 보기
실험 순진한 재귀는 같은 문제를 몇 번 다시 풀까
한 줄이 호출 하나입니다. 위에서 아래로 부른 순서, 들여쓰기가 재귀 깊이입니다. 인자를 고르면 같은 호출이 모두 칠해집니다.
- 해볼 것
- fib(5)에서 fib(2)를 골라 몇 번 불렸는지 본다
- fib(6)으로 바꿔 호출 수가 얼마나 느는지 본다
fib(5)의 호출 목록을 위에서 아래로 읽으면 부른 순서가 [5, 4, 3, 2, 1, 0, 1, 2, 1, 0, 3, 2, 1, 0, 1]이다.
fib(5)는 15번 불린다. 그동안 fib(3)은 2번, fib(2)는 3번 처음부터 다시 풀었다. fib(6)은 25번이다. 호출 수는 n이 1 늘 때마다 약 1.6배씩 늘어서, fib(30)은 2,692,537번 불린다. 답은 832,040 하나인데 그 답을 얻으려고 같은 작은 문제를 수십만 번씩 다시 푼다.
메모이제이션: 한 번 푼 답은 적어 둔다
고칠 곳은 하나다. fib(k)를 한 번 풀면 그 답을 어딘가에 적어 두고, 다시 fib(k)가 필요하면 적어 둔 답을 꺼낸다. 이 기법을 (memoization)이라고 한다. 같은 함수에 memo만 더했다.
const memo = new Map<number, number>()function fib(n: number): number { if (n <= 1) return n if (memo.has(n)) return memo.get(n)! const value = fib(n - 1) + fib(n - 2) memo.set(n, value) return value}
실험 한 번 푼 답을 적어 두면
메모를 켜면 이미 푼 fib(k)를 다시 만났을 때 memo에서 꺼내고(점선), 그 아래로는 내려가지 않습니다.
- 해볼 것
- fib(5)에서 메모를 켜고 호출 수를 메모 없을 때와 견줘 본다
- 메모를 켠 채 fib(6)으로 올려 본다
fib(5)의 호출이 15번에서 9번, fib(6)은 25번에서 11번으로 준다. memo가 있으면 fib(k)마다 직접 푸는 것은 한 번뿐이고, 나머지는 memo에서 꺼낸다. fib(2)부터 fib(n)까지 n − 1개를 각각 한 번만 직접 풀고, 풀 때마다 두 번 부르니 호출은 첫 호출 1번 + 2(n − 1)번 = 2n − 1번이다(n = 5면 1 + 8 = 9번. 재귀 호출 수를 세는 법은 『개발 수학』 Unit 7). fib(30)도 59번이다. 지수로 자라던 일(n이 하나 늘 때마다 곱으로 불어나는 증가. Unit 3)이 n에 비례하는 O(n)이 되었고, 대신 memo에 답 n개만큼 메모리를 더 쓴다.
이 변화가 가능했던 이유는 두 가지다.
- 같은 작은 문제가 되풀이된다(겹치는 부분 문제, overlapping subproblems). fib(3)이 여러 번 필요했다.
- 작은 문제의 답으로 큰 문제의 답을 조립할 수 있다(최적 부분 구조, optimal substructure). fib(5)는 fib(4)와 fib(3)의 답만 알면 된다.
두 조건을 갖춘 문제에 답을 적어 두는 방법을 쓰는 것이 동적 계획법이다. 위처럼 큰 문제에서 출발해 재귀로 내려가며 적어 두는 방식을 하향식(top-down), 작은 문제부터 표를 채워 올라가는 방식을 상향식(bottom-up)이라고 한다. Python은 함수에 붙이기만 하면 인자별 결과를 적어 두는 @functools.cache를 표준 라이브러리로 준다. cache는 크기 제한 없는 lru_cache(maxsize=None)와 같다. 공식 문서는 lru_cache로 피보나치를 계산하는 예를 "동적 계획법 기법"이라고 소개한다(Python 문서: functools).
LCS: 표를 채워 공통 줄 세기
다시 diff로 돌아가자. 두 파일에서 순서를 지키며 공통으로 남길 수 있는 가장 긴 줄 목록을 최장 공통 부분 수열(longest common subsequence, LCS)이라고 한다. 부분 수열(subsequence)은 중간을 건너뛰어도 되지만 순서는 바꿀 수 없다.
작은 문제를 이렇게 잡는다. 답을 적어 둘 표를 관례대로 dp라 부르면, dp[i][j] = 옛 파일의 앞 i줄과 새 파일의 앞 j줄의 LCS 길이다. 그러면 칸 하나는 이웃한 세 칸으로 정해진다.
- 옛 파일의 i번째 줄과 새 파일의 j번째 줄이 같으면, 그 줄을 공통으로 남긴다. dp[i][j] = dp[i − 1][j − 1] + 1(왼쪽 위 칸 + 1).
- 다르면 둘 중 한 줄은 공통이 아니다. 옛 줄을 빼 보거나 새 줄을 빼 본 것 중 큰 값을 가져온다. dp[i][j] = max(dp[i − 1][j], dp[i][j − 1])(위 칸과 왼쪽 칸 중 큰 값). 두 줄을 다 빼는 경우(왼쪽 위 칸)는 따로 보지 않아도 된다. 한 줄만 뺀 경우에 이미 들어 있고, 줄을 더 빼서 값이 더 커질 수는 없기 때문이다.
0행과 0열은 빈 파일과 비교한 칸이라 모두 0이다. 위에서 아래로, 왼쪽에서 오른쪽으로 채우면 칸을 채울 때 필요한 이웃 칸은 이미 채워져 있다. 옛 파일 a가 m줄, 새 파일 b가 n줄일 때 코드로는 이렇다.
const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0))for (let i = 1; i <= m; i++) for (let j = 1; j <= n; j++) dp[i][j] = a[i - 1] === b[j - 1] ? dp[i - 1][j - 1] + 1 : Math.max(dp[i - 1][j], dp[i][j - 1])
옛 파일이 ABCD, 새 파일이 ACBD다(글자 하나가 줄 하나). 순서를 지키며 공통으로 남길 수 있는 줄은 최대 몇 개일까?
선택지와 해설 보기
실험 LCS 표를 한 칸씩 채우기
줄 하나를 글자 하나로 줄여 적었습니다. 파란 칸이 방금 채운 칸(같은 줄이면 초록), 노란 칸이 참고한 이웃 칸, ·이 아직 채우지 않은 칸입니다.
| ∅ | A | C | B | D | |
|---|---|---|---|---|---|
| ∅ | 0 | 0 | 0 | 0 | 0 |
| A | 0 | · | · | · | · |
| B | 0 | · | · | · | · |
| C | 0 | · | · | · | · |
| D | 0 | · | · | · | · |
- 해볼 것
- ABCD / ACBD를 끝까지 채워 오른쪽 아래 칸을 본다
- 공통 줄이 하나도 없는 ABC / XYZ도 채워 본다
공통 줄이 하나도 없는 ABC / XYZ는 모든 칸을 계산해도 0이다.
ABCD와 ACBD의 공통 줄 수는 표의 오른쪽 아래 칸에 적힌 3이다. 이 표는 칸 16개를 한 번씩 채우고, 칸마다 이웃 칸을 많아야 두 개만 본다. 옛 파일이 m줄, 새 파일이 n줄이면 시간과 메모리 모두 O(m × n)이다.
표를 거꾸로 읽어 diff 만들기
표의 오른쪽 아래 칸은 공통 줄의 개수만 알려 준다. 어떤 줄을 남기고 어떤 줄을 지웠는지는 그 칸이 어디서 왔는지 거꾸로 따라가면 나온다.
- 두 줄이 같으면 왼쪽 위에서 온 칸이다. 그 줄은 그대로 남은 줄이고, 왼쪽 위로 간다.
- 다르면 왼쪽 칸을 본다. 왼쪽 칸은 새 파일의 j번째 줄을 빼고 비교한 답이다. 그 값이 지금 칸과 같다면 j번째 줄은 공통 줄에 보탠 것이 없다. 곧 새 파일에만 있는 줄, 더한 줄(
+)이고, 왼쪽으로 간다. - 그 밖에는(왼쪽 칸이 지금 칸보다 작으면) 위 칸, 곧 옛 파일의 i번째 줄을 빼고 비교한 답이 지금 칸과 같다. 그 줄은 옛 파일에만 있는 줄, 지운 줄(
-)이고, 위로 간다.
ABCD / ACBD로 한 번만 숫자로 따라가 보자. 오른쪽 아래 칸 dp[4][4] = 3에서 D = D가 같으니 왼쪽 위 dp[3][3]으로 간다. 이 칸은 옛 파일 ABC와 새 파일 ACB를 비교한 답 2다. C ≠ B라서 왼쪽 칸 dp[3][2](ABC와 AC)를 보면 2, 지금 칸과 같다. 새 파일의 셋째 줄 B를 빼도 공통 줄이 2개 그대로이니 B는 새 파일에만 있는 줄, + B다.
실험 표를 거꾸로 읽어 diff 만들기
앞에서 본 방법으로 표를 다 채웠습니다. 오른쪽 아래 칸에서 출발해 왼쪽 위로 갑니다. 초록 칸이 지나온 길, 파란 칸이 지금 칸입니다.
| ∅ | A | C | B | D | |
|---|---|---|---|---|---|
| ∅ | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 1 | 1 | 1 | 1 |
| B | 0 | 1 | 1 | 2 | 2 |
| C | 0 | 1 | 2 | 2 | 2 |
| D | 0 | 1 | 2 | 2 | 3 |
- 해볼 것
- ABCD / ACBD를 끝까지 거꾸로 걸어 B가 -와 +로 한 번씩 나오는 것을 본다
- 한 줄만 바뀐 ABCDE / ABXDE도 걸어 본다
ABCD → ACBD는 - B와 + B가 하나씩 나온다. B 줄이 C 줄 뒤로 옮겨졌는데, LCS는 "옮김"이라는 개념이 없어서 지우고 다시 더한 것으로 적는다. 리뷰 화면에서 코드 블록을 옮겼을 때 통째로 지우고 다시 더한 것처럼 보이는 이유가 이것이다. ABCDE → ABXDE는 한 줄만 바뀌어 - C, + X만 나온다. 왼쪽 칸과 위 칸이 같으면 왼쪽(+)을 먼저 고른다. 끝에서부터 모았으니 위에서 읽으면 지운 줄(-)이 더한 줄(+)보다 위에 온다.
실제 도구는 이 표를 그대로 쓰지 않는다. 1만 줄짜리 파일 두 개를 비교하면 표가 1억 칸이 된다. git의 --diff-algorithm 옵션은 myers, minimal, patience, histogram을 고르게 하고, 기본값인 myers를 문서는 "기본 탐욕(greedy, 매 단계 당장 좋은 쪽을 고르는) diff 알고리즘"이라고 설명한다. minimal은 시간을 더 들여서라도 가장 작은 diff를 만드는 옵션이다(git 문서: git-diff). 알고리즘은 달라도 "공통으로 남길 줄을 최대한 많이 고른다"는 질문은 같다. LCS 표는 그 질문의 답을 가장 단순하게 보여 주는 모델이다.
React는 왜 최소 diff를 포기했나
React도 diff를 한다. 상태가 바뀌면 새로 그린 엘리먼트 트리와 이전 트리를 비교해서 바뀐 곳만 DOM에 반영한다(재조정, 가상 DOM 노트). React 문서는 한 트리를 다른 트리로 바꾸는 최소 연산을 구하는 최신 알고리즘도 트리의 엘리먼트가 n개면 O(n³)이 든다고 적는다. 엘리먼트 1,000개면 = 10억 번 단위의 비교다. 그래서 React는 두 가지 가정을 둔 O(n) 어림 규칙(휴리스틱, heuristic)을 쓴다(React 문서: Reconciliation).
- 타입이 다른 두 엘리먼트는 다른 트리를 만든다.
<div>가<span>으로 바뀌면 그 아래를 비교하지 않고 통째로 새로 만든다. - 개발자가
keyprop으로, 여러 번 렌더링해도 어느 자식이 같은 자식인지 알려 줄 수 있다.
가장 짧은 diff를 포기하는 대신 비교를 엘리먼트 수에 비례하게 만든 선택이다. 대가도 있다. 같은 문서에 따르면 루트 엘리먼트의 타입이 바뀌면 옛 트리를 허물고 새로 만들며, 그 아래 컴포넌트도 모두 언마운트되어 상태를 잃는다. 같은 내용을 감싸는 태그만 바꿔도 그렇다. 또 목록에 key를 주지 않으면 React는 자식을 자리 순서대로(첫째는 첫째와, 둘째는 둘째와) 짝지어 내용을 고쳐 쓴다. 항목을 옮겨도 옮김으로 알아보지 못하니, 옮긴 항목의 상태가 원래 자리에 남을 수 있다. 앞 절의 LCS도 B 줄 옮김을 알아보지 못했다. 둘 다 옮김이라는 개념이 없다는 점이 같다. 어떤 알고리즘이 "같은 것"을 어떻게 알아보는지 알면, 그 알고리즘이 놓치는 경우도 예상할 수 있다.
실무 코드에서 찾아보기
DP 코드는 표와 메모 두 군데에서 자주 틀린다. 표의 행이 서로 다른 배열인지, 메모가 정말 다음 호출까지 살아 있는지 보자.
함정 찾기 AI가 짠 DP 함수 두 개, 어디가 틀렸을까?
“두 문자열의 LCS 길이를 구하는 함수와, 격자에서 장애물(1)을 피해 위·왼쪽 방향 이웃만 거쳐 (0, 0)까지 가는 경로 수를 메모이제이션으로 세는 함수를 짜 줘.”
의심스러운 줄을 모두 눌러 표시한 뒤 “검토 끝”을 누르세요. 함정은 4개입니다.
정리하면 메모가 쓰이지 않는 모양은 셋이다. 메모를 함수 안에서 만들어 호출마다 비고(지수 시간), 0인 답을 memo.get으로 물어 매번 다시 계산하고(memo.has로 묻는다), 구분자 없는 키로 (1, 23)과 (12, 3)이 겹친다. 표는 fill에 배열을 넘겨 모든 행이 한 배열을 가리킨다.
확인 문제 장을 덮기 전에 떠올려 보기
1. 동적 계획법이 효과를 내는 문제의 두 조건은?
2. 옛 파일 m줄, 새 파일 n줄을 LCS 표로 비교할 때 표를 채우는 시간과 메모리는?
3. React가 트리 비교를 O(n)으로 하려고 둔 가정은? (React 문서의 Reconciliation 기준)
더 풀어 보기(선택) · 검색어 오타 추천: 편집 거리
검색창에 form을 쳤는데 상품명에는 from만 있다. 한 글자를 넣기·지우기·다른 글자로 바꾸기를 편집 1번으로 칠 때, 문자열 a를 b로 바꾸는 최소 편집 수(편집 거리, Levenshtein distance)를 구하는 함수를 짜 보자. 이 값이 작은 상품명을 "혹시 이것을 찾으셨나요?"로 보여 줄 수 있다.
cat → cut: 1 form → from: 2