두 수의 합과 다양한 변형
해시 맵과 투 포인터를 사용해 two-sum, three-sum, four-sum, 정렬 배열의 two-sum을 해결하고 시간·공간 비용을 비교합니다.
두 수의 합과 다양한 변형은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
두 수의 합: 대표적인 면접 문제
LeetCode 1 ‘두 수의 합’: 정렬되지 않은 배열과 목표값이 주어졌을 때, 합이 목표값이 되는 두 요소의 인덱스를 반환합니다. 완전 탐색 방식인 O(n²) 접근법은 모든 쌍을 확인합니다. 최적의 O(n) 접근법은 해시 맵을 사용합니다. 각 요소 x에 대해 target - x가 이미 맵에 있는지 확인합니다. 있다면 두 인덱스의 쌍을 반환하고, 없다면 x와 그 인덱스를 맵에 저장합니다.
두 수의 합은 면접에서 가장 먼저 출제되는 문제인 경우가 많습니다. 이 문제를 완전히 익혔다는 것은 더 어려운 문제로 나아갈 준비가 되었다는 신호입니다.
def twoSum(nums, target):
seen = {} # val -> index
for i, x in enumerate(nums):
complement = target - x
if complement in seen:
return [seen[complement], i]
seen[x] = i
return []
print(twoSum([2, 7, 11, 15], 9)) # [0, 1]
print(twoSum([3, 2, 4], 6)) # [1, 2]
print(twoSum([3, 3], 6)) # [0, 1]두 수의 합에서 해시 맵이 작동하는 이유
해시 맵에는 지금까지 확인한 모든 요소가 저장됩니다. 요소 x를 처리할 때 target - x가 맵에 있으면 두 요소가 유효한 쌍을 이룹니다. 중요한 점은 x를 저장하기 전에 보완값을 확인한다는 것입니다. 이렇게 하면 하나의 요소를 자기 자신과 짝짓는 상황을 방지할 수 있습니다. 예를 들어 x == target/2인 경우에도 x를 저장하기 전에 맵을 확인하므로, 같은 값이 두 개 있지 않다면 일치하지 않습니다.
# Trace two-sum on [2, 7, 11, 15], target=9
nums, target = [2, 7, 11, 15], 9
seen = {}
for i, x in enumerate(nums):
complement = target - x
print(f'i={i} x={x} complement={complement} seen={seen}')
if complement in seen:
print(f' Found: indices [{seen[complement]}, {i}]')
break
seen[x] = i정렬된 배열의 두 수의 합(두 포인터)
배열이 이미 정렬되어 있고 원래 인덱스가 아닌 값의 인덱스가 필요하다면 두 포인터 기법을 사용하세요. 양쪽 끝에서 시작하는 왼쪽 포인터와 오른쪽 포인터를 둡니다. 합이 목표값과 같으면 반환합니다. 합이 너무 작으면 왼쪽 포인터를 오른쪽으로 이동하고, 합이 너무 크면 오른쪽 포인터를 왼쪽으로 이동합니다. 시간 복잡도는 O(n), 공간 복잡도는 O(1)이며, 배열이 정렬되어 있고 메모리가 제한된 경우 해시 맵 방식보다 효율적입니다.
def twoSumSorted(numbers, target):
lo, hi = 0, len(numbers) - 1
while lo < hi:
s = numbers[lo] + numbers[hi]
if s == target:
return [lo + 1, hi + 1] # 1-indexed as per LeetCode 167
elif s < target:
lo += 1
else:
hi -= 1
return []
print(twoSumSorted([2, 7, 11, 15], 9)) # [1, 2]
print(twoSumSorted([2, 3, 4], 6)) # [1, 3]
print(twoSumSorted([-1, 0], -1)) # [1, 2]세 수의 합(LeetCode 15)
LeetCode 15 ‘세 수의 합’: 합이 0이 되는 모든 고유한 세 요소 조합을 찾습니다. 배열을 정렬하고, 한 번에 하나의 요소를 고정한 뒤 나머지 정렬된 부분 배열에 두 포인터 기법을 적용합니다. 중복된 값을 건너뛰어 중복 조합을 방지합니다. 시간 복잡도는 O(n²)입니다. 출력 자체에 O(n²)개의 조합이 포함될 수 있으므로 이 문제에 최적인 복잡도입니다.
def threeSum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: # skip duplicates
continue
lo, hi = i + 1, len(nums) - 1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if s == 0:
result.append([nums[i], nums[lo], nums[hi]])
while lo < hi and nums[lo] == nums[lo+1]: lo += 1
while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
lo += 1; hi -= 1
elif s < 0:
lo += 1
else:
hi -= 1
return result
print(threeSum([-1, 0, 1, 2, -1, -4])) # [[-1,-1,2],[-1,0,1]]
print(threeSum([0, 0, 0, 0])) # [[0,0,0]]네 수의 합(LeetCode 18)
LeetCode 18 ‘네 수의 합’: 합이 목표값이 되는 모든 고유한 네 요소 조합을 찾습니다. 세 수의 합을 확장해 두 개의 중첩 반복문으로 두 요소를 고정하고(중복 건너뛰기), 내부 부분 배열에 두 포인터 기법을 적용합니다. 시간 복잡도는 O(n³)입니다. 일반적인 k-합 문제에서는 k-2개의 요소를 재귀적으로 고정한 다음 두 포인터를 적용하므로 시간 복잡도는 O(n^(k-1))입니다.
def fourSum(nums, target):
nums.sort()
n, result = len(nums), []
for i in range(n - 3):
if i > 0 and nums[i] == nums[i-1]:
continue
for j in range(i+1, n-2):
if j > i+1 and nums[j] == nums[j-1]:
continue
lo, hi = j+1, n-1
while lo < hi:
s = nums[i]+nums[j]+nums[lo]+nums[hi]
if s == target:
result.append([nums[i],nums[j],nums[lo],nums[hi]])
while lo < hi and nums[lo] == nums[lo+1]: lo += 1
while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
lo += 1; hi -= 1
elif s < target: lo += 1
else: hi -= 1
return result
print(fourSum([1,0,-1,0,-2,2], 0))
# [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]목표값에 가장 가까운 두 수의 합
흔한 변형 문제로, 합이 목표값과 정확히 같지 않아도 목표값에 가장 가까운 쌍을 찾는 문제가 있습니다. 배열을 정렬하고 두 포인터를 사용하세요. 지금까지 확인한 가장 가까운 합을 추적하고, 목표값과의 절댓값 차이가 더 작은 쌍을 찾을 때마다 갱신합니다. 정렬 후에는 이 O(n log n) 방식으로 간단히 해결할 수 있습니다.
def twoSumClosest(nums, target):
nums.sort()
lo, hi = 0, len(nums) - 1
best = float('inf')
best_pair = None
while lo < hi:
s = nums[lo] + nums[hi]
if abs(s - target) < abs(best - target):
best = s
best_pair = (nums[lo], nums[hi])
if s < target:
lo += 1
elif s > target:
hi -= 1
else:
return best_pair # exact match
return best_pair
print(twoSumClosest([1, 3, 4, 7, 10], 15)) # (7, 10) => 17, closest to 15
print(twoSumClosest([2, 5, 8, 11], 10)) # (2, 8) => 10, exact!여러 쌍을 찾는 두 수의 합(모든 쌍)
합이 목표값이 되는 모든 쌍을 찾으려면 배열을 정렬하고 두 포인터를 사용해 모든 쌍을 수집합니다. 유효한 쌍을 찾은 뒤에는 계속 진행하기 전에 양쪽 끝에서 중복을 건너뜁니다. 정렬에 O(n log n), 탐색에 O(n)이 걸리므로 전체 시간 복잡도는 O(n log n)입니다. 해시 맵을 사용해 쌍을 수집하는 방법도 가능하지만 중복을 신중하게 처리해야 합니다.
def twoSumAllPairs(nums, target):
nums.sort()
lo, hi = 0, len(nums) - 1
pairs = []
while lo < hi:
s = nums[lo] + nums[hi]
if s == target:
pairs.append((nums[lo], nums[hi]))
while lo < hi and nums[lo] == nums[lo+1]: lo += 1
while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
lo += 1; hi -= 1
elif s < target:
lo += 1
else:
hi -= 1
return pairs
print(twoSumAllPairs([1,1,2,3,4,4,5], 5)) # [(1,4),(1,4)-deduped,(2,3)]
# After duplicate-skipping: [(1,4),(2,3)]합이 K보다 작은 쌍의 개수 세기
또 다른 변형 문제로 합이 k보다 작은 쌍의 개수를 세는 문제가 있습니다. 배열을 정렬하고 두 포인터를 사용하세요. nums[lo] + nums[hi] < k이면 (lo, lo+1), (lo, lo+2), ..., (lo, hi)의 모든 쌍이 유효합니다. 즉 hi - lo개의 쌍입니다. lo를 증가시키고, 그렇지 않으면 hi를 줄입니다. 전체 시간 복잡도는 정렬에 O(n log n), 개수 계산에 O(n)이므로 O(n log n)입니다.
def countPairsLessThan(nums, k):
nums.sort()
lo, hi = 0, len(nums) - 1
count = 0
while lo < hi:
if nums[lo] + nums[hi] < k:
count += hi - lo # all (lo, lo+1)...(lo, hi) are valid
lo += 1
else:
hi -= 1
return count
print(countPairsLessThan([1, 3, 7, 11, 12], 10)) # (1,3),(1,7),(3,7) => 3
print(countPairsLessThan([3, 5, 2, 3], 7)) # (2,3),(2,3) => 2... verify해시 맵을 사용하는 두 수의 합: 중복 처리
같은 값이 여러 번 나타날 수 있고 유효한 쌍의 존재 여부가 아니라 개수가 필요하다면 맵에 빈도수를 저장하세요. 두 요소가 같은 쌍의 경우 빈도가 f일 때 쌍의 개수는 f*(f-1)//2입니다. 두 요소의 값이 다르면 두 빈도수를 곱합니다. 이 방법으로 모든 유효한 쌍을 O(n)에 셀 수 있습니다.
from collections import Counter
def countTwoSumPairs(nums, target):
freq = Counter(nums)
count = 0
seen = set()
for x in freq:
y = target - x
if y in freq and (x, y) not in seen:
if x == y:
count += freq[x] * (freq[x] - 1) // 2
else:
count += freq[x] * freq[y]
seen.add((x, y))
seen.add((y, x))
return count
print(countTwoSumPairs([1,1,2,3,4,4,3], 4))
# Pairs summing to 4: (1,3)x2x2=4, (0+more)...두 수의 합 패턴 변형 알아보기
두 수의 합 패턴은 다양한 형태로 나타납니다. 문제에서 수의 관계(합, 곱, 차)를 만족하는 두 개 이상의 요소를 찾으라고 하면 이 패턴을 떠올리세요. 핵심 전략은 항상 같습니다. 하나의 요소를 고정한 다음 미리 계산한 자료구조(해시 맵 또는 정렬된 배열과 포인터)에서 그 보완값을 찾습니다. k-합으로 확장할 때는 중첩 반복문으로 k-2개의 요소를 고정하고 기본 사례를 적용합니다.
# Summary of approaches by scenario
scenarios = [
('Unsorted array, any indices, one pair', 'hash map O(n) time O(n) space'),
('Sorted array, any indices, one pair', 'two pointers O(n) time O(1) space'),
('All unique pairs summing to target', 'sort + two pointers O(n log n)'),
('Three numbers summing to zero (3-sum)', 'sort + fix + two pointers O(n^2)'),
('k numbers summing to target (k-sum)', 'sort + k-2 loops + two pointers O(n^(k-1))')
]
for scenario, approach in scenarios:
print(f'{scenario}\n => {approach}\n')두 수의 합 문제에서의 면접 소통
면접에서 두 수의 합 문제가 나오면 다음과 같이 사고 과정을 소리 내어 설명하세요. ‘합이 목표값이 되는 두 수가 필요합니다. 각 수 x에 대해 그 수와 더해 목표값이 되는 값이 존재하는지 확인해야 합니다. 해시 맵을 사용하면 이를 O(1)에 확인할 수 있으므로 전체 시간 복잡도는 O(n), 공간 복잡도는 O(n)입니다. 또는 배열이 정렬되어 있다면 O(1) 공간에서 두 포인터를 사용할 수 있습니다.’ 두 접근법을 모두 설명하고, 선택하기 전에 공간 제약이 있는지 질문하세요.
빠른 확인
이번 레슨에서 다룬 자료 구조 및 알고리즘 — 코딩 면접 준비 개념에 대한 이해도를 확인해 보세요.
레슨 요약
이번 레슨에서는 두 수의 합 문제에서 해시 맵으로 보수의 존재 여부를 O(1)에 확인하여 전체 O(n)을 달성하는 방법, 정렬된 배열에서 두 포인터로 O(1) 공간을 사용하는 방법, 그리고 정렬과 중첩 반복문을 사용해 세 수의 합과 네 수의 합을 두 수의 합 문제로 줄여 각각 O(n²)과 O(n³)에 실행하는 방법을 배웠습니다. 다음에는 빈도 계산 패턴과 기본값 사전 및 카운터를 사용한 그룹화를 살펴봅니다.
자주 묻는 질문
“두 수의 합과 다양한 변형” 강의는 무료인가요?
네 — “두 수의 합과 다양한 변형” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“두 수의 합과 다양한 변형”에서 뭘 배우나요?
해시 맵과 투 포인터를 사용해 two-sum, three-sum, four-sum, 정렬 배열의 two-sum을 해결하고 시간·공간 비용을 비교합니다. 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.
“두 수의 합과 다양한 변형” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 해시 함수 내부와 충돌 처리
- 두 수의 합과 다양한 변형
- 빈도 계산과 그룹화
- 가장 긴 연속 수열과 LRU 캐시