Leetcode 101: Two Sum과 시간 복잡도

1. Two Sum

LeetCode를 풀게되면 만나는 제일 처음 문제는 바로 Two Sum 입니다. 저는 이 문제를 2가지 방법으로 풀 수 있어서 참 좋아합니다. 직관적인 해결 방법과 자료구조로 말이죠. Two Sum 말고, Three Sum, Four Sum등 변형 문제가 참 많은데 Two Sum부터 풀어보도록 하겠습니다.

문제 설명: 정수 배열 nums와 정수 target이 주어질 때, 합이 target이 되는 두 숫자의 인덱스를 반환하는 문제입니다.

제약 조건을 잘 보아야 합니다.

2. 알고리즘 문제를 풀기 전: 시간 복잡도 감각 익히기

우리가 알고리즘 문제를 처음 접했을 때 가장 직관적으로 떠올려야 하는 접근 방식은, 가능한 모든 경우를 직접 대입해 보며 검사하는 것입니다. 흔히 말하는 ‘무식하게 노가다하는 방식’이며, 대부분의 경우 2중 for-loop 형태로 구현할 수 있습니다. 컴퓨터 과학에서는 이러한 모든 경우를 빠짐없이 탐색하는 방식을 무차별대입, Brute Force, 완전 탐색라고 부릅니다.

다만, 실제 풀이를 결정할 때는 반드시 문제에 주어진 제약 사항 (constraint) 중 특히 입력 크기(length) 를 확인해야 합니다. 예를 들어 입력의 길이가 100 이라면 이는 매우 작은 수에 해당합니다. 이처럼 입력 크기가 100처럼 작다면 시간 복잡도가 O(n²)인 알고리즘을 사용하더라도 100² = 10,000회 정도의 반복만 수행하면 되므로, 시간 측면에서 전혀 문제가 되지 않습니다.

그렇다면 어느 정도 큰 수가 되어야 시간 측면에서 문제가 생길까요? 결론부터 말하면 알고리즘 커뮤니티의 경험칙 (Rule of thumb)으로 일반적으로 백준, 프로그래머스, Codeforce, LeetCode, GeeksforGeeks와 같은 온라인 저지 환경에서 연산 횟수가 10⁸을 넘어가면 Brute Force는 어렵다라고 판단합니다. 이유는 대부분의 문제는 1-2초 이내에 동작해야 한다는 시간적 조건이 있기 때문입니다.

3. 왜 1초에 10⁸번인가?

온라인 저지 사이트의 베어메탈 서버, 클라우드 인스턴스의 성능에 따라서 다르지만, 백준을 예시로 들어보겠습니다. 백준의 채점 환경 AWS EC2 인스턴스 스펙은 다음과 같습니다.

[AWS EC2]

조금 더 자세히 살펴보면 언어 컴파일 (최적화) 방법과 버전, 시간 제한, 메모리 제한도 살펴볼 수 있습니다. 예시로 Python의 시간 제한은 x3+2초로 c++보다 넉넉하게 설정되어 있네요.

[Python]

여기서 눈여겨 보아야 할 점은 ‘클럭’ 입니다. 우리가 사용하는 CPU 클럭은 대개 2~4 GHz (기가헤르츠) 입니다. 기가 (Giga)는 10⁹, 즉 10억을 뜻하고, 클럭 2.9 GHz란 1초에 약 29억 번의 사이클을 의미합니다. 엄밀히 말하면 1사이클 == 1번의 CPU 명령 인스트럭션 (instruction)이라고 하기는 어렵지만, 1 cycle = 1 instruction이라고 가정하면 어림잡아 이 CPU는 1초에 약 29억번의 명령을 수행할 수 있습니다.

instruction에는 여러 명령이 포함됩니다 (타입과 추상화 오버헤드, 간단한 변수 할당과 반복 등). 그래서 약 1번의 루프가 10~100번의 instruction을 사용한다고 가정하면, 어림잡아 1초에 10⁸번의 연산을 수행할 수 있다고 이야기할 수 있습니다.

import time

N = 100_000_000
acc = 0
start = time.perf_counter()

for i in range(N):
	acc += i & 1
end = time.perf_counter()

print("acc =", acc)
print(f"Execution time: {end - start:.3f} seconds")

실제로 여러분의 컴퓨터에서 위 코드를 실행시켜 보면 약 N초에 끝나는 것을 볼 수 있습니다. 이처럼 일반적인 채점 환경에서 1초에 처리할 수 있는 단순 연산 횟수가 대략 10⁸회 정도라는 경험칙 (Rule of thumb) 기준을 세워서 문제를 풀어 나가는 게 좋습니다.

이 기준을 적용하면, 입력 크기가 10⁴일 때 O(n²) 알고리즘은 (10⁴)² = 10⁸번의 연산을 필요로 하게 되어 간신히 통과할 수 있는 경계선입니다. 입력 크기가 10⁵ 이상이 되면 O(n²)는 10¹⁰번 연산이 필요해 현실적으로 실행이 불가능합니다. 따라서 이러한 경우에는 O(n²)보다 더 효율적인 시간 복잡도, 예를 들어 O(n log n) 또는 O(n) 수준의 알고리즘을 반드시 고려해야 합니다.

입력 크기별 가이드를 드리면 아래 표를 참고해주세요.

입력 크기별 알고리즘 선택 가이드

입력 크기 제약 (n)최악 시간 복잡도알고리즘적 접근예시 문제
n ≤ 12O(n!)재귀, 백트래킹1부터 n까지의 모든 순열
n ≤ 25O(2ⁿ)재귀, 백트래킹, 비트 마스킹크기가 n인 배열의 모든 부분집합
n ≤ 100O(n⁴)동적 계획법4 Sum
n ≤ 500O(n³)동적 계획법변의 길이가 n보다 작은 모든 삼각형
n ≤ 10⁴O(n²)동적 계획법, 그래프, 트리버블 정렬 (느린 비교 기반 정렬)
n ≤ 10⁶O(n log n)정렬, 이분 탐색, 분할 정복병합 정렬 (빠른 비교 기반 정렬)
n ≤ 10⁸O(n)수학적 접근, 그리디최솟값과 최댓값 찾기
n > 10⁸O(log n) 또는 O(1)수학적 접근, 그리디이분 탐색

4. 1번 풀이: Brute Force

단순히 모든 조건을 만족하는 O(n^2) 2중 for-loop을 설명하기까지 너무나 많은 부연설명을 했네요. 다시 돌아와서 이번 Two Sum 문제의 제약 조건을 다시 보면, nums.length ≤ 10⁴입니다. 앞서 정리한 표에 따르면 n ≤ 10⁴일 때 O(n²)는 경계선이지만 통과 가능한 범위입니다. 10⁴² = 10⁸이고, 이는 대략 1초 안에 처리할 수 있는 연산 횟수이기 때문입니다. 따라서 이 문제는 Brute Force로도 풀 수 있습니다. 모든 (i, j) 쌍을 검사하는 방식이죠.

function twoSum(nums: number[], target: number): number[] {
  for (let i = 0; i < nums.length - 1; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
  return [];
}

시간 복잡도는 O(n²), 공간 복잡도는 O(1)입니다. 그런데 이 방법으로 풀면 뭔가 찜찜합니다. 이렇게 쉬운 문제를…? 더 좋은 방법이 있을까? 속도 측면에서 다른 사람들은 더 빠르게 풀어냅니다.

Runtime

Brute Force Runtime

Memory

Brute Force Memory

5. 2번 풀이: Hash Table

조금 더 낫게 만들 수 있을까요? LeetCode의 Hint 1,2,3을 참고하면 2중 for문을 이용한 brute force는 너무 느릴 수 있습니다. 그래서 hash map을 사용한 아이디어를 생각해볼 수 있습니다.

LeetCode Hint

조금 더 효율적으로 만들 수 있을까요? LeetCode의 Hint를 참고하면, 2중 for문을 이용한 brute force는 최적이 아닙니다. Hash Map을 사용하면 O(n)으로 해결할 수 있습니다.

핵심 아이디어: Complement (보수) 찾기 비유로 설명하면 이렇습니다:

Hash Map이 바로 그 손드는 시스템입니다. 각자 자기가 가진 금액을 key map Dictionary에 등록해두면, 누가 찾든 즉시 응답할 수 있습니다. 즉, 현재 숫자 nums[i]를 보고 있을 때, target - nums[i]를 complement, 보수라고 부릅니다. 이 complement가 이미 등록되어 있다면 정답을 찾은 것이고, 없다면 현재 숫자를 등록해두고 다음으로 넘어갑니다.

예시로 따라가기

nums = [2, 7, 11, 15]
target = 9

i = 0일 때:

nums[0] = 2
complement = 9 - 2 = 7   // "나와 짝이 될 7이 있나?"
map에 7 없음              // "아직 7을 본 적 없네"
→ 나(2)를 등록해둠         // "나중에 누가 2를 찾으면 여기 있다고 알려줘"
map = { 2: 0 }

i = 1일 때:

nums[1] = 7
complement = 9 - 7 = 2   // "나와 짝이 될 2가 있나?"
map에 2 있음! (index 0)   // "2가 index 0에 있네!"
→ 정답: [0, 1]

코드

function twoSum(nums: number[], target: number): number[] {
  const map = new Map<number, number>(); // value -> index
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map.has(complement)) {
      return [map.get(complement)!, i];
    }
    map.set(nums[i], i);
  }
  return [];
}

이처럼 Hash Map은 key를 해시 함수로 변환해 배열 인덱스처럼 직접 접근합니다. 마치 도서관에서 책을 찾을 때 모든 책장을 뒤지는 게 아니라, 청구기호를 보고 바로 해당 위치로 가는 것과 같습니다.

시간 복잡도는 O(n), 공간 복잡도는 O(n)입니다. 1번 풀이보다 메모리를 조금 더 사용하지만, 시간은 훨씬 빠릅니다.

Runtime

Hash Table Runtime

Memory

Hash Table Memory

마무리

제가 처음에 Two Sum 문제를 좋아한다고 말한 이유는, 이 문제가 알고리즘 문제 풀이의 전 과정을 한 번에 압축해서 보여주기 때문입니다. 직관적인 Brute Force 접근에서 출발해, 입력 크기와 시간 복잡도를 따져 보고, 결국 자료구조(Hash Map)를 활용해 한 단계 더 나은 해법으로 발전시키는 흐름까지—알고리즘 사고의 기본 루프가 그대로 담겨 있습니다.

중요한 점은 처음부터 정답 풀이를 떠올릴 필요는 없다는 것입니다. 오히려 ‘이 문제를 가장 단순하게 풀면 어떻게 될까?‘라는 질문에서 시작해, ‘이 방식은 어디까지 허용될까?’, ‘제약 조건을 근거로 더 나은 선택지는 없을까?’ 이 과정을 차분히 밟아가는 것이 진짜 실력으로 이어집니다.

Two Sum은 단순히 배열 문제 하나를 푸는 데서 끝나지 않습니다. Three Sum, Four Sum, 나아가 투 포인터, 슬라이딩 윈도우, 해시 기반 탐색 문제로 확장될 수 있는 출발점입니다. 이 한 문제를 통해 시간 복잡도 감각, 자료구조 선택 기준, 그리고 “왜 이 풀이가 좋은가”를 설명할 수 있다면, 그때부터 알고리즘 문제 풀이가 단순한 암기가 아니라 사고 훈련이 됩니다.

앞으로 LeetCode 문제를 풀 때도, 정답 코드보다 접근 과정과 판단 근거를 먼저 떠올리는 습관을 가져가면 좋겠습니다. 그 습관이 쌓이면, 문제 난이도가 올라가도 결국 같은 질문을 던지며 풀어낼 수 있게 됩니다.

정리

  1. 일단은 직관적으로 떠오르는 방법 (Brute Force)로 풀어본다.
  2. 1초에 약 1억 번(10⁸) 연산을 수행할 수 있음을 경험칙 (Rule of thumb)으로 인지하고 문제를 푼다.
  3. 입력 크기 제약이 10⁴를 초과하면 O(n²)보다 효율적인 알고리즘을 시도한다.
  4. 효율적인 자료구조 (Hash Map 등), 탐색 구조, 알고리즘을 미리 수련하고 적합한 방법을 대입하여 푼다.

Reference