Python 알고리즘

Python으로 Two Sum 문제 풀기

이 레슨에서는 합이 주어진 값이 되는 두 요소를 리스트를 한 번만 훑어서 찾는 Two Sum 문제를 풉니다.

  • 중급
  • 2분 분량
  • 실행 가능한 예제 1개

소개

어떤 문제를 해결하나요

가격 목록과 예산이 있습니다. 어떤 물건 두 개를 사면 정확히 예산만큼이 될까요? 모든 쌍을 확인해도 답은 나오지만 약 n² / 2 번을 비교해야 합니다. 이미 본 값을 기억해 두면 리스트를 한 번만 훑고도 찾을 수 있습니다.

일상 속 비유

Two Sum은 정해진 금액을 딱 맞춰 쇼핑하는 것과 비슷합니다. 가격표를 볼 때마다 모자란 금액을 계산하고 메모를 확인합니다. 정확히 그 가격인 물건을 이미 본 적이 있을까요? 있다면 짝을 찾은 것입니다. 없다면 이 가격과 본 위치를 적어 두고 다음으로 넘어갑니다.

금액 맞춰 쇼핑하기에서 코드로
complement = target - value🤔 아직 모자란 금액
if complement in seen:📋 그 가격이 메모에 있나요?
return [seen[complement], index]🛍️ 짝을 찾았습니다: 두 위치
seen[value] = index✍️ 이 가격과 위치를 적고 계속 갑니다
모든 짝을 확인하는 대신 모자란 금액을 찾아봅니다.
한 문장으로

Two Sum은 리스트에서 더하면 목표 값이 되는 두 수의 위치를 찾는 문제입니다. 이미 본 값을 딕셔너리에 담아 두면 리스트를 한 번만 훑어서 O(n) 시간에 풀 수 있습니다.

핵심 포인트

  1. complement = target - value는 지금 값과 짝을 이루어 목표 합을 만드는 값입니다.
  2. seen은 이미 지나온 값마다 그 인덱스를 짝지어 저장하므로, 값을 빠르게 찾을 수 있습니다.
  3. if complement in seen:은 앞에서 본 값들 가운데 짝이 있는지 확인합니다.
  4. seen[value] = index는 확인한 다음에 저장합니다. 그래서 값이 자기 자신과 짝이 되는 일이 없습니다.
  5. 목표가 9일 때, 값 7은 인덱스 0에 있는 짝 2를 찾아 [0, 1]을 돌려줍니다.

언제 사용하나요?

  • 합이나 차가 주어진 값이 되는 쌍을 찾을 때.
  • 해시 테이블로 메모리를 더 쓰는 대신 속도를 얻는 방법을 배울 때.
  • 코딩 면접에 아주 자주 나오는 문제이고, 3-Sum 같은 문제의 바탕이 됩니다.

필요 없는 경우

  • 입력이 정렬되어 있고 메모리가 빠듯한 경우: 양 끝에서 출발하는 투 포인터 방법은 메모리를 더 쓰지 않습니다.
  • 쌍 하나가 아니라 모든 쌍이 필요한 경우: 처음 찾은 쌍에서 바로 반환하지 말고 결과를 모읍니다.

예제 코드

코드 실행 →
main.py
def two_sum(values, target):
    seen = {}
    for index, value in enumerate(values):
        complement = target - value
        if complement in seen:
            return [seen[complement], index]
        seen[value] = index
    return []

print(two_sum([2, 7, 11, 15], 9))
이 예제의 실행 버튼 만들기

실행 결과

[0, 1]

코드 설명

딕셔너리 seen은 이미 지나온 값과 그 위치를 기록합니다. 프로그램은 각 요소마다 보수 complement = target - value를 계산하고, 그 값이 seen에 이미 있는지 확인합니다. 딕셔너리 조회는 O(1)이므로 알고리즘 전체는 O(n) 시간과 O(n) 추가 메모리로 실행됩니다.

값을 변경하고 Python 설치 없이 CodeUtility 온라인 Python 컴파일러에서 실행하세요.

연습 문제

아래 제안을 따라 코드를 바꿔 보세요. 코드를 직접 고치고 결과를 확인하면 읽기만 할 때보다 레슨을 훨씬 잘 이해할 수 있습니다.

  1. 빈 리스트, 요소가 하나인 리스트, 중복이 있는 리스트로 테스트해 보세요.
  2. 단계마다 상태를 출력해서 알고리즘이 동작하는 모습을 살펴보세요.
  3. 요소 100개, 1,000개, 10,000개로 실행 시간을 재고 다른 방법과 비교해 보세요.
Python 컴파일러에서 실행 →

자주 하는 실수

확인하기 전에 저장하기

값이 자기 자신과 짝이 될 수 있습니다. 예를 들어 3이 하나뿐인데도 3 + 3 = 6이 됩니다.

문제
seen[value] = index
if target - value in seen:
수정
if target - value in seen:
    return [seen[target - value], index]
seen[value] = index

이 레슨을 마쳤나요?

학습 완료로 표시하면 진행 상황을 기록할 수 있습니다.

챌린지로 연습하기

이 레슨에서 배운 내용으로 실제 문제를 풀어 보세요. 모든 챌린지는 브라우저에서 실행되며 즉시 테스트와 AI 리뷰를 받을 수 있습니다.

모든 챌린지