Ch.8 정렬과 탐색
면접실전 — Merge Intervals, Search Rotated, Find Min Rotated
FAANG 면접에서 실제로 나오는 문제들
정렬과 탐색을 조합하는 면접 문제 3개를 실전 수준으로 풀어봅니다.
개념은 알겠는데, 실제 문제에서 어떻게 적용하지?
패턴 인식 → 자료구조 선택 → 구현의 3단계로 체계적으로 접근합니다.
핵심 개념
Merge Intervals
겹치는 구간들을 합쳐 하나로 만드는 문제 (LeetCode #56)
핵심 내용
LeetCode #56 — Merge Intervals 면접 빈출도 최상위
문제: 겹치는 구간들을 합치세요. 입력: 1,3],[2,6],[8,10],[15,18 출력: 1,6],[8,10],[15,18 [1,3]과 [2,6]이 겹치므로 → [1,6]
핵심 아이디어: 시작점 기준 정렬 후 순차적으로 겹침 여부 확인
def merge_intervals(intervals):
intervals.sort(key=lambda x: x[0]) # 시작점 정렬
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]: # 겹침
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return merged
# 시간: O(n log n) — 정렬
# 공간: O(n) — 결과 배열정렬이 핵심! 정렬 없이는 모든 쌍을 비교해야 O(n²). 정렬하면 한 번 순회로 해결
1,3],[2,6],[8,10],[15,18을 단계별로 처리합니다
정렬 후 한 번 순회만으로 모든 겹침을 처리했습니다
LeetCode #33 — 회전 배열 탐색 섹션 6에서 배운 패턴의 실전 적용
문제: 회전된 정렬 배열에서 target을 O(log n)에 찾으세요. 입력: nums=[4,5,6,7,0,1,2], target=0 출력: 4
def search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return mid
if nums[lo] <= nums[mid]: # 왼쪽 정렬
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else: # 오른쪽 정렬
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1면접 팁: "mid 기준 정렬된 쪽을 먼저 찾고, target이 그 범위에 있는지 확인"이라고 설명하세요
LeetCode #153 — 회전 배열 최솟값 Binary Search의 응용
문제: 회전된 정렬 배열의 최솟값을 O(log n)에 찾으세요. 입력: [3, 4, 5, 1, 2] 출력: 1 회전 지점 바로 다음이 최솟값!
def find_min(nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] > nums[hi]: # 최솟값은 오른쪽에
lo = mid + 1
else: # 최솟값은 왼쪽(mid 포함)
hi = mid
return nums[lo]
# 핵심: nums[mid]와 nums[hi]를 비교
# mid > hi → 꺾인 지점이 오른쪽
# mid <= hi → 꺾인 지점이 왼쪽(또는 mid 자체)왜 `nums[lo]`가 아니라 `nums[hi]`와 비교할까? → lo 비교 시 회전 안 된 경우를 구분할 수 없음
면접에서 정렬/탐색 문제를 만났을 때의 체계적 접근법입니다
Step 1: 정렬이 필요한가? → sort 후 투포인터/이진탐색 Step 2: 이미 정렬되어 있는가? → Binary Search 패턴 선택 Step 3: 회전/변형이 있는가? → 정렬된 쪽 판별 후 범위 좁히기 Step 4: 복잡도 확인 — O(n log n) 이하인가?
정렬/탐색은 70% 이상의 코딩 면접에서 직간접적으로 사용됩니다
Merge Intervals에서 정렬의 기준은?
Find Minimum in Rotated Array에서 nums[mid]와 nums[lo]를 비교한다
면접 실전 문제 클리어!
정리 노트
면접실전 — 정렬/탐색 문제
핵심 문제
- Merge Intervals
- 시작점 정렬 → 순회하며 겹침 병합
- Search Rotated
- 정렬된 쪽 판별 → 범위 좁히기
- Find Min Rotated
- `nums[mid]` vs `nums[hi]` 비교
풀이 프레임워크
- Step 1
- 정렬 필요 여부 판단
- Step 2
- Binary Search 패턴 선택 (값/경계/조건)
이 3문제는 FAANG 면접에서 반복 출제됩니다. 패턴을 외우세요!
시각 자료
핵심 정리
- 1Merge Intervals — 정렬 후 한 번 순회
- 2Search Rotated — 정렬된 쪽 판별이 핵심
- 3Find Min Rotated — nums[hi]와 비교
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작