Diff 알고리즘 완전 가이드

Diff란 무엇인가

Diff(difference)는 두 텍스트 사이의 차이를 계산하는 알고리즘과 그 결과물을 의미합니다. 1970년대 Unix 시스템에 처음 도입된 이래, 소스 코드 버전 관리(Git), 문서 편집기, 코드 리뷰 도구, 배포 검증 등 소프트웨어 개발의 핵심 인프라로 자리잡았습니다.

Diff의 핵심 목표는 두 시퀀스(보통 텍스트 줄의 배열)에서 최소한의 편집 작업(추가, 삭제)으로 원본을 수정본으로 변환하는 방법을 찾는 것입니다. 이 최소 편집 집합을 최소 편집 거리(Minimum Edit Distance) 또는 레벤슈타인 거리(Levenshtein Distance)라고 합니다.

LCS(최장 공통 부분 수열) 알고리즘

Diff의 수학적 기반은 LCS(Longest Common Subsequence, 최장 공통 부분 수열)입니다. LCS는 두 시퀀스에서 공통으로 등장하는 원소의 최장 순서열을 찾는 알고리즘으로, 동적 프로그래밍(Dynamic Programming)으로 해결합니다.

LCS의 시간 복잡도는 O(mn)으로, m과 n은 각 시퀀스의 길이입니다. 두 줄의 배열에서 LCS를 찾으면, LCS에 포함되지 않은 원소가 곧 변경된 줄들입니다. LCS에 있는 줄 = 변경 없음(context), 원본에만 있는 줄 = 삭제(-), 수정본에만 있는 줄 = 추가(+)로 표시됩니다.

Myers Diff 알고리즘

실제 Git이 사용하는 알고리즘은 Eugene Myers가 1986년 발표한 Myers diff 알고리즘입니다. LCS 기반이지만 O((N+M)D) 시간 복잡도를 가지며, 여기서 D는 최소 편집 거리입니다. 변경이 적은 경우(일반적인 코드 수정) LCS보다 훨씬 빠릅니다.

Myers 알고리즘은 "두 시퀀스 간 최단 편집 경로"를 그래프 최단 경로 문제로 변환합니다. 다이아몬드 모양의 편집 그래프에서 좌측 상단(원본 시작)에서 우측 하단(수정본 끝)으로의 최단 경로를 찾는데, 오른쪽 이동은 추가(+), 아래 이동은 삭제(-), 대각선 이동은 공통 줄(변경 없음)을 의미합니다.

Git diff 출력 해석

Git diff 출력 형식인 Unified diff를 이해하면 코드 리뷰와 변경 추적이 훨씬 쉬워집니다.

diff --git a/src/utils.js b/src/utils.js
index 4b825dc..9f3c2e1 100644
--- a/src/utils.js    # 원본 파일
+++ b/src/utils.js    # 수정본 파일
@@ -10,7 +10,8 @@   # 헝크(hunk) 헤더
 function formatDate(date) {
-  return date.toLocaleDateString();    # 삭제된 줄
+  const options = { year: 'numeric', month: '2-digit', day: '2-digit' };
+  return date.toLocaleDateString('ko-KR', options);  # 추가된 줄
 }

헝크 헤더 @@ -10,7 +10,8 @@는 원본 파일의 10번 줄부터 7줄, 수정본의 10번 줄부터 8줄을 보여준다는 의미입니다. 줄 앞의 공백은 변경 없는 컨텍스트 줄, -는 삭제, +는 추가입니다.

실무 활용: 코드 리뷰

효과적인 코드 리뷰를 위한 diff 활용 전략입니다. 먼저 대규모 리팩토링에서는 의미 없는 공백 변경이 대량의 diff 잡음을 만들 수 있습니다. git diff -w(공백 무시) 옵션으로 실제 로직 변경에 집중하세요. 또한 파일명 변경+내용 변경이 동시에 발생하면 Git이 삭제+신규 파일로 표시할 수 있습니다. git diff -M(이름 변경 감지) 옵션으로 올바르게 표시할 수 있습니다.

Pull Request에서 특정 커밋 범위의 diff를 보려면 git diff commit1..commit2, 특정 파일만 보려면 git diff HEAD~1 -- src/utils.js를 사용합니다.

실무 활용: 배포 전 설정 검증

배포 전 설정 파일 변경 사항을 확인하는 것은 운영 사고 방지의 핵심입니다. 환경 변수 파일(.env), Nginx 설정, 데이터베이스 마이그레이션 스크립트 등을 배포 전에 diff로 검토하는 프로세스를 팀 규칙으로 만들면 실수를 크게 줄일 수 있습니다.

CI/CD 파이프라인에서는 빌드 산출물과 이전 배포본의 주요 파일을 자동으로 diff하여 예상치 못한 변경을 감지하는 단계를 추가할 수 있습니다.

단어 단위 vs 줄 단위 Diff

줄 단위 diff는 전통적인 방식으로 처리 속도가 빠르지만, 한 줄에서 단어 하나만 바뀌어도 전체 줄이 변경으로 표시됩니다. 단어 단위 diff는 더 세밀한 변경을 보여주어 문서 편집이나 한 줄이 긴 코드에 유용합니다.

Git에서는 git diff --word-diff 옵션으로 단어 단위 diff를 볼 수 있습니다. GitHub PR에서는 "Split" 뷰가 줄 단위, "Unified" 뷰가 전통적 unified diff 형식입니다.

자주 묻는 질문

공백 하나 차이로 diff가 크게 나오는 이유는?

줄 단위 diff에서는 공백 하나만 달라져도 전체 줄이 변경으로 표시됩니다. 팀 전체가 동일한 코드 포맷터(Prettier, ESLint)를 사용하고 커밋 전 자동 포맷팅을 적용하면 이 문제를 해결할 수 있습니다. git diff -w로 공백을 무시한 diff도 확인 가능합니다.

바이너리 파일도 diff로 비교할 수 있나요?

일반적인 텍스트 diff는 바이너리 파일에 적용할 수 없습니다. Git은 바이너리 파일에 대해 "Binary files differ"만 표시합니다. 이미지, PDF 등의 바이너리 변경은 해시값 비교로 동일 여부를 확인하는 것이 효율적입니다.

LCS와 Myers diff 중 어느 것이 더 좋은가요?

실제 코드 변경처럼 변경량이 적을 때는 Myers가 훨씬 빠릅니다. 반면 두 파일이 완전히 다른 경우(D가 크다)에는 O(mn)인 LCS가 Myers(O((N+M)D))보다 효율적일 수 있습니다. Git은 기본적으로 Myers를 사용하지만, --diff-algorithm=patience나 --diff-algorithm=histogram으로 대안 알고리즘을 선택할 수 있습니다.

도구 활용

두 텍스트를 브라우저에서 즉시 비교하려면 텍스트 비교 도구를 사용하세요. GitHub 스타일의 좌우 분할 뷰로 추가/삭제/변경 줄을 시각적으로 확인할 수 있습니다.