조던 워크가 제시한 ‘틀린 그림 찾기’라는 비전은 매력적이었지만, 동시에 거대한 기술적 허들을 품고 있었다. 컴퓨터 과학 분야에서 두 개의 트리 구조를 비교하여 차이점을 찾는 것은 ‘Tree-to-tree correction problem’이라 불리는, 결코 간단치 않은 문제였다.
최적의 해법을 찾기 위한 알고리즘의 시간 복잡도는 일반적으로 트리의 노드 개수에 따라 기하급수적으로 증가했다. 페이스북 뉴스피드처럼 수천 개의 노드를 가진 트리를 비교하는 데 이 알고리즘을 그대로 적용했다가는, 배보다 배꼽이 더 커질 터였다.
데이빗은 이 점을 정확히 파고들었다.
“조던, 당신의 아이디어는 결국 두 개의 트리 사이의 최소 편집 거리(Minimum Edit Distance)를 찾는 문제로 귀결됩니다. 이건 O(n³) 복잡도를 가지는 어려운 문제예요. 노드가 1000개만 되어도 연산량은 10억에 육박합니다. 자바스크립트로 이걸 실시간에 처리하는 건 불가능해요.”
데이빗의 지적은 날카로웠고, 이론적으로 완벽했다. 회의실의 공기는 다시 회의적으로 변해갔다. 조던의 아이디어가 학문적으로는 흥미롭지만, 현실 세계에서는 적용 불가능한 탁상공론처럼 보이기 시작했다.
조던은 침착했다. 그는 이미 이 문제에 대해 깊이 고민해 온 터였다.
“데이빗의 말이 맞습니다. 일반적인 두 개의 트리를 비교하는 것은 매우 비싼 작업이죠.”
그는 잠시 말을 멈추고, 숨을 골랐다. 그리고 결정적인 가정을 제시했다.
“하지만 우리가 비교하려는 두 개의 트리는, 아무 상관없는 임의의 트리가 아닙니다.”
모두의 시선이 그에게 집중되었다.
“두 트리는 같은 컴포넌트 구조에서 파생된, 사실상 ‘거의 비슷한’ 트리입니다. 데이터가 조금 바뀌었을 뿐, 전체적인 구조와 형태는 유지될 가능성이 매우 높죠.”
이것이 핵심이었다. 조던은 일반적인 트리 비교 문제에 두 가지 강력한 가정을 추가하여, 문제의 복잡도를 획기적으로 낮추는 휴리스틱(Heuristic) 접근법을 제안했다.
가정 1: 서로 다른 타입의 컴포넌트는 완전히 다른 트리를 생성한다.
만약 이전 트리에서는 <div>였던 노드가 새 트리에서 <span>으로 바뀌었다면, 우리는 그 두 노드가 연관이 있다고 생각하고 차이점을 비교하려 애쓸 필요가 없다. 그냥 이전 <div> 트리를 통째로 버리고, 새로운 <span> 트리를 처음부터 새로 만드는 것이 더 싸다. 즉, <Profile> 컴포넌트가 <PhotoGrid> 컴포넌트로 바뀌는 일은 거의 없으므로, 이런 경우는 과감하게 포기하고 전체를 교체한다.
가정 2: 여러 개의 자식 요소들 사이에서, 개발자는 key라는 속성을 통해 어떤 자식 요소가 동일한 것인지 알려줄 수 있다.
10개의 <li> 목록이 있을 때, 중간에 하나가 추가되거나 순서가 바뀌는 경우를 생각해 보자. 알고리즘은 어떤 <li>가 어떤 <li>로 바뀌었는지 추적하기 어렵다. 하지만 개발자가 각 <li>에 고유한 key값(예: key="user-123")을 붙여준다면, 알고리즘은 이 key를 보고 ‘아, 이 녀석이 아까 그 녀석이구나’라고 즉시 알아챌 수 있다. 그러면 불필요한 비교나 DOM 파괴 없이, 순서만 효율적으로 바꿀 수 있다.
이 두 가지 실용적인 가정을 통해, 조던은 O(n³)의 복잡도를 가진 괴물 같던 문제를, O(n)이라는 거의 선형적인 시간 복잡도로 해결할 수 있다는 청사진을 제시했다.
“우리는 완벽한 최소 편집 거리를 찾는 것을 포기합니다.” 조던이 결론을 내렸다. “대신, 웹 애플리케이션의 특성을 활용한 ‘충분히 좋은’ 비교 알고리즘을 만드는 겁니다. 99%의 경우에 놀랍도록 빠르게 동작하고, 1%의 예외적인 경우에는 조금 비효율적이지만 여전히 작동하는 방식이죠.”
완벽함 대신 실용성을 택한 대담한 절충안.
데이빗은 할 말을 잃었다. 그는 조던이 단순히 꿈을 꾸는 이상주의자가 아니라, 문제의 본질을 꿰뚫고 현실적인 해결책을 제시할 줄 아는 뛰어난 엔지니어임을 인정할 수밖에 없었다.
‘바뀐 부분만 찾아낼 수 있다면…’
그 막연했던 희망이, 이제는 구체적인 알고리즘의 형태로 눈앞에 그려지기 시작했다. 팀원들의 마음속에 있던 의심의 벽이 마침내 허물어지고 있었다.
