이미지 로딩 중...
AI Generated
2025. 11. 7. · 3 Views
해시맵으로 투 섬 문제 최적화 완벽 가이드
배열에서 두 수의 합이 목표값이 되는 경우를 찾는 투 섬(Two Sum) 문제를 해시맵을 활용해 O(n²)에서 O(n)으로 최적화하는 방법을 배웁니다. 브루트 포스부터 해시맵 최적화까지 단계별로 이해하고 실전에서 바로 적용할 수 있는 패턴을 익힙니다.
목차
- 투 섬 문제 이해하기
- 브루트 포스 접근법
- 해시맵 기본 개념
- 해시맵을 활용한 투 섬 최적화
- 원패스 해시맵 기법
- 공간복잡도 트레이드오프
- 투 포인터 기법과의 비교
- 중복 처리와 엣지 케이스
1. 투 섬 문제 이해하기
시작하며
여러분이 코딩 인터뷰를 준비하거나 알고리즘 공부를 시작할 때 가장 먼저 만나게 되는 문제가 있습니다. 바로 "배열에서 두 수를 더해서 특정 목표값을 만들 수 있는가?"라는 투 섬(Two Sum) 문제입니다.
예를 들어 [2, 7, 11, 15]라는 배열에서 합이 9가 되는 두 수를 찾으라고 하면, 2와 7의 인덱스인 [0, 1]을 반환해야 합니다. 이 문제는 단순해 보이지만, 실제로는 알고리즘 최적화의 핵심 개념들을 모두 담고 있습니다.
많은 초급 개발자들이 이중 반복문으로 해결하지만, 이는 배열이 커질수록 급격히 느려지는 O(n²) 시간복잡도를 갖습니다. 10,000개의 데이터라면 최대 1억 번의 연산이 필요합니다.
실무에서는 데이터가 수십만, 수백만 개인 경우가 흔합니다. 전자상거래 사이트에서 할인 쿠폰 조합을 찾거나, 금융 앱에서 거래 패턴을 분석할 때 비슷한 문제가 발생합니다.
이럴 때 효율적인 알고리즘이 없다면 사용자는 몇 분씩 기다려야 할 수도 있습니다. 바로 이럴 때 필요한 것이 해시맵을 활용한 최적화입니다.
해시맵을 사용하면 같은 문제를 O(n) 시간에 해결할 수 있어, 1억 번의 연산을 1만 번으로 줄일 수 있습니다.
개요
간단히 말해서, 투 섬 문제는 주어진 정수 배열에서 두 수를 골라 더했을 때 목표값(target)이 되는 쌍을 찾는 문제입니다. 반환값은 보통 두 수의 인덱스이며, 같은 원소를 두 번 사용할 수 없습니다.
왜 이 문제가 중요한지 실무 관점에서 살펴보면, 이는 "빠른 검색"과 "효율적인 자료구조 선택"이라는 프로그래밍의 핵심 주제를 다루기 때문입니다. 예를 들어, 추천 시스템에서 사용자의 선호도 점수 두 개를 조합해 특정 임계값을 넘는 경우를 찾거나, 재고 관리 시스템에서 두 상품의 가격 합이 예산에 맞는지 확인할 때 동일한 패턴을 사용합니다.
전통적인 방법과 비교해보면, 기존에는 모든 가능한 쌍을 일일이 확인하는 이중 루프를 사용했다면, 해시맵을 활용하면 "보완수(complement)"라는 개념을 이용해 한 번의 순회만으로 답을 찾을 수 있습니다. 투 섬 문제의 핵심 특징은 다음과 같습니다: 1) 정확히 두 개의 수를 찾아야 함, 2) 같은 인덱스를 중복 사용할 수 없음, 3) 답이 정확히 하나만 존재한다고 가정할 수 있음(문제 조건에 따라 다름).
이러한 특징들을 이해하면 다양한 변형 문제(Three Sum, Four Sum 등)도 쉽게 해결할 수 있습니다. 마지막으로, 이 문제는 알고리즘 최적화의 "전형적인 패턴"을 보여줍니다.
시간복잡도를 줄이기 위해 추가 공간(해시맵)을 사용하는 "공간-시간 트레이드오프"의 완벽한 예시입니다. 이 패턴은 실무에서 성능 최적화가 필요할 때 반복적으로 사용됩니다.
코드 예제
# 문제 정의: nums 배열에서 target을 만드는 두 수의 인덱스 찾기
def two_sum_problem_definition(nums, target):
"""
예시:
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
설명: nums[0] + nums[1] = 2 + 7 = 9
"""
# 이 함수는 문제 정의를 보여주는 템플릿입니다
# 다음 카드들에서 실제 구현을 배웁니다
pass
# 실제 예시 테스트
nums = [2, 7, 11, 15]
target = 9
# 예상 출력: [0, 1]
# 왜냐하면 nums[0] + nums[1] = 2 + 7 = 9
설명
이것이 하는 일: 투 섬 문제는 주어진 배열을 분석해서 두 원소의 합이 목표값과 일치하는 경우를 찾아내는 탐색 문제입니다. 결과로 두 원소의 인덱스를 반환하며, 이를 통해 실제 값에 접근할 수 있습니다.
문제를 단계별로 나누면 이렇습니다. 첫 번째로, 입력값을 파악해야 합니다.
nums라는 정수 배열과 target이라는 목표값이 주어집니다. 배열의 크기는 n이며, 원소들은 중복될 수 있지만 같은 인덱스를 두 번 사용할 수는 없습니다.
예를 들어 [3, 3]이라는 배열에서 target이 6이라면 [0, 1]을 반환하지만, [3]이라는 배열에서는 같은 인덱스 0을 두 번 쓸 수 없으므로 답이 없습니다. 두 번째 단계는 "보완수(complement)" 개념을 이해하는 것입니다.
현재 보고 있는 수가 x라면, 우리가 찾아야 할 다른 수는 target - x입니다. 예를 들어 target이 9이고 현재 수가 2라면, 7을 찾아야 합니다.
이 개념이 해시맵 최적화의 핵심입니다. 세 번째 단계는 제약 조건을 확인하는 것입니다.
문제에서는 보통 "정확히 하나의 해답만 존재한다"고 가정하지만, 실전에서는 해답이 없거나 여러 개일 수 있습니다. 또한 음수, 0, 중복 값 등의 엣지 케이스도 고려해야 합니다.
여러분이 이 문제 패턴을 마스터하면 다음과 같은 이점을 얻을 수 있습니다: 1) 코딩 인터뷰에서 가장 자주 나오는 유형을 해결할 수 있음, 2) 해시맵을 활용한 최적화 사고방식을 익힐 수 있음, 3) Three Sum, Four Sum 등 더 복잡한 변형 문제로 확장 가능, 4) 실무에서 조합 탐색이 필요한 다양한 문제에 응용 가능. 예를 들어 쇼핑몰에서 "쿠폰 두 개를 조합해 최대 할인을 받는 경우"를 찾는 로직도 같은 패턴입니다.
마지막으로, 이 문제는 알고리즘 공부의 시작점으로 완벽합니다. 간단해 보이지만 브루트 포스, 해시맵, 투 포인터 등 여러 접근법을 비교하며 시간복잡도와 공간복잡도의 트레이드오프를 체감할 수 있기 때문입니다.
실전 팁
💡 문제를 처음 받으면 바로 코딩하지 말고 입출력 예시를 2-3개 직접 손으로 풀어보세요. 패턴이 보이기 시작합니다.
💡 인터뷰에서는 "브루트 포스 방법을 먼저 설명하고, 그 한계를 지적한 후 최적화 방법을 제시"하는 것이 좋은 인상을 줍니다.
💡 반환값이 인덱스인지 실제 값인지 문제에서 명확히 확인하세요. 인덱스를 반환해야 하는데 값을 반환하는 실수가 흔합니다.
💡 "정확히 하나의 해답이 존재한다"는 가정이 있는지 확인하고, 없다면 해답이 없을 때와 여러 개일 때를 각각 처리해야 합니다.
💡 투 섬 문제를 완전히 이해하면 Three Sum, Four Sum, K Sum 같은 변형 문제도 같은 패턴으로 해결할 수 있습니다.
2. 브루트 포스 접근법
시작하며
여러분이 투 섬 문제를 처음 본다면, 가장 직관적으로 떠오르는 방법이 있을 겁니다. "모든 가능한 두 수의 조합을 다 확인해보면 되지 않을까?" 바로 이것이 브루트 포스(무차별 대입) 접근법입니다.
배열의 첫 번째 수를 선택하고, 그 뒤의 모든 수와 더해보면서 target과 일치하는지 확인하는 방식입니다. 이 방법은 확실히 작동합니다.
코드도 직관적이고 이해하기 쉽습니다. 하지만 실무에서는 치명적인 문제가 있습니다.
데이터가 조금만 커져도 급격하게 느려진다는 점입니다. 배열의 크기가 n이라면, 최악의 경우 n×(n-1)/2번의 비교가 필요합니다.
100개의 데이터는 약 5,000번, 1,000개는 약 50만 번, 10,000개는 약 5천만 번의 연산이 필요합니다. 실제 프로젝트에서 이런 일이 일어납니다.
한 전자상거래 스타트업에서 "사용자가 두 쿠폰을 조합해 최대 할인을 받는 기능"을 브루트 포스로 구현했는데, 쿠폰이 수백 개가 넘어가자 페이지 로딩이 몇 초씩 걸리기 시작했습니다. 사용자 경험이 급격히 나빠졌고, 결국 알고리즘을 전면 재작성해야 했습니다.
바로 이럴 때 브루트 포스의 한계를 이해하고 더 나은 방법을 찾아야 합니다. 하지만 브루트 포스를 완전히 무시해서는 안 됩니다.
이는 "올바른 답"을 확실히 찾는 방법이며, 더 복잡한 최적화 알고리즘을 검증할 때 기준점(baseline)으로 사용됩니다.
개요
간단히 말해서, 브루트 포스 접근법은 이중 반복문을 사용해 배열의 모든 가능한 두 수의 조합을 확인하는 방법입니다. 외부 루프는 첫 번째 수를 선택하고, 내부 루프는 그 뒤의 모든 수를 두 번째 수로 선택하여 합을 계산합니다.
왜 이 방법을 배워야 하는지 실무 관점에서 설명하면, 모든 최적화는 "느린 버전"을 먼저 이해해야 가능하기 때문입니다. 브루트 포스는 알고리즘의 정확성을 보장하는 가장 확실한 방법이며, 코딩 인터뷰에서도 "일단 작동하는 해법을 빠르게 제시한 후 최적화하는" 전략이 선호됩니다.
또한 데이터가 매우 작을 때(예: n < 100)는 브루트 포스가 오히려 구현이 간단해서 실용적일 수 있습니다. 전통적인 선형 탐색과 비교하면, 기존에는 "하나의 값을 찾는" 단순 검색이었다면, 여기서는 "두 값의 조합을 찾는" 2차원 탐색입니다.
이는 문제의 복잡도를 O(n)에서 O(n²)로 증가시킵니다. 브루트 포스의 핵심 특징은 다음과 같습니다: 1) 시간복잡도 O(n²)로 느리지만 확실함, 2) 공간복잡도 O(1)로 추가 메모리가 거의 필요 없음, 3) 구현이 직관적이고 버그가 적음.
이러한 특징은 "시간을 희생해 공간을 절약"하는 선택이며, 메모리가 극도로 제한된 임베디드 시스템에서는 유용할 수 있습니다. 실무에서는 브루트 포스를 "프로토타입"으로 먼저 구현한 후, 성능 병목이 확인되면 그때 최적화하는 전략을 씁니다.
도널드 크누스의 유명한 말처럼 "조기 최적화는 만악의 근원"이기 때문입니다. 먼저 작동하는 코드를 만들고, 측정을 통해 병목을 찾은 후, 필요한 부분만 최적화하는 것이 현명합니다.
코드 예제
def two_sum_brute_force(nums, target):
"""브루트 포스: 모든 쌍을 확인하는 O(n²) 해법"""
n = len(nums)
# 외부 루프: 첫 번째 수 선택 (0부터 n-2까지)
for i in range(n - 1):
# 내부 루프: 두 번째 수 선택 (i+1부터 n-1까지)
# i+1부터 시작해서 같은 인덱스 중복 사용 방지
for j in range(i + 1, n):
# 두 수의 합이 target과 일치하면 인덱스 반환
if nums[i] + nums[j] == target:
return [i, j]
# 답을 찾지 못한 경우 (문제 조건상 항상 답이 있다면 이 줄은 실행 안 됨)
return None
# 테스트
result = two_sum_brute_force([2, 7, 11, 15], 9)
print(result) # 출력: [0, 1]
설명
이것이 하는 일: 브루트 포스 알고리즘은 배열의 모든 가능한 두 수의 조합을 체계적으로 확인합니다. 외부 루프가 한 단계 진행할 때마다 내부 루프는 나머지 모든 원소를 확인하므로, 어떤 조합도 놓치지 않습니다.
첫 번째 단계로, 외부 루프는 인덱스 i를 0부터 n-2까지 순회합니다. n-1까지 가지 않는 이유는 마지막 원소는 이미 이전 단계들에서 두 번째 수로 모두 확인되었기 때문입니다.
예를 들어 [2, 7, 11, 15]에서 i=0일 때 nums[0]=2가 첫 번째 수로 선택됩니다. 두 번째 단계로, 내부 루프는 j를 i+1부터 n-1까지 순회합니다.
i+1부터 시작하는 것이 핵심인데, 이렇게 하면 1) 같은 인덱스를 두 번 사용하지 않고, 2) 이미 확인한 조합(예: [0,1])을 다시 확인하지 않습니다([1,0]은 같은 조합). i=0, j=1일 때 2+7=9를 계산하고, target 9와 일치하므로 [0, 1]을 반환합니다.
세 번째 단계는 조건 확인입니다. nums[i] + nums[j] == target이 참이면 즉시 [i, j]를 반환하고 함수를 종료합니다.
이를 "조기 반환(early return)"이라고 하며, 답을 찾았는데도 불필요하게 나머지를 확인하지 않게 합니다. 만약 모든 루프를 다 돌았는데도 답을 못 찾으면 None을 반환합니다(문제 조건상 항상 답이 있다면 이 경우는 발생하지 않음).
성능 분석을 해보면, 최악의 경우 답이 배열의 마지막 두 원소일 때 모든 조합을 확인해야 합니다. n=4일 때 비교 횟수는 3+2+1=6번, n=5일 때 4+3+2+1=10번, 일반적으로 n(n-1)/2번입니다.
이는 O(n²) 시간복잡도를 의미하며, n이 두 배가 되면 실행 시간은 약 네 배가 됩니다. 반면 공간복잡도는 O(1)로, 변수 i, j, n만 사용하므로 추가 메모리가 거의 없습니다.
여러분이 이 코드를 실무에서 사용한다면, 데이터 크기를 반드시 고려해야 합니다. n < 1,000 정도라면 밀리초 단위로 실행되므로 괜찮지만, n > 10,000이면 눈에 띄게 느려집니다.
웹 API의 경우 응답 시간이 200ms를 넘으면 사용자가 느리다고 느끼므로, 큰 데이터에서는 최적화가 필수입니다.
실전 팁
💡 이중 루프를 쓸 때 range(i+1, n)처럼 i+1부터 시작하는 패턴을 기억하세요. 이는 조합 문제에서 중복을 제거하는 표준 기법입니다.
💡 디버깅할 때 작은 배열(예: [1, 2, 3])로 테스트하면서 몇 번의 비교가 일어나는지 세어보세요. 시간복잡도를 체감할 수 있습니다.
💡 코딩 인터뷰에서는 "이 방법은 O(n²)이므로 큰 데이터에서는 느립니다. 해시맵을 쓰면 O(n)으로 개선할 수 있습니다"라고 말하며 다음 단계로 넘어가세요.
💡 브루트 포스를 "정답 검증용 기준 코드"로 남겨두면, 최적화한 코드의 결과와 비교해 버그를 찾을 수 있습니다.
💡 만약 문제에서 "모든 해답을 찾으라"고 하면 return 대신 결과 리스트에 추가하고 계속 탐색해야 합니다.
3. 해시맵 기본 개념
시작하며
여러분이 전화번호부에서 친구의 번호를 찾는다고 상상해보세요. 만약 처음부터 끝까지 한 줄씩 읽으면서 찾는다면 엄청나게 오래 걸릴 겁니다.
하지만 실제로는 이름의 첫 글자를 보고 해당 섹션을 바로 펼치죠. "김"으로 시작하면 앞쪽, "최"로 시작하면 뒤쪽을 바로 찾습니다.
이것이 바로 해시맵의 원리입니다. 해시맵(HashMap, 파이썬에서는 딕셔너리)은 "키를 값으로 변환하는 마법의 상자"입니다.
배열에서 특정 값을 찾으려면 처음부터 끝까지 확인해야 하는 O(n) 시간이 걸리지만, 해시맵에서는 평균적으로 O(1), 즉 상수 시간에 찾을 수 있습니다. 데이터가 1개든 100만 개든 찾는 시간은 거의 같습니다.
실무에서 해시맵은 어디에나 있습니다. 웹 애플리케이션의 세션 저장소, 데이터베이스의 인덱스, 캐시 시스템, 중복 제거 로직 등 "빠른 검색"이 필요한 모든 곳에서 사용됩니다.
예를 들어 유튜브가 "이미 본 동영상" 목록을 관리할 때 배열을 쓴다면 매번 수천 개를 검색해야 하지만, 해시맵을 쓰면 즉시 확인할 수 있습니다. 바로 이 해시맵을 투 섬 문제에 적용하면, O(n²)의 브루트 포스를 O(n)으로 극적으로 개선할 수 있습니다.
이는 알고리즘 최적화의 가장 강력한 패턴 중 하나입니다.
개요
간단히 말해서, 해시맵은 키-값 쌍을 저장하는 자료구조로, 키를 통해 값을 평균 O(1) 시간에 찾을 수 있습니다. 내부적으로는 해시 함수를 사용해 키를 배열 인덱스로 변환하여 저장하므로, 직접 접근이 가능합니다.
왜 이것이 투 섬 문제에서 중요한지 설명하면, "이미 본 값들을 기억해두고, 현재 값의 보완수가 있는지 즉시 확인"할 수 있기 때문입니다. 예를 들어 target이 9이고 현재 값이 7이라면, "2를 이미 봤나?"를 O(1)에 확인할 수 있습니다.
배열로는 다시 처음부터 찾아야 하므로 O(n)이 걸립니다. 기존 배열 탐색과 비교하면, 배열에서 in 연산자나 index() 메서드는 선형 탐색으로 O(n)이지만, 해시맵에서 in 연산자나 get() 메서드는 평균 O(1)입니다.
이는 10,000개 데이터에서 10,000배의 속도 차이를 만들 수 있습니다. 해시맵의 핵심 특징은 다음과 같습니다: 1) 평균 O(1) 탐색/삽입/삭제 시간, 2) 키는 고유해야 하며(중복 불가), 값은 중복 가능, 3) 순서가 보장되지 않음(파이썬 3.7+ 딕셔너리는 삽입 순서 유지), 4) 추가 메모리 O(n) 필요.
투 섬 문제에서는 시간을 극적으로 줄이기 위해 공간을 조금 더 사용하는 "시간-공간 트레이드오프"를 선택합니다. 파이썬에서 해시맵은 딕셔너리 {}로 표현되며, JavaScript는 Object나 Map, Java는 HashMap, C++은 unordered_map입니다.
문법은 다르지만 핵심 개념은 동일하므로, 한 언어에서 배우면 다른 언어로 쉽게 전환할 수 있습니다.
코드 예제
# 해시맵 기본 연산 데모
hash_map = {} # 빈 해시맵 생성
# 삽입 연산: O(1)
hash_map[2] = 0 # 키 2에 값 0 저장
hash_map[7] = 1 # 키 7에 값 1 저장
hash_map[11] = 2
# 탐색 연산: O(1)
if 7 in hash_map: # 키 7이 존재하는지 확인
print(f"값 7의 인덱스: {hash_map[7]}") # 출력: 값 7의 인덱스: 1
# get 메서드: 키가 없을 때 기본값 반환
index = hash_map.get(15, -1) # 15가 없으면 -1 반환
print(f"15의 인덱스: {index}") # 출력: 15의 인덱스: -1
# 투 섬 문제 적용: "보완수" 확인
target = 9
current_value = 7
complement = target - current_value # 2
if complement in hash_map: # 2가 해시맵에 있나? O(1)
print(f"답 찾음: [{hash_map[complement]}, 현재 인덱스]")
설명
이것이 하는 일: 해시맵은 내부적으로 해시 함수를 사용해 키를 배열 인덱스로 변환하고, 그 위치에 값을 저장합니다. 따라서 키를 알면 계산 한 번으로 저장 위치를 바로 찾아갈 수 있어 O(1) 시간이 걸립니다.
첫 번째로, 삽입 연산을 이해해봅시다. hash_map[key] = value 문법은 내부적으로 이렇게 동작합니다: 1) 키를 해시 함수에 넣어 정수(해시값)를 얻음, 2) 해시값을 배열 크기로 나눈 나머지로 인덱스 계산, 3) 그 인덱스에 값 저장.
예를 들어 hash(7) % 10 = 7이면 배열의 7번 위치에 저장됩니다. 충돌(같은 인덱스에 여러 키)이 발생하면 체이닝이나 오픈 어드레싱으로 처리하지만, 이는 내부 구현 디테일이므로 사용자는 신경 쓸 필요 없습니다.
두 번째로, 탐색 연산을 봅시다. key in hash_map은 같은 해시 함수로 키의 위치를 계산한 후 그곳을 바로 확인합니다.
배열처럼 처음부터 끝까지 찾지 않으므로 O(1)입니다. hash_map.get(key, default)는 키가 있으면 값을 반환하고, 없으면 기본값을 반환하는 안전한 방법입니다.
hash_map[key]를 직접 쓰면 키가 없을 때 KeyError가 발생하므로 주의해야 합니다. 세 번째로, 투 섬 문제에 적용하는 방법입니다.
배열을 순회하면서 각 값을 해시맵에 저장합니다. 현재 값이 x라면 complement = target - x를 계산하고, complement가 해시맵에 있는지 O(1)에 확인합니다.
있다면 이전에 본 값이므로 답을 찾은 것입니다. 예를 들어 [2, 7, 11, 15]에서 target=9일 때: 1) 2를 보고 해시맵에 저장 {2: 0}, 2) 7을 보고 complement=9-7=2를 확인, 3) 2가 해시맵에 있으므로 [0, 1] 반환.
시간복잡도 분석을 해보면, 해시맵의 평균 시간복잡도는 O(1)이지만 최악의 경우(모든 키가 충돌)는 O(n)입니다. 하지만 현대 해시맵 구현은 충돌을 최소화하도록 설계되어 실무에서는 거의 O(1)로 동작합니다.
공간복잡도는 O(n)인데, 최악의 경우 모든 원소를 해시맵에 저장하기 때문입니다. 여러분이 해시맵을 사용할 때 주의할 점은, 키로 사용할 수 있는 타입은 불변(immutable) 타입만 가능하다는 것입니다.
파이썬에서는 int, str, tuple은 가능하지만 list, dict는 불가능합니다. 이는 해시값이 변하지 않아야 하기 때문입니다.
또한 해시맵은 순서를 보장하지 않으므로(파이썬 3.7+ 제외), 순서가 중요하다면 OrderedDict나 다른 자료구조를 고려해야 합니다.
실전 팁
💡 파이썬에서 딕셔너리 접근 시 KeyError를 방지하려면 get() 메서드나 if key in dict 체크를 사용하세요. get(key, default)가 특히 유용합니다.
💡 해시맵의 시간복잡도는 "평균 O(1)"이지만 최악 O(n)임을 기억하세요. 인터뷰에서는 "평균적으로 O(1)"이라고 정확히 표현하는 것이 좋습니다.
💡 투 섬 문제에서는 {값: 인덱스} 형태로 저장합니다. 키와 값을 바꾸지 않도록 주의하세요. 값이 키가 되어야 나중에 "이 값을 봤는지" 확인할 수 있습니다.
💡 메모리가 제한적인 환경이라면 해시맵의 O(n) 공간복잡도가 부담될 수 있습니다. 이럴 때는 투 포인터 같은 O(1) 공간 알고리즘을 고려하세요.
💡 충돌을 최소화하려면 해시맵의 초기 크기를 적절히 설정하세요. 파이썬은 자동으로 관리하지만, Java나 C++에서는 예상 크기를 생성자에 전달할 수 있습니다.
4. 해시맵을 활용한 투 섬 최적화
시작하며
여러분이 지금까지 브루트 포스의 O(n²) 한계와 해시맵의 O(1) 탐색 능력을 배웠다면, 이제 이 둘을 결합할 시간입니다. 핵심 아이디어는 간단합니다: "배열을 한 번만 순회하면서, 각 원소에 대해 '보완수를 이미 봤는지' 해시맵에서 즉시 확인하는 것"입니다.
이렇게 하면 이중 루프가 필요 없습니다. 구체적으로 설명하면, 현재 값이 7이고 target이 9라면, 우리가 찾아야 할 값은 2입니다.
브루트 포스에서는 배열의 나머지 부분을 다시 탐색했지만, 해시맵을 쓰면 "2를 이전에 봤는지" 한 번의 조회로 알 수 있습니다. 이전에 2를 봤다면 그 인덱스가 해시맵에 저장되어 있으므로 바로 답을 반환합니다.
실무에서 이 최적화는 극적인 차이를 만듭니다. 한 금융 앱에서 사용자의 거래 내역 중 "두 거래의 합이 특정 금액"인 경우를 찾는 기능이 있었습니다.
초기 브루트 포스 구현은 거래가 1만 건을 넘자 30초 이상 걸렸지만, 해시맵으로 바꾼 후 0.1초 이내로 완료되었습니다. 300배의 성능 향상입니다.
이 패턴은 투 섬뿐만 아니라 "중복 찾기", "애너그램 그룹핑", "서브어레이 합" 등 수많은 문제에 응용됩니다. 한 번 마스터하면 알고리즘 문제 해결 능력이 크게 향상됩니다.
개요
간단히 말해서, 해시맵 투 섬은 배열을 한 번 순회하면서 각 원소와 그 인덱스를 해시맵에 저장하고, 동시에 현재 원소의 보완수가 이미 해시맵에 있는지 확인하는 O(n) 알고리즘입니다. 보완수가 있으면 즉시 두 인덱스를 반환합니다.
왜 이것이 강력한지 실무 관점에서 보면, 시간복잡도를 O(n²)에서 O(n)으로 줄이면서도 코드는 여전히 간결하고 이해하기 쉽기 때문입니다. 이는 "공간을 조금 더 써서 시간을 크게 절약"하는 전형적인 트레이드오프입니다.
대부분의 실무 상황에서 메모리는 충분하지만 사용자는 빠른 응답을 원하므로, 이 선택이 합리적입니다. 브루트 포스와 비교하면, 브루트 포스는 각 원소마다 나머지 모든 원소를 확인(O(n) × n번)했지만, 해시맵 방식은 각 원소마다 해시맵 한 번만 확인(O(1) × n번)합니다.
이중 루프가 단일 루프로 줄어든 것입니다. 이 알고리즘의 핵심 특징은 다음과 같습니다: 1) 시간복잡도 O(n)으로 선형 시간에 해결, 2) 공간복잡도 O(n)으로 해시맵에 최대 n개 원소 저장, 3) "투 패스" 방식으로 먼저 해시맵을 구축한 후 탐색, 4) 같은 인덱스 중복 사용을 자동으로 방지.
다음 카드에서는 이를 더 개선한 "원패스" 방식도 배웁니다. 실무에서 이 패턴을 적용할 때는, 문제가 "빠른 탐색"을 필요로 하는지 먼저 판단해야 합니다.
만약 "이 값을 이전에 봤는가?"나 "이 값의 쌍이 있는가?" 같은 질문이 반복된다면, 해시맵이 거의 항상 최선의 선택입니다.
코드 예제
def two_sum_hash_map(nums, target):
"""해시맵 투패스: O(n) 시간, O(n) 공간"""
hash_map = {} # 값을 키로, 인덱스를 값으로 저장
# 첫 번째 패스: 모든 원소를 해시맵에 저장
for i, num in enumerate(nums):
hash_map[num] = i
# 두 번째 패스: 각 원소의 보완수를 해시맵에서 찾기
for i, num in enumerate(nums):
complement = target - num # 찾아야 할 값
# 보완수가 해시맵에 있고, 같은 인덱스가 아닌지 확인
if complement in hash_map and hash_map[complement] != i:
return [i, hash_map[complement]]
return None # 답이 없는 경우
# 테스트
result = two_sum_hash_map([2, 7, 11, 15], 9)
print(result) # 출력: [0, 1]
설명
이것이 하는 일: 이 알고리즘은 "투 패스(두 번 순회)" 방식으로, 첫 번째 순회에서 모든 값을 해시맵에 저장하고, 두 번째 순회에서 각 값의 보완수가 해시맵에 있는지 확인합니다. 보완수를 찾으면 두 인덱스를 즉시 반환합니다.
첫 번째 단계인 "해시맵 구축"을 봅시다. for i, num in enumerate(nums)는 인덱스와 값을 동시에 가져옵니다.
hash_map[num] = i는 "값을 키로, 인덱스를 값으로" 저장합니다. 예를 들어 [2, 7, 11, 15]는 {2: 0, 7: 1, 11: 2, 15: 3}으로 변환됩니다.
만약 배열에 중복 값이 있다면 나중 인덱스로 덮어씌워지지만, 투 섬 문제에서는 일반적으로 문제없습니다(같은 값을 두 번 쓸 수 있다면). 두 번째 단계인 "보완수 탐색"을 봅시다.
다시 배열을 순회하면서 각 num에 대해 complement = target - num을 계산합니다. target=9, num=2라면 complement=7입니다.
그 다음 if complement in hash_map으로 7이 해시맵에 있는지 O(1)에 확인합니다. 있다면 이전에 7을 봤다는 뜻이므로, 7의 인덱스(hash_map[7]=1)와 현재 인덱스(0)를 반환합니다.
세 번째 단계는 "같은 인덱스 중복 방지"입니다. hash_map[complement] != i 조건은 중요합니다.
예를 들어 [3, 2, 4]에서 target=6이면, 3을 볼 때 complement=3인데, 해시맵에도 3이 있습니다. 하지만 같은 인덱스 0을 두 번 쓸 수는 없으므로 이 조건으로 걸러냅니다.
나중에 2를 보면 complement=4를 찾고, 4의 인덱스 2와 2의 인덱스 1을 반환하여 정답 [1, 2]를 얻습니다. 시간복잡도 분석을 하면, 첫 번째 루프는 O(n), 두 번째 루프도 O(n), 해시맵 조회는 O(1)이므로 전체는 O(n) + O(n) = O(n)입니다.
공간복잡도는 해시맵이 최대 n개 원소를 저장하므로 O(n)입니다. 브루트 포스의 O(n²) 시간, O(1) 공간과 비교하면, 시간을 획기적으로 줄이는 대신 공간을 조금 더 사용합니다.
여러분이 이 코드를 실무에 적용하면, 데이터가 10,000개일 때 브루트 포스는 약 5천만 번 비교하지만 이 방법은 2만 번(구축 1만 + 탐색 1만)만 수행합니다. 2,500배의 향상입니다.
실제 실행 시간으로는 수 초가 수 밀리초로 줄어드는 체감 차이를 느낄 수 있습니다. 또한 이 패턴은 "Group Anagrams", "Contains Duplicate" 등 수많은 LeetCode 문제에 그대로 적용됩니다.
실전 팁
💡 해시맵을 {값: 인덱스} 형태로 저장하는 이유를 명확히 이해하세요. 나중에 "이 값을 봤는지"와 "그 인덱스는 몇 번인지"를 동시에 알아야 하기 때문입니다.
💡 hash_map[complement] != i 조건을 빼먹으면 틀립니다. 디버깅할 때 [3, 3] target=6 같은 엣지 케이스로 테스트하세요.
💡 enumerate(nums)는 파이썬에서 인덱스와 값을 동시에 가져오는 관용구입니다. 다른 언어에서는 for (int i = 0; i < n; i++) 형태로 작성합니다.
💡 투 패스 방식은 이해하기 쉽지만, 다음 카드에서 배울 원패스 방식이 더 효율적이고 면접에서 선호됩니다. 두 방법을 모두 알아두세요.
💡 만약 문제가 "인덱스 대신 값을 반환하라"고 하면 [nums[i], nums[hash_map[complement]]]로 바꾸면 됩니다. 문제 요구사항을 정확히 읽으세요.
5. 원패스 해시맵 기법
시작하며
여러분이 방금 배운 투 패스 해시맵은 이미 훌륭하지만, 한 가지 개선할 점이 있습니다. "왜 배열을 두 번 순회해야 하지?
한 번에 할 수는 없을까?" 실제로 가능합니다. 원패스(One-Pass) 기법은 배열을 한 번만 순회하면서 해시맵 구축과 보완수 탐색을 동시에 수행합니다.
핵심 아이디어는 "현재 값을 해시맵에 저장하기 전에, 먼저 보완수가 있는지 확인하는 것"입니다. 예를 들어 [2, 7]에서 target=9일 때, 2를 보면 complement=7을 찾지만 아직 해시맵이 비어있으므로 2를 저장합니다.
그 다음 7을 보면 complement=2인데, 2가 이미 해시맵에 있으므로 즉시 답을 찾습니다. 7은 저장할 필요도 없이 바로 반환합니다.
실무에서는 작은 차이처럼 보이지만, 원패스가 더 효율적입니다. 메모리 접근이 절반으로 줄고, 캐시 효율성도 좋아집니다.
또한 코드가 더 간결하고, 코딩 인터뷰에서 "더 최적화된 버전"을 보여줄 수 있어 좋은 인상을 줍니다. 구글, 아마존 같은 빅테크 면접에서는 원패스 버전을 기대합니다.
이 기법을 이해하면 "순회하면서 동시에 처리"하는 패턴을 익히게 됩니다. 이는 스트리밍 데이터 처리, 온라인 알고리즘, 메모리 제한이 있는 환경에서 자주 사용되는 실전 기법입니다.
개요
간단히 말해서, 원패스 해시맵은 배열을 순회하면서 각 원소에 대해 1) 먼저 보완수가 해시맵에 있는지 확인하고, 2) 없다면 현재 원소를 해시맵에 추가하는 방식입니다. 보완수를 찾으면 즉시 반환하므로 나머지 원소를 볼 필요도 없습니다.
왜 이것이 투 패스보다 나은지 설명하면, 실제 연산 횟수가 절반 가까이 줄어들기 때문입니다. 투 패스는 n번 삽입 + n번 조회 = 2n번이지만, 원패스는 평균적으로 n번의 조회와 몇 번의 삽입만 수행합니다(답을 찾으면 중단하므로).
또한 코드가 더 간결하고, 공간도 약간 절약됩니다(모든 원소를 저장하지 않을 수 있음). 투 패스와 비교하면, 투 패스는 "모든 정보를 먼저 수집한 후 분석"하는 배치 처리이고, 원패스는 "데이터를 보는 즉시 처리"하는 스트리밍 처리입니다.
원패스는 메모리 효율성이 더 좋고, early return으로 불필요한 연산을 줄입니다. 원패스의 핵심 특징은 다음과 같습니다: 1) 시간복잡도 여전히 O(n)이지만 상수 계수가 더 작음, 2) 공간복잡도 O(n)이지만 평균적으로 더 적게 사용, 3) 답을 찾으면 즉시 반환하므로 조기 종료 가능, 4) 같은 인덱스 중복 문제가 자동으로 해결됨(현재 값을 저장하기 전에 확인하므로).
이는 투 패스의 hash_map[complement] != i 조건이 필요 없다는 의미입니다. 코딩 인터뷰에서는 원패스 버전을 먼저 제시하면 "최적화 사고"를 보여줄 수 있습니다.
면접관이 "더 개선할 수 있나요?"라고 물으면 "투 패스를 원패스로 줄이면 메모리 접근을 절반으로 줄일 수 있습니다"라고 답하면 됩니다.
코드 예제
def two_sum_one_pass(nums, target):
"""해시맵 원패스: O(n) 시간, 더 효율적인 구현"""
hash_map = {} # 값: 인덱스 매핑
# 한 번의 순회로 해결
for i, num in enumerate(nums):
complement = target - num # 찾아야 할 값
# 보완수가 이미 해시맵에 있으면 답 찾음!
if complement in hash_map:
# 보완수의 인덱스가 먼저, 현재 인덱스가 나중
return [hash_map[complement], i]
# 보완수가 없으면 현재 값을 해시맵에 저장
hash_map[num] = i
return None # 답이 없는 경우
# 테스트
result = two_sum_one_pass([2, 7, 11, 15], 9)
print(result) # 출력: [0, 1]
설명
이것이 하는 일: 원패스 알고리즘은 배열을 처음부터 끝까지 한 번만 순회하면서, 각 원소를 볼 때마다 "이 값의 보완수를 이미 봤는가?"를 먼저 확인하고, 없다면 현재 값을 해시맵에 기록합니다. 보완수를 찾는 순간 즉시 답을 반환하므로 나머지는 확인할 필요가 없습니다.
첫 번째 단계로, 각 원소를 순회하면서 complement = target - num을 계산합니다. 예를 들어 [2, 7, 11, 15]에서 target=9일 때, i=0, num=2라면 complement=7입니다.
이제 "7을 이전에 봤는가?"를 확인합니다. 현재 해시맵은 {}로 비어있으므로 7이 없습니다.
따라서 현재 값 2를 저장합니다: hash_map = {2: 0}. 두 번째 단계로, i=1, num=7일 때 complement=2를 계산합니다.
if complement in hash_map으로 확인하면 2가 해시맵에 있습니다! 이는 이전에 2를 봤다는 뜻입니다.
2의 인덱스는 hash_map[2]=0이고 현재 인덱스는 1이므로 [0, 1]을 반환합니다. 이 시점에서 함수가 종료되므로 11과 15는 확인하지 않습니다.
이것이 조기 반환(early return)의 이점입니다. 세 번째 단계로, 왜 같은 인덱스 중복 문제가 자동으로 해결되는지 봅시다.
투 패스에서는 모든 값을 먼저 저장하므로 hash_map[complement] != i 조건이 필요했습니다. 하지만 원패스에서는 현재 값을 저장하기 전에 보완수를 확인하므로, 현재 값과 보완수가 같다면 해시맵에 아직 저장되지 않았습니다.
예를 들어 [3, 2, 4]에서 target=6일 때, 3을 보면 complement=3인데 해시맵에 없으므로 3을 저장합니다. 같은 인덱스를 두 번 쓰는 문제가 발생하지 않습니다.
시간복잡도는 여전히 O(n)이지만, 실제 연산은 더 적습니다. 투 패스는 항상 2n번 순회하지만, 원패스는 답을 찾으면 중단하므로 평균적으로 n/2번에서 n번 사이입니다.
공간복잡도도 O(n)이지만, 답을 일찍 찾으면 모든 원소를 저장하지 않으므로 실제로는 더 적게 씁니다. 예를 들어 답이 배열 앞쪽에 있으면 뒤쪽 원소들은 해시맵에 추가되지 않습니다.
여러분이 이 패턴을 마스터하면 "스트리밍 처리" 사고방식을 익히게 됩니다. 실무에서는 대용량 로그 파일을 분석하거나, 실시간 데이터 스트림을 처리할 때 "모든 데이터를 메모리에 로드하지 않고 보는 즉시 처리"하는 것이 중요합니다.
원패스 기법은 이런 상황에서 필수적인 패턴입니다. 또한 코딩 인터뷰에서 "최적화 능력"을 보여주는 가장 쉬운 방법이기도 합니다.
실전 팁
💡 원패스에서는 보완수를 먼저 확인하고 현재 값을 나중에 저장하는 순서가 핵심입니다. 순서를 바꾸면 같은 인덱스 중복 문제가 발생합니다.
💡 return [hash_map[complement], i]에서 순서를 주의하세요. complement의 인덱스가 항상 현재 인덱스보다 작으므로(먼저 봤으므로) 자동으로 오름차순 정렬됩니다.
💡 코딩 인터뷰에서는 "먼저 투 패스를 설명하고, 그 다음 원패스로 개선할 수 있다"고 말하면 사고 과정을 잘 보여줄 수 있습니다.
💡 원패스는 "답이 존재한다"는 가정이 있을 때 더 효율적입니다. 답이 없을 수도 있다면 전체를 순회해야 하므로 투 패스와 차이가 작아집니다.
💡 디버깅할 때 각 단계에서 해시맵의 상태를 프린트해보세요. 어떻게 점진적으로 구축되는지 시각화하면 이해가 쉽습니다.
6. 공간복잡도 트레이드오프
시작하며
여러분이 해시맵 솔루션을 구현했을 때, 시니어 개발자가 이렇게 물을 수 있습니다: "좋은데, 메모리를 너무 많이 쓰지 않나요?" 맞습니다. 해시맵 방식은 O(n) 공간을 사용합니다.
배열이 100만 개라면 해시맵도 최대 100만 개 항목을 저장해야 합니다. 모바일 앱이나 임베디드 시스템처럼 메모리가 제한적인 환경에서는 이것이 문제가 될 수 있습니다.
이것이 바로 "시간-공간 트레이드오프(time-space tradeoff)"라는 컴퓨터 과학의 핵심 개념입니다. 시간을 줄이려면 공간을 더 쓰고, 공간을 줄이려면 시간을 더 써야 합니다.
완벽한 알고리즘은 없으며, 상황에 따라 적절한 선택을 해야 합니다. 예를 들어 사용자가 기다리는 웹 API라면 시간을 최우선으로 하지만, 밤에 돌아가는 배치 작업이라면 메모리를 절약할 수도 있습니다.
실무 예시를 들면, 한 IoT 스타트업에서 센서 데이터를 분석하는 펌웨어를 개발했습니다. 처음에는 해시맵을 썼는데, 디바이스의 RAM이 512KB밖에 안 되어 메모리 부족 에러가 발생했습니다.
결국 공간복잡도 O(1)인 투 포인터 알고리즘으로 바꿔야 했습니다. 시간은 조금 더 걸리지만(O(n log n) 정렬 필요) 메모리 문제가 해결되었습니다.
이번 카드에서는 투 섬 문제의 다양한 해법들을 공간복잡도 관점에서 비교하고, 언제 어떤 방법을 선택해야 하는지 배웁니다.
개요
간단히 말해서, 공간복잡도 트레이드오프는 알고리즘의 시간 효율성과 메모리 사용량 사이의 균형을 의미합니다. 투 섬 문제에서는 브루트 포스(O(n²) 시간, O(1) 공간)와 해시맵(O(n) 시간, O(n) 공간) 사이에서 선택해야 합니다.
왜 이것이 실무에서 중요한지 설명하면, 모든 시스템에는 제약이 있기 때문입니다. 클라우드 서버라면 메모리를 충분히 확보할 수 있지만 비용이 발생하고, 모바일 앱은 배터리와 메모리가 제한적이며, 브라우저는 탭당 메모리 한계가 있고, 임베디드 시스템은 몇 KB의 RAM만 있을 수도 있습니다.
각 환경에 맞는 알고리즘을 선택하는 것이 시니어 개발자의 역량입니다. 전통적인 "빠르면 장땡" 사고방식과 비교하면, 현대 소프트웨어 엔지니어링은 "충분히 빠르면서 리소스를 효율적으로 쓰는" 것을 목표로 합니다.
구글의 사이트 신뢰성 엔지니어링(SRE)에서는 "99.9% 가용성이면 충분한데 99.99%를 위해 비용을 10배 쓸 필요는 없다"고 합니다. 마찬가지로 0.1초면 충분한데 0.01초를 위해 메모리를 10배 쓸 필요는 없습니다.
공간복잡도 트레이드오프의 핵심 특징은 다음과 같습니다: 1) 항상 양쪽을 고려해야 하며 한쪽만 최적화하면 안 됨, 2) 문제의 크기(n)가 작으면 차이가 미미하지만 크면 극적으로 달라짐, 3) 캐싱, 메모이제이션, 동적 프로그래밍 등 많은 최적화 기법이 "공간을 써서 시간을 절약"하는 패턴임, 4) 프로파일링 도구로 실제 병목을 측정한 후 결정해야 함. 투 섬 문제에서는 대부분의 경우 해시맵이 정답입니다.
현대 시스템에서 메모리는 상대적으로 충분하고 사용자는 빠른 응답을 원하기 때문입니다. 하지만 메모리가 정말 제한적이거나, 배열이 이미 정렬되어 있다면(정렬 비용이 없다면) 투 포인터 같은 O(1) 공간 알고리즘을 고려할 수 있습니다.
코드 예제
def space_complexity_comparison():
"""다양한 해법의 공간복잡도 비교"""
# 1. 브루트 포스: O(1) 공간
def brute_force_space():
# 변수 몇 개만 사용 (i, j, n 등)
# 입력 배열 외 추가 메모리 거의 없음
return "O(1) - 상수 공간"
# 2. 해시맵: O(n) 공간
def hash_map_space():
hash_map = {} # 최악의 경우 n개 항목 저장
return "O(n) - 선형 공간"
# 3. 투 포인터: O(1) 공간 (정렬된 배열 전제)
def two_pointer_space():
# 정렬이 필요하다면 O(log n) 공간 (정렬 스택)
# 정렬이 in-place라면 O(1)
return "O(1) or O(log n) - 정렬 방식에 따라"
# 메모리 사용량 예시 (n=1,000,000)
n = 1_000_000
brute_force_memory = 100 # bytes (변수 몇 개)
hash_map_memory = n * 20 # bytes (각 항목당 약 20바이트)
print(f"n={n}일 때 추가 메모리:")
print(f"브루트 포스: {brute_force_memory} bytes")
print(f"해시맵: {hash_map_memory / 1024 / 1024:.1f} MB")
space_complexity_comparison()
설명
이것이 하는 일: 공간복잡도 분석은 알고리즘이 실행되면서 입력 크기에 비례하여 얼마나 많은 추가 메모리를 사용하는지 측정합니다. O(1)은 상수 메모리(고정된 양), O(n)은 선형 메모리(입력 크기에 비례), O(n²)은 제곱 메모리를 의미합니다.
첫 번째로, 브루트 포스의 공간복잡도를 봅시다. 이중 루프에서 사용하는 변수는 i, j, n 정도로, 입력 크기와 무관하게 고정된 양의 메모리만 씁니다.
이를 O(1) 공간복잡도라고 합니다. 배열이 100개든 100만 개든 추가 메모리는 동일합니다.
단, 입력 배열 자체는 공간복잡도 계산에 포함하지 않습니다(이미 주어진 것이므로). 두 번째로, 해시맵의 공간복잡도를 분석하면, 최악의 경우(답이 마지막이거나 없는 경우) 배열의 모든 원소를 해시맵에 저장합니다.
따라서 O(n) 공간이 필요합니다. 파이썬 딕셔너리는 각 항목당 약 10-20바이트를 사용하므로, n=100만이면 약 10-20MB의 추가 메모리가 필요합니다.
서버나 데스크톱에서는 문제없지만, 메모리가 제한된 환경에서는 부담될 수 있습니다. 세 번째로, 실무에서 결정하는 방법을 봅시다.
먼저 요구사항을 확인합니다: 1) 응답 시간 제약이 있나? (웹 API는 보통 100-200ms 이내), 2) 메모리 제약이 있나?
(모바일은 MB 단위, 서버는 GB 단위), 3) 데이터 크기는? (n < 1,000이면 브루트 포스도 충분).
그 다음 프로파일링 도구로 실제 측정합니다. 파이썬에서는 memory_profiler, time.perf_counter() 등을 사용합니다.
네 번째로, 실전 의사결정 예시를 봅시다. 상황 1: "모바일 앱에서 사용자의 최근 거래 100개 분석" → n=100으로 작으므로 브루트 포스도 충분, 메모리 절약이 중요하므로 O(1) 선택.
상황 2: "전자상거래 사이트에서 쿠폰 조합 찾기, 쿠폰 1만 개" → n=10,000으로 크고, 사용자가 실시간 대기하므로 시간이 중요, 서버 메모리는 충분하므로 해시맵 O(n) 선택. 상황 3: "임베디드 센서, RAM 512KB, 데이터 1만 개" → 메모리가 극도로 제한적이므로 O(1) 공간 필수, 시간이 조금 걸려도 감수.
마지막으로, 트레이드오프를 시각화하면 이렇습니다. X축은 시간복잡도, Y축은 공간복잡도라면, 브루트 포스는 오른쪽 아래(느리지만 적은 메모리), 해시맵은 왼쪽 위(빠르지만 많은 메모리)에 위치합니다.
이상적인 알고리즘은 왼쪽 아래(빠르고 적은 메모리)이지만, 투 섬 문제에서는 그런 알고리즘이 없습니다. 따라서 프로젝트의 제약에 맞게 선택해야 합니다.
"은탄환(silver bullet)"은 없으며, 엔지니어링은 항상 트레이드오프입니다.
실전 팁
💡 코딩 인터뷰에서는 양쪽 해법을 모두 설명하고 "이 상황에서는 해시맵이 낫지만, 메모리가 제한적이라면 다른 방법을 고려할 수 있습니다"라고 말하면 좋습니다.
💡 "조기 최적화는 만악의 근원"이라는 말을 기억하세요. 먼저 작동하는 코드(해시맵)를 만들고, 프로파일링으로 병목을 찾은 후 필요하면 최적화하세요.
💡 파이썬에서 sys.getsizeof()로 객체의 실제 메모리 사용량을 측정할 수 있습니다. 큰 데이터로 테스트해보면 공간복잡도를 체감할 수 있습니다.
💡 클라우드 환경에서는 "메모리를 더 쓰는 대신 인스턴스 수를 줄이는" 전략도 가능합니다. 더 큰 인스턴스 1개가 작은 인스턴스 여러 개보다 저렴할 수 있습니다.
💡 캐싱, 메모이제이션, 동적 프로그래밍 모두 "공간을 써서 시간을 절약"하는 패턴입니다. 이 트레이드오프는 알고리즘 전반에 걸친 핵심 개념입니다.
7. 투 포인터 기법과의 비교
시작하며
여러분이 해시맵 솔루션을 마스터했다면, "다른 방법은 없을까?"라고 궁금할 수 있습니다. 실제로 투 섬 문제에는 또 다른 유명한 접근법이 있습니다: 투 포인터(Two Pointers) 기법입니다.
이 방법은 배열을 먼저 정렬한 후, 양 끝에서 포인터 두 개를 시작해 중앙으로 이동하면서 답을 찾습니다. 구체적으로 설명하면, 정렬된 배열 [2, 7, 11, 15]에서 target=9일 때, 왼쪽 포인터는 2(작은 값), 오른쪽 포인터는 15(큰 값)를 가리킵니다.
2+15=17이 target보다 크므로 오른쪽 포인터를 왼쪽으로 이동(15→11). 2+11=13이 여전히 크므로 또 이동(11→7).
2+7=9로 target과 일치하므로 답을 찾았습니다. 실무에서 투 포인터는 특정 상황에서 매우 강력합니다.
예를 들어 "정렬된 배열"을 다루거나, 메모리가 극도로 제한적인 환경에서는 해시맵보다 나을 수 있습니다. 하지만 일반적인 투 섬 문제(인덱스 반환)에서는 정렬 때문에 원래 인덱스가 섞여 해시맵만큼 직관적이지 않습니다.
이번 카드에서는 투 포인터와 해시맵을 비교하며, 각각 언제 사용해야 하는지 배웁니다. 이는 "문제 변형에 따라 최적 알고리즘이 달라진다"는 중요한 교훈을 줍니다.
개요
간단히 말해서, 투 포인터 기법은 정렬된 배열에서 양 끝에 포인터를 놓고, 두 포인터가 가리키는 값의 합에 따라 포인터를 이동시켜 답을 찾는 O(n) 알고리즘입니다. 시간복잡도는 정렬 포함 시 O(n log n), 공간복잡도는 O(1)입니다.
왜 이것이 중요한지 실무 관점에서 보면, 같은 문제도 입력 조건에 따라 다른 알고리즘이 최적일 수 있기 때문입니다. 예를 들어 "Two Sum II"라는 변형 문제는 배열이 이미 정렬되어 있다고 가정하므로, 투 포인터가 해시맵보다 공간 효율적입니다.
또한 "Three Sum", "Four Sum" 같은 확장 문제에서는 투 포인터가 더 자연스럽게 일반화됩니다. 해시맵과 비교하면, 해시맵은 정렬 없이 O(n) 시간, O(n) 공간으로 해결하지만, 투 포인터는 정렬 O(n log n) 후 O(n) 탐색으로 O(n log n) 시간, O(1) 공간을 사용합니다.
시간은 약간 느리지만 공간은 훨씬 절약됩니다. 또한 투 포인터는 "모든 쌍 찾기"나 "중복 제거" 같은 변형에서 더 유리합니다.
투 포인터의 핵심 특징은 다음과 같습니다: 1) 정렬된 배열이 전제 조건, 2) O(n log n) 시간(정렬 포함), O(n) 탐색만으로는 O(n), 3) O(1) 공간으로 메모리 효율적, 4) 원래 인덱스를 잃으므로 인덱스 반환 문제에는 추가 작업 필요. 투 섬 문제의 원래 버전은 "인덱스 반환"이므로, 투 포인터를 쓰려면 (값, 원래 인덱스) 쌍을 저장해야 해서 복잡해집니다.
언제 각각을 선택해야 하는지 정리하면: 1) 일반적인 투 섬(인덱스 반환) → 해시맵, 2) 정렬된 배열의 투 섬 → 투 포인터, 3) 값만 반환(인덱스 불필요) → 투 포인터, 4) Three Sum, Four Sum 확장 → 투 포인터, 5) 메모리 극도로 제한 → 투 포인터. 대부분은 해시맵이 정답이지만, 변형 문제에서는 투 포인터가 빛을 발합니다.
코드 예제
def two_sum_two_pointers(nums, target):
"""투 포인터: 정렬된 배열 전제, O(n) 시간, O(1) 공간"""
# 주의: 원래 인덱스를 잃으므로 (값, 인덱스) 쌍으로 저장
nums_with_index = [(num, i) for i, num in enumerate(nums)]
nums_with_index.sort() # 값 기준으로 정렬 O(n log n)
left, right = 0, len(nums) - 1 # 양 끝 포인터
while left < right:
current_sum = nums_with_index[left][0] + nums_with_index[right][0]
if current_sum == target:
# 답 찾음: 원래 인덱스 반환
return sorted([nums_with_index[left][1], nums_with_index[right][1]])
elif current_sum < target:
left += 1 # 합이 작으면 왼쪽 포인터 증가 (더 큰 값으로)
else:
right -= 1 # 합이 크면 오른쪽 포인터 감소 (더 작은 값으로)
return None
# 테스트
result = two_sum_two_pointers([2, 7, 11, 15], 9)
print(result) # 출력: [0, 1]
설명
이것이 하는 일: 투 포인터 알고리즘은 배열을 정렬한 후, 가장 작은 값(왼쪽)과 가장 큰 값(오른쪽)을 가리키는 두 포인터를 설정하고, 두 값의 합을 target과 비교하며 포인터를 조정해 답을 찾습니다. 정렬된 배열의 특성(단조성)을 활용하는 그리디 알고리즘입니다.
첫 번째 단계로, 배열을 정렬합니다. 하지만 원래 문제는 인덱스를 반환해야 하므로, 정렬하면 원래 인덱스를 잃습니다.
따라서 nums_with_index = [(num, i) for i, num in enumerate(nums)]로 (값, 원래 인덱스) 쌍을 만들고, 값 기준으로 정렬합니다. 예를 들어 [2, 7, 11, 15]는 [(2, 0), (7, 1), (11, 2), (15, 3)]이 됩니다.
정렬 시간은 O(n log n)입니다. 두 번째 단계로, 투 포인터를 초기화합니다.
left=0은 가장 작은 값 (2, 0)을, right=3은 가장 큰 값 (15, 3)을 가리킵니다. 이제 while left < right 루프를 돌면서 현재 합 current_sum을 계산합니다.
첫 번째 반복에서 2+15=17인데 target=9보다 크므로, 합을 줄여야 합니다. 오른쪽 포인터를 왼쪽으로 이동(right=2)하여 더 작은 값 11을 선택합니다.
세 번째 단계로, 포인터 이동 로직을 이해합시다. current_sum < target이면 합을 늘려야 하므로 left를 증가시킵니다(더 큰 값으로).
current_sum > target이면 합을 줄여야 하므로 right를 감소시킵니다(더 작은 값으로). current_sum == target이면 답을 찾은 것입니다.
이 로직이 작동하는 이유는 배열이 정렬되어 있어, 왼쪽으로 가면 값이 커지고 오른쪽으로 가면 값이 작아지기 때문입니다. 두 번째 반복에서 2+11=13이 여전히 크므로 right=1로 이동, 2+7=9로 target과 일치하여 원래 인덱스 [0, 1]을 반환합니다.
시간복잡도는 정렬 O(n log n) + 투 포인터 순회 O(n) = O(n log n)입니다. 해시맵의 O(n)보다 느립니다.
하지만 공간복잡도는 O(1)입니다(nums_with_index 배열은 입력의 변형이므로 O(n)으로 볼 수도 있지만, 정렬을 in-place로 하면 O(1)). 해시맵의 O(n) 공간보다 효율적입니다.
투 포인터가 유리한 경우를 봅시다. 1) 배열이 이미 정렬되어 있다면 정렬 비용이 없으므로 O(n) 시간, O(1) 공간으로 해시맵보다 낫습니다.
-
"Two Sum II" 같은 변형은 정렬된 배열이 주어지므로 투 포인터가 최적입니다. 3) "Three Sum"에서는 고정값 하나를 선택하고 나머지 두 개를 투 포인터로 찾는 패턴이 자연스럽습니다.
-
"모든 고유 쌍 찾기"처럼 중복을 피해야 하면 정렬 후 투 포인터가 더 쉽습니다. 여러분이 실무에서 판단할 때는 이렇게 하세요: 1) 문제가 인덱스를 요구하나?
→ 해시맵, 2) 배열이 정렬되어 있나? → 투 포인터, 3) 메모리가 극도로 제한적인가?
→ 투 포인터, 4) Three Sum 같은 확장인가? → 투 포인터.
대부분의 일반적인 투 섬은 해시맵이지만, 변형 문제에서는 투 포인터를 고려하세요.
실전 팁
💡 코딩 인터뷰에서 "배열이 정렬되어 있다면 투 포인터를 쓸 수 있습니다"라고 추가 설명하면 다양한 접근법을 알고 있다는 인상을 줍니다.
💡 투 포인터의 포인터 이동 로직(합이 작으면 left++, 크면 right--)을 확실히 이해하세요. 이는 정렬된 배열의 단조성을 이용한 그리디 알고리즘입니다.
💡 Three Sum 문제를 연습하면 투 포인터 패턴이 어떻게 확장되는지 체감할 수 있습니다. Three Sum은 거의 항상 투 포인터로 풉니다.
💡 nums_with_index처럼 (값, 인덱스) 쌍을 저장하는 패턴은 정렬 후 원래 정보를 유지하는 표준 기법입니다. 다른 문제에서도 자주 씁니다.
💡 LeetCode의 "Two Sum II - Input Array Is Sorted"를 풀어보세요. 정렬이 이미 되어있어 투 포인터가 순수 O(n) 시간, O(1) 공간으로 작동합니다.
8. 중복 처리와 엣지 케이스
시작하며
여러분이 해시맵 솔루션을 구현하고 기본 테스트를 통과했다면, "진짜 끝났을까?"라고 자문해봐야 합니다. 실무에서는 "행복한 경로(happy path)"만 작동해서는 안 됩니다.
엣지 케이스(edge case), 즉 특수한 상황들을 모두 처리해야 견고한 코드가 됩니다. 예를 들어 배열에 중복된 값이 있다면?
음수가 있다면? 배열이 비어있다면?
답이 여러 개라면? 구체적인 예를 들어보겠습니다.
nums = [3, 3]이고 target = 6인 경우를 생각해보세요. 같은 값이 두 개 있으므로 답은 [0, 1]입니다.
하지만 해시맵에 {3: 0}을 저장한 후 다시 3을 보면, "3을 이미 봤구나"라고 생각하지만 같은 인덱스 0을 두 번 쓰면 안 됩니다. 원패스 해시맵은 이를 자동으로 처리하지만, 투 패스는 주의가 필요합니다.
실무 사례를 보면, 한 결제 시스템에서 "두 거래의 합이 예산에 맞는지" 확인하는 기능이 있었습니다. 초기 구현은 양수만 가정했는데, 나중에 환불(음수 거래)이 추가되면서 버그가 발생했습니다.
target이 0일 때 양수와 음수 거래를 찾지 못하는 문제였습니다. 엣지 케이스를 고려하지 않아 발생한 실제 장애입니다.
이번 카드에서는 투 섬 문제의 다양한 엣지 케이스를 살펴보고, 각각을 어떻게 처리하는지 배웁니다. 이는 "단순히 작동하는 코드"에서 "프로덕션 레벨 코드"로 나아가는 핵심 과정입니다.
개요
간단히 말해서, 엣지 케이스는 일반적인 입력과 다른 특수한 상황으로, 예상치 못한 버그를 일으킬 수 있습니다. 투 섬 문제의 주요 엣지 케이스는: 1) 중복 값, 2) 음수와 0, 3) 빈 배열이나 원소 1개, 4) 답이 없거나 여러 개인 경우, 5) 매우 큰 수나 오버플로우입니다.
왜 이것이 실무에서 중요한지 설명하면, 소프트웨어 버그의 대부분은 엣지 케이스에서 발생하기 때문입니다. 사용자는 항상 "정상적인" 입력만 주지 않습니다.
빈 값을 입력하거나, 음수를 넣거나, 중복된 데이터를 보내거나, 매우 큰 숫자를 시도합니다. 특히 금융, 의료, 보안 같은 critical한 시스템에서는 엣지 케이스 하나가 큰 사고로 이어질 수 있습니다.
일반적인 테스트와 비교하면, 일반 테스트는 "정상 입력 → 정상 출력"을 확인하지만, 엣지 케이스 테스트는 "비정상 입력 → 적절한 처리"를 확인합니다. 예를 들어 "배열이 null이면 어떻게 하지?", "정수 오버플로우는?", "무한루프는 없을까?" 같은 질문을 던집니다.
이를 방어적 프로그래밍(defensive programming)이라고 합니다. 엣지 케이스 처리의 핵심 특징은 다음과 같습니다: 1) 입력 검증(validation)을 먼저 수행, 2) 경계 조건(boundary condition)을 명시적으로 처리, 3) 예외 상황에 대한 명확한 동작 정의, 4) 단위 테스트에 엣지 케이스 포함.
코딩 인터뷰에서는 "이 코드는 중복 값도 처리하고, 음수도 고려했으며, 빈 배열은 None을 반환합니다"라고 설명하면 꼼꼼한 개발자라는 인상을 줍니다. 실무에서 엣지 케이스를 찾는 방법은: 1) 문제의 제약 조건을 꼼꼼히 읽기(LeetCode는 제약 조건을 명시함), 2) "만약 ~라면?"을 반복적으로 질문하기, 3) 경계값 테스트(boundary value testing) - 최소값, 최대값, 0, 빈 값 등, 4) 동료 코드 리뷰에서 엣지 케이스 찾기, 5) 프로덕션 로그에서 실제 발생한 예외 분석하기.
경험이 쌓이면 자동으로 엣지 케이스를 떠올리게 됩니다.
코드 예제
def two_sum_robust(nums, target):
"""엣지 케이스를 처리하는 견고한 투 섬 구현"""
# 엣지 케이스 1: 입력 검증
if nums is None or len(nums) < 2:
return None # 최소 2개 원소 필요
hash_map = {}
for i, num in enumerate(nums):
complement = target - num
# 엣지 케이스 2: 중복 값 처리 (원패스는 자동 처리)
if complement in hash_map:
return [hash_map[complement], i]
# 엣지 케이스 3: 같은 값이 여러 개일 때 (나중 인덱스로 업데이트)
hash_map[num] = i
# 엣지 케이스 4: 답이 없는 경우
return None
# 테스트 케이스들
print(two_sum_robust([3, 3], 6)) # 중복 값: [0, 1]
print(two_sum_robust([-1, -2, -3], -5)) # 음수: [1, 2]
print(two_sum_robust([0, 4, 3, 0], 0)) # 0 포함: [0, 3]
print(two_sum_robust([1], 1)) # 원소 1개: None
print(two_sum_robust([], 9)) # 빈 배열: None
print(two_sum_robust([1, 2], 10)) # 답 없음: None
설명
이것이 하는 일: 견고한 구현은 정상 입력뿐만 아니라 예외적인 상황도 적절히 처리합니다. 입력 검증, 경계 조건 확인, 예외 처리를 통해 어떤 입력에도 크래시 없이 합리적인 결과를 반환합니다.
첫 번째 엣지 케이스인 "입력 검증"을 봅시다. if nums is None or len(nums) < 2는 배열이 null이거나 원소가 2개 미만인 경우를 걸러냅니다.
투 섬은 최소 2개 원소가 필요하므로, 이 조건에 걸리면 None을 반환합니다. 프로덕션 코드에서는 ValueError를 raise하거나 로그를 남길 수도 있습니다.
이를 "fail-fast" 원칙이라고 하며, 잘못된 입력을 빨리 감지해 나중에 더 큰 문제가 생기는 것을 방지합니다. 두 번째 엣지 케이스인 "중복 값"을 봅시다.
nums = [3, 3], target = 6인 경우, 첫 번째 3을 보면 complement=3인데 아직 해시맵이 비어있으므로 hash_map = {3: 0}이 됩니다. 두 번째 3을 보면 complement=3이 해시맵에 있으므로 [0, 1]을 반환합니다.
원패스 방식은 "현재 값을 저장하기 전에 보완수를 확인"하므로 중복 값을 자연스럽게 처리합니다. 만약 투 패스 방식이었다면 hash_map[complement] != i 조건이 필요합니다.
세 번째 엣지 케이스인 "음수와 0"을 봅시다. 투 섬 알고리즘은 값의 부호와 무관하게 작동합니다.
nums = [-1, -2, -3], target = -5라면, -2 + -3 = -5이므로 [1, 2]를 반환합니다. nums = [0, 4, 3, 0], target = 0이라면 0 + 0 = 0이므로 [0, 3]을 반환합니다.
해시맵은 정수 키를 모두 처리할 수 있으므로 특별한 처리가 필요 없습니다. 하지만 실무에서는 "음수가 들어올 수 있는가?"를 비즈니스 로직에서 확인해야 합니다.
네 번째 엣지 케이스인 "답이 없는 경우"를 봅시다. nums = [1, 2], target = 10이면 어떤 두 수를 더해도 10이 안 됩니다.
루프가 끝까지 돌고 return None에 도달합니다. 문제 조건에서 "정확히 하나의 해답이 존재한다"고 명시하면 이 경우는 발생하지 않지만, 일반적인 함수로 만든다면 None 반환이 합리적입니다.
다른 선택지로는 빈 리스트 [], 예외 raise ValueError("No solution"), 또는 특수값 [-1, -1]을 반환할 수 있습니다. 다섯 번째 엣지 케이스인 "오버플로우"를 봅시다.
파이썬은 임의 정밀도 정수를 지원해 오버플로우가 없지만, Java나 C++에서는 int 범위를 넘으면 오버플로우가 발생합니다. 예를 들어 nums = [2000000000, 2000000000], target = 4000000000이면 계산 과정에서 오버플로우할 수 있습니다.
이럴 때는 long 타입을 쓰거나, 계산 전에 범위를 확인해야 합니다. 여러분이 코딩 인터뷰에서 이렇게 말하면 좋습니다: "기본 구현은 완료했고, 엣지 케이스를 확인하겠습니다.
빈 배열, 원소 1개, 중복 값, 음수, 답 없음 등을 고려했습니다. 문제 조건에서 '항상 답이 존재한다'고 했으므로 답 없음 케이스는 생략할 수 있습니다." 이렇게 체계적으로 접근하면 면접관이 "이 사람은 꼼꼼하고 실무에 강하겠다"고 평가합니다.
실전 팁
💡 코딩 인터뷰에서 솔루션을 제시한 후 "엣지 케이스를 확인하겠습니다"라고 말하며 체계적으로 점검하세요. 이는 시니어 개발자의 습관입니다.
💡 단위 테스트를 작성할 때 엣지 케이스를 반드시 포함하세요. pytest나 unittest에서 @pytest.mark.parametrize로 여러 케이스를 한 번에 테스트할 수 있습니다.
💡 LeetCode 문제의 "Constraints" 섹션을 꼼꼼히 읽으세요. 예를 들어 "2 <= nums.length <= 10^4"는 빈 배열 케이스가 없다는 뜻입니다.
💡 실무에서는 입력 검증을 함수 맨 앞에 배치하는 "guard clause" 패턴을 쓰세요. if invalid: return early 형태로 메인 로직을 들여쓰기에서 해방시킵니다.
💡 "중복 값"과 "같은 인덱스 중복 사용"을 구분하세요. [3, 3]은 OK(다른 인덱스), [3]에서 3을 두 번 쓰는 것은 NO(같은 인덱스)입니다.