Ch.2 배열과 문자열
Two Pointer 기법 — 양 끝에서 좁혀오기
O(n²)을 O(n)으로 줄이는 마법이 있다면?
두 사람이 복도 양쪽 끝에서 동시에 걸어오며 방을 확인합니다. 혼자 처음부터 끝까지 두 번 돌 필요가 없죠.
어떤 문제에 Two Pointer를 쓸 수 있을까? 모든 문제에 적용 가능할까?
정렬된 배열 또는 양 끝 비교 문제에서 Two Pointer는 강력한 무기입니다.
핵심 개념
Two Pointer
두 개의 포인터를 이동시키며 탐색 범위를 줄이는 기법
시간복잡도 최적화
O(n²) → O(n)으로 개선하는 핵심 패턴
핵심 내용
복도 양 끝에서 두 사람이 걸어옵니다. 만날 때까지 각자 방을 하나씩 확인하죠
두 포인터가 만나면 탐색 종료! 전체 배열을 한 번만 순회합니다
정렬된 배열에서 합이 target인 두 수를 찾는 문제를 풀어봅시다
def two_sum_sorted(arr, target):
left, right = 0, len(arr) - 1
while left < right:
current_sum = arr[left] + arr[right]
if current_sum == target:
return [left, right]
elif current_sum < target:
left += 1 # 합이 작으면 왼쪽 포인터 증가
else:
right -= 1 # 합이 크면 오른쪽 포인터 감소
return [] # 해 없음
# 예시
arr = [1, 3, 5, 7, 11, 13]
print(two_sum_sorted(arr, 12)) # [1, 4] → 3 + 11 = 14? 아니, arr[1]+arr[4]=3+11=14면접 단골 문제! Container With Most Water를 풀어봅시다
문제: 높이 배열이 주어질 때, 두 막대로 만들 수 있는 최대 물의 양은? 넓이 = min(height[l], height[r]) × (r - l) 핵심: 높이가 낮은 쪽의 포인터를 이동시킨다!
def max_area(height):
left, right = 0, len(height) - 1
max_water = 0
while left < right:
width = right - left
h = min(height[left], height[right])
max_water = max(max_water, width * h)
# 핵심: 낮은 쪽을 이동
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_water
print(max_area([1,8,6,2,5,4,8,3,7])) # 49면접 포인트: '왜 낮은 쪽을 이동하나요?' — 높은 쪽을 이동하면 너비만 줄고 높이는 개선될 수 없습니다
Two Pointer 기법의 시간복잡도는?
Container With Most Water에서 높이가 낮은 쪽의 포인터를 이동하는 이유는?
Two Pointer는 정렬되지 않은 배열에서도 항상 사용할 수 있다
Two Pointer 마스터
핵심 용어
Left Pointer
배열의 왼쪽 끝에서 시작하여 오른쪽으로 이동
Right Pointer
배열의 오른쪽 끝에서 시작하여 왼쪽으로 이동
핵심 원리
매 단계 한 쪽을 이동 → 총 이동 O(n)
정리 노트
Two Pointer — O(n²)을 O(n)으로
핵심 개념
- 원리
- 양 끝 두 포인터를 조건에 따라 이동시켜 탐색 범위를 줄임
- 시간복잡도
- O(n) — 각 포인터가 최대 n번 이동
- 적용 조건
- 정렬 배열 또는 양 끝 비교 문제
대표 문제
- Two Sum (정렬)
- 합이 작으면 left++, 크면 right--
- Container With Most Water
- 낮은 쪽 포인터를 이동
면접 키워드: 'Two pointer로 O(n²) → O(n) 최적화'
시각 자료
핵심 정리
- 1Two Pointer = 양 끝에서 좁혀오기 → O(n)
- 2정렬 배열 Two Sum: 합 비교로 포인터 이동
- 3Container With Most Water: 낮은 쪽 이동
- 4면접에서 O(n²) → O(n) 최적화 설명 필수
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작