Two Sum을 세 번 풀어야 보이는 것: 불변조건, 인덱스, 해시의 비용

이 글의 문제 발견 출처는 Instagram의 Two Sum 포스트입니다. 원본 캡션·영상·이미지·코드를 복제하거나 변형해 사용하지 않았습니다. 아래 설명, TypeScript 흐름, 실행 trace와 시각화는 입력 계약과 세 알고리즘의 불변조건을 직접 검증하기 위해 독립적으로 다시 구성했습니다.

먼저 결론

Two Sum은 “두 수를 더해 target을 만들라”는 한 줄보다 무엇을 반환하고, 같은 원소를 다시 써도 되는지, 여러 해 중 무엇을 고르는지를 먼저 정해야 하는 문제다. 계약이 흐리면 세 구현이 모두 합은 맞지만 서로 다른 인덱스를 반환하거나, 중복 값 하나를 두 번 사용하거나, JavaScript 숫자 오차 때문에 잘못된 답을 낼 수 있다.

이 글은 다음 계약을 사용한다.

• 입력은 유한한 safe integer로 이루어진 배열 nums와 safe integer target이다.
• 서로 다른 위치 i < j에서 nums[i] + nums[j] === target인 쌍을 찾는다.
• 해가 없으면 null, 있으면 원래 배열의 인덱스 [i, j]를 반환한다.
• 해가 여러 개면 j가 가장 작은 쌍, 그중 i가 가장 작은 쌍을 반환한다.
• 입력 배열은 변경하지 않는다.

이 tie policy를 선택한 이유는 한 번 순회 해시가 왼쪽에서 오른쪽으로 자연스럽게 만족하고, brute force와 정렬 방식도 같은 결과를 내도록 만들 수 있기 때문이다. 다른 정책도 가능하지만 API와 테스트가 한 정책을 공유해야 한다.

보드는 같은 입력을 완전탐색, 정렬된 entry의 투 포인터, 한 번 순회 해시로 실행한다. 한 순간에 코드 한 줄만 강조하고, 현재 index·target·complement, 포인터나 hash state, 발견한 원래 인덱스 쌍과 연산 횟수를 함께 보여준다. frame 수는 wall-clock benchmark가 아니라 상태 전이를 설명하는 도구다.

계약을 코드 타입으로 고정하기

type Pair = readonly [number, number]

function twoSum(
  nums: readonly number[],
  target: number,
): Pair | null

readonly는 호출자의 배열을 정렬하거나 덮어쓰지 않겠다는 의도를 드러낸다. 반환값은 값의 쌍이 아니라 인덱스의 쌍이다. 값만 반환하면 같은 값이 여러 번 나올 때 어느 원소를 사용했는지 잃고, 후속 작업에서 원본 항목을 찾기 어렵다.

입력 검증을 함수 안에서 할지 경계 계층에서 할지도 정해야 한다. 이 글의 복잡도 분석은 이미 검증된 배열을 받는 core algorithm 기준이다. 각 원소의 Number.isSafeInteger를 확인하면 별도 O(n) 전처리가 더해지지만 세 알고리즘의 점근적 상한은 바뀌지 않는다.

세 전략을 한눈에 비교하기

정렬 전략의 O(n) 공간은 원래 인덱스를 잃지 않고 입력도 보존하기 위해 { value, originalIndex } entry를 복사하기 때문이다. 입력을 바꿔도 되고 값만 필요하다면 공간 조건은 달라질 수 있지만, 이 글의 반환 계약에는 원래 인덱스가 필요하다.

1. 완전탐색: 가장 단순한 correctness oracle

tie policy에 맞춰 바깥 loop를 두 번째 인덱스 j, 안쪽 loop를 첫 번째 인덱스 i로 둔다.

for (let j = 1; j < nums.length; j += 1) {
  for (let i = 0; i < j; i += 1) {
    if (nums[i] + nums[j] === target) return [i, j]
  }
}
return null

불변조건

j번째 바깥 반복을 시작할 때, 두 번째 인덱스가 j보다 작은 모든 쌍은 이미 검사되었고 해가 아니었다. 안쪽 반복에서 i는 항상 0 ≤ i < j이므로 같은 원소를 두 번 쓰지 않는다.

왜 맞는가

• 반환했다면 실제로 서로 다른 두 위치의 합을 비교했으므로 sound하다.
• 해 (i, j)가 존재하면 유한한 중첩 loop가 그 쌍을 반드시 방문하므로 complete하다.
• j가 증가하는 순서이고 같은 j에서는 i가 증가하므로 첫 반환이 계약의 tie-break를 만족한다.

비교 횟수는 최악에 n(n-1)/2다. 시간은 O(n²), loop 변수 외 추가 공간은 O(1)이다. n이 작거나 한 번만 실행하고 단순성이 가장 중요할 때는 이 방법이 충분히 좋은 선택이다. 또한 최적화된 구현의 property test oracle로 쓰기 좋다.

2. 정렬 + 투 포인터: 값을 정렬해도 인덱스를 잃지 않기

배열 값만 복사해 정렬하면 원래 인덱스를 반환할 수 없다. 따라서 entry를 만든 뒤 값, 원래 인덱스 순서로 안정적인 총순서를 정한다.

const entries = nums
  .map((value, originalIndex) => ({ value, originalIndex }))
  .sort((a, b) => a.value - b.value || a.originalIndex - b.originalIndex)

let left = 0
let right = entries.length - 1

현재 합이 target보다 작으면 left를 오른쪽으로, 크면 right를 왼쪽으로 옮긴다.

포인터 불변조건

반복 시작 시 left 바깥의 작은 값과 right 바깥의 큰 값은 아직 남은 어떤 entry와도 target을 만들 수 없어서 제거된 상태다.

• entries[left].value + entries[right].value < target이면 현재 left 값은 가장 큰 남은 right와 더해도 작다. 따라서 그 left가 더 작은 어느 값과 짝을 이뤄도 해가 될 수 없다.
• 합이 target보다 크면 현재 right 값은 가장 작은 남은 left와 더해도 크다. 그 right를 더 큰 값과 짝지어도 해가 될 수 없다.

그래서 한 단계 이동할 때 실제 해를 버리지 않는다.

합을 찾자마자 반환하지 않는 이유

일반적인 Two Sum 설명은 첫 일치에서 끝난다. 하지만 그러면 정렬된 값 순서가 반환 쌍을 결정해 “가장 작은 j, 그다음 i” 계약과 다를 수 있다. 이 글의 구현은 같은 값의 left group과 right group에서 가능한 가장 이른 원래 인덱스 후보를 O(group size)에 구해 best와 비교한 뒤, 두 중복 group을 한 번에 건너뛴다.

서로 다른 값 그룹이라면 각 그룹의 가장 작은 원래 index 하나씩이 그 값 조합의 canonical 후보다. 두 포인터의 값이 같다면 target은 그 값의 두 배이고, 같은 그룹에서 원래 index가 가장 작은 두 entry를 고른다. 각 entry는 group scan에 최대 한 번 참여하므로 정렬 뒤 순회는 여전히 O(n)이다.

정렬이 O(n log n), entry 생성과 포인터 순회가 O(n)이므로 전체 시간은 O(n log n), 추가 공간은 O(n)이다. JavaScript의 Array.prototype.sort 구현 세부 비용과 comparator 호출 횟수는 runtime에 따라 달라지지만 이 비교 기반 상한은 유지된다.

3. 한 번 순회 해시: 보수를 먼저 찾고 현재 값을 저장하기

현재 값 x에 필요한 값은 target - x다. 오른쪽 인덱스 j를 증가시키며 왼쪽에서 본 값을 map에 저장한다.

const earliest = new Map<number, number>()

for (let j = 0; j < nums.length; j += 1) {
  const complement = target - nums[j]
  const i = earliest.get(complement)
  if (i !== undefined) return [i, j]
  if (!earliest.has(nums[j])) earliest.set(nums[j], j)
}
return null

핵심 불변조건

j번째 반복의 lookup 직전에 map은 0..j-1 prefix에서 본 각 값의 가장 작은 인덱스를 저장한다. 현재 j는 아직 map에 넣지 않았다.

이 순서가 같은 원소 재사용을 막는다. 예를 들어 [3], target 6에서 먼저 3을 저장하고 같은 반복에서 lookup하면 index 0을 두 번 쓰는 잘못된 답을 만들 수 있다. lookup을 먼저 하면 map의 모든 인덱스가 현재 j보다 작다는 사실이 보장된다.

[3, 3], target 6에서는 j=0에서 보수 3이 없으므로 3 → 0을 저장한다. j=1에서 보수 3을 찾아 [0, 1]을 반환한다. 중복은 문제가 아니라 서로 다른 인덱스가 실제로 두 개 존재해야 한다는 조건이다.

같은 값이 다시 나왔을 때 map을 덮어쓰지 않고 가장 이른 index를 보존하면 동일한 j에서 가장 작은 i가 선택된다. j 자체도 왼쪽에서 오른쪽으로 증가하므로 첫 반환은 공통 tie policy를 만족한다.

Map lookup과 insert를 평균 O(1)로 보면 전체 평균 시간은 O(n), 추가 공간은 최대 서로 다른 값의 수 u에 대해 O(u), 최악 O(n)이다.

세 구현의 공통 correctness

반환 결과의 soundness

세 구현 모두 반환 직전에 다음을 직접 확인한다.

1. 두 원래 인덱스가 다르다.
2. 인덱스를 오름차순으로 반환한다.
3. 두 값의 합이 target과 같다.

정렬 전략은 포인터 위치가 아니라 entry의 originalIndex를 반환해야 한다. 정렬 위치를 반환하면 합은 맞아도 API 결과는 틀린다.

존재하는 해를 놓치지 않는 completeness

• 완전탐색은 모든 i < j를 열거한다.
• 투 포인터는 현재 최솟값 또는 최댓값이 해에 참여할 수 없다는 부등식이 증명될 때만 제거한다.
• 해시는 j에 도달했을 때 그 해의 i가 prefix map에 있고, 따라서 complement lookup이 성공한다.

종료

중첩 loop의 인덱스, 두 포인터 사이 간격, 한 번 순회의 j는 매 단계 유한하게 줄거나 증가한다. 따라서 세 구현 모두 유한 배열에서 종료한다.

중복, 음수, 0, 해 없음

알고리즘은 값의 부호가 아니라 순서와 등식만 사용하므로 음수도 특별 취급할 필요가 없다. 다만 테스트에는 반드시 넣어야 한다.

“해가 정확히 하나 있다”는 코딩 문제의 전제에 기대지 말고, 실제 API라면 no-solution과 multiple-solution 정책을 타입과 문서에 남겨야 한다.

JavaScript Number, overflow와 등식의 의미

JavaScript number는 고정 폭 정수가 아니라 IEEE 754 binary64다. Number.MAX_SAFE_INTEGER를 넘으면 서로 다른 정수가 같은 number로 표현될 수 있고, 덧셈과 뺄셈의 등식이 수학적 정수 등식과 달라질 수 있다.

Number.MAX_SAFE_INTEGER + 1 === Number.MAX_SAFE_INTEGER + 2 // true

그래서 이 글의 계약은 모든 입력과 target을 safe integer로 제한한다. 그것만으로 합이 자동으로 safe하다는 뜻은 아니다. 두 safe integer의 합이나 target - value가 safe 범위를 벗어날 수 있으므로 경계에서 다음 중 하나를 택한다.

• 모든 중간 합과 complement에도 Number.isSafeInteger를 검사하고 범위를 벗어나면 오류를 반환한다.
• 정수 범위가 더 크면 처음부터 bigint 전용 API를 제공한다. number와 bigint는 암묵적으로 섞을 수 없다.
• 부동소수를 지원한다면 === target 대신 허용 오차를 도입해야 하지만, approximate equality는 hash key의 정확한 complement와 맞지 않는다. 이 경우 양자화 규칙이나 다른 문제 정의가 필요하다.

NaN, Infinity, -Infinity는 거부한다. Map은 key 비교에 SameValueZero를 사용해 NaN끼리 같게 보고 0과 -0을 같은 key로 취급한다. 산술 ===와 자료구조 key 의미가 미묘하게 달라지는 입력을 core algorithm까지 들이지 않는 편이 안전하다.

해시는 평균 O(n)이지 무조건 O(n)이 아니다

“Map이 있으니 O(n)”이라고 끝내면 중요한 전제가 빠진다. 해시 방식은 lookup과 insert의 평균 또는 amortized O(1) 을 가정한다. 충돌 처리, resize, hash seed, key 표현은 runtime 구현에 달려 있다. 이론적으로 공격자가 충돌을 통제할 수 있는 table은 한 연산이 O(n), 전체가 O(n²)까지 악화될 수 있다.

JavaScript Map<number, number>는 직접 bucket을 노출하지 않으므로 애플리케이션이 충돌 수를 제어할 수 없다. 신뢰할 수 없는 대규모 입력에서는 다음을 함께 본다.

• runtime의 collision 방어와 version별 동작
• 입력 길이 상한과 CPU budget
• map entry의 실제 memory overhead와 GC pause
• streaming 중 map이 무한히 커지지 않도록 하는 정책
• 장애 시 timeout과 취소 가능성

해시가 원소당 값과 index만 저장한다고 해서 실제 메모리가 16n bytes처럼 단순하지 않다. bucket 여유 공간, object header, pointer, allocator와 GC metadata가 더해진다. peak RSS를 실제 runtime과 데이터 분포에서 측정해야 한다.

결정적 tie-break는 숨은 API 요구다

여러 해가 있을 때 “아무거나” 반환하면 같은 데이터에서도 구현 교체, runtime upgrade, 병렬화에 따라 결과가 달라질 수 있다. 결과가 cache key, UI 선택, replay log에 들어가면 재현성이 깨진다.

이 글의 j 우선, i 차선 정책은 다음처럼 구현된다.

• brute force: j를 바깥 loop로 둔다.
• one-pass hash: j를 증가시키고 value별 가장 이른 i만 보존한다.
• sorted pointers: 모든 matching value group의 canonical 원래-index 후보를 비교한다.

정렬 구현이 첫 합에서 반환하는 더 단순한 정책도 유효하다. 다만 그때는 “세 구현이 같은 쌍을 반환한다”는 테스트를 두면 안 되고, 각 전략의 traversal order를 API 계약으로 공개하거나 반환 결과를 canonicalize해야 한다.

단위 테스트와 property test

예제 몇 개만 통과하는 것으로는 중복과 index 오류를 찾기 어렵다.

표 기반 테스트

• 빈 배열, 길이 1, 길이 2
• 첫 쌍·마지막 쌍·중간 쌍
• 중복 값 두 개와 세 개 이상
• 음수끼리, 음수+양수, 0+0
• 해 없음과 여러 해
• safe integer 경계 안과 경계 밖
• 입력 배열이 호출 전후 동일한지

공통 oracle

작은 random 배열에서는 명백한 O(n²) reference가 canonical 결과를 만들게 하고, 정렬과 해시 결과를 그것과 비교한다. 확인할 성질은 다음과 같다.

1. 결과가 있으면 0 ≤ i < j < n이다.
2. nums[i] + nums[j] === target이다.
3. reference보다 tie-break가 늦은 쌍이 아니다.
4. null이면 reference도 모든 쌍에서 해를 찾지 못한다.
5. 세 함수가 입력을 변경하지 않는다.

trace 자체도 테스트 대상이다. 같은 입력은 같은 frame sequence를 만들고, 모든 frame의 강조 줄은 현재 code listing 안에 있어야 하며, final frame의 pair가 solver 결과와 같아야 한다. UI는 언제나 정확히 한 code line만 active여야 한다.

운영 코드로 확장할 때

결과를 하나가 아니라 모두 반환한다면

모든 index pair를 반환하면 출력 크기 자체가 O(k)다. [0,0,0,...], target 0에서는 k가 O(n²)이므로 어떤 알고리즘도 결과를 쓰는 비용보다 빨라질 수 없다. value pair만 deduplicate할지 index pair를 모두 보존할지도 별도 계약이다.

count만 필요하다면

value별 빈도를 누적하며 현재 complement 빈도를 더하면 O(n) 평균 시간으로 pair 수를 셀 수 있다. 같은 값의 두 index를 세는 조합과 overflow 가능한 큰 count type을 주의한다.

이미 정렬된 입력이라면

값만 필요하거나 원래 위치가 별도 ID로 보존되어 있다면 투 포인터는 O(n) 시간과 O(1) 보조 포인터로 동작할 수 있다. 그러나 원본 인덱스 반환과 non-mutation 계약 때문에 이 글의 구현은 entry copy를 유지한다.

값 범위가 작고 고정돼 있다면

정수 범위가 좁으면 hash map 대신 직접 주소 table이나 bitset을 고려할 수 있다. 메모리는 n이 아니라 값 범위 R에 대해 O(R)이고, bounds validation이 필수다.

streaming 입력이라면

한 번 순회 해시는 앞에서 본 상태만 필요하므로 stream에 자연스럽다. 하지만 no-solution을 확정하려면 stream 종료를 알아야 하고, 무한 stream에서는 memory bound나 window semantics가 필요하다. sliding window Two Sum은 오래된 index를 제거해야 하므로 단순 earliest map과 다른 자료구조가 된다.

선택 기준

마지막 원칙

Two Sum의 핵심은 해시를 외우는 것이 아니다. 반환할 대상, 서로 다른 인덱스라는 조건, prefix에 저장된 상태, 여러 해의 순서, 숫자 등식의 의미를 먼저 적는 것이다. 그 계약이 정해지면 완전탐색은 기준점이 되고, 투 포인터의 제거 규칙과 해시의 complement lookup은 같은 correctness를 서로 다른 시간·공간 비용으로 구현한다.