💡 왼쪽 원문을 읽으면서 오른쪽에 따라 써보세요. Tab 키로 힌트를 받을 수 있습니다.

원문 렌더가 준비되기 전까지 텍스트 가이드로 표시합니다.

1. 2025 코딩 인터뷰 현황

FAANG 출제 빈도와 트렌드

2025년 FAANG(Meta, Apple, Amazon, Netflix, Google) 코딩 인터뷰는 이전보다 **패턴 기반 문제 출제** 비율이 높아졌습니다. 단순 암기 문제보다는 기존 패턴을 변형하거나 조합하는 문제가 주를 이루고, 특히 Graph + DP 복합 문제, Sliding Window + Hash Map 조합 문제가 빈번하게 등장하고 있습니다.

2025년 기준 주요 출제 빈도를 살펴보면 다음과 같습니다.

| --------------------------- | ------ | ---- | ------ | ----- | --------- |

| Arrays/Hashing | 25% | 30% | 35% | 20% | 28% |

| Trees/Graphs | 22% | 18% | 15% | 25% | 20% |

| Dynamic Programming | 18% | 15% | 12% | 18% | 15% |

| Two Pointers/Sliding Window | 12% | 15% | 18% | 10% | 12% |

| Binary Search | 8% | 7% | 8% | 10% | 10% |

| 기타 (Stack, Heap, Trie 등) | 15% | 15% | 12% | 17% | 15% |

AI-Aware 코딩 라운드의 등장

2025년부터 일부 기업은 **AI 코파일럿 사용을 전제로 한 코딩 인터뷰**를 도입하기 시작했습니다. 단순 구현 능력보다는 **문제 분석, 최적 알고리즘 선택, 코드 리뷰 능력**을 평가하는 방향으로 변화하고 있습니다. 하지만 여전히 전통적인 whiteboard 코딩이 주류이며, 알고리즘 패턴 이해는 필수입니다.

NeetCode 150 vs Blind 75 vs Grind 75 비교

| ------------- | ------------------------------ | ------------------------------ | ------------------------------ |

| 문제 수 | 75 | 150 | 75 (커스텀 가능) |

| 패턴 커버리지 | 13개 | 15개 | 14개 |

| 최신 업데이트 | 2021 | 2024 | 2023 |

이 글에서는 NeetCode 150을 기반으로 **핵심 75문제를 선별**하여, 각 패턴별로 반드시 풀어야 할 문제를 정리합니다.

언어 선택: Python vs Java vs TypeScript

- **Python**: 코드가 간결하고 빠른 풀이 가능. FAANG 면접에서 가장 인기 있는 언어. 내장 라이브러리(heapq, collections, itertools)가 강력

- **Java**: 타입 안전성과 성능이 장점. Amazon, Google에서 선호. TreeMap, PriorityQueue 등 자료구조가 풍부

- **TypeScript**: 프론트엔드 직군 면접에서 유리. 하지만 알고리즘 문제에서는 Python 대비 장점이 적음

이 글의 코드 예시는 **Python**을 기본으로 합니다.

12주 학습 로드맵 개요

| 주차 | 패턴 | 일일 문제 수 |

| ------- | ------------------------------------ | ------------ |

| 1-2주 | Arrays/Hashing, Two Pointers | 2문제 |

| 3-4주 | Sliding Window, Stack, Binary Search | 2문제 |

| 5-6주 | Linked List, Trees | 2문제 |

| 7-8주 | Tries, Heap, Backtracking | 2문제 |

| 9-10주 | Graphs, 1D DP | 2-3문제 |

| 11-12주 | 2D DP, Greedy, Intervals, 종합 복습 | 2-3문제 |

2. Pattern 1 — Arrays and Hashing

핵심 아이디어

배열과 해시맵은 모든 알고리즘의 기초입니다. **해시맵을 활용한 O(1) 룩업**으로 brute force O(n^2)를 O(n)으로 줄이는 것이 핵심입니다. 빈도 카운팅, 중복 검사, 그루핑 문제에 필수적으로 사용됩니다.

시간/공간 복잡도

- 해시맵 삽입/조회: O(1) 평균, O(n) 최악

- 정렬 기반 접근: O(n log n)

- 공간: O(n) — 해시맵 저장

대표 문제

1. **Two Sum** (LeetCode 1) — Easy

2. **Contains Duplicate** (LeetCode 217) — Easy

3. **Valid Anagram** (LeetCode 242) — Easy

4. **Group Anagrams** (LeetCode 49) — Medium

5. **Top K Frequent Elements** (LeetCode 347) — Medium

Python 풀이 — Two Sum (LeetCode 1)

def twoSum(nums: list[int], target: int) -> list[int]:

해시맵: 값 -> 인덱스 매핑

seen = {}

for i, num in enumerate(nums):

complement = target - num

if complement in seen:

return [seen[complement], i]

seen[num] = i

return []

시간: O(n), 공간: O(n)

핵심: complement를 해시맵에서 O(1)에 조회

변형 문제와 팁

- **Three Sum** (LeetCode 15): 정렬 후 Two Pointers 조합

- **Product of Array Except Self** (LeetCode 238): prefix/suffix 곱 패턴

- 면접 팁: 항상 해시맵으로 O(n) 풀이가 가능한지 먼저 생각하세요

3. Pattern 2 — Two Pointers

핵심 아이디어

정렬된 배열이나 문자열에서 **두 개의 포인터를 양 끝에서 좁혀가며** 조건을 만족하는 쌍을 찾습니다. 또는 같은 방향으로 이동하는 fast/slow 포인터 패턴도 있습니다. O(n^2) brute force를 O(n)으로 최적화할 수 있습니다.

시간/공간 복잡도

- 시간: O(n) (이미 정렬된 경우) 또는 O(n log n) (정렬 필요 시)

- 공간: O(1) — 추가 공간 불필요

대표 문제

1. **Valid Palindrome** (LeetCode 125) — Easy

2. **Two Sum II - Sorted Array** (LeetCode 167) — Medium

3. **3Sum** (LeetCode 15) — Medium

4. **Container With Most Water** (LeetCode 11) — Medium

5. **Trapping Rain Water** (LeetCode 42) — Hard

Python 풀이 — Container With Most Water (LeetCode 11)

def maxArea(height: list[int]) -> int:

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

시간: O(n), 공간: O(1)

핵심: 더 낮은 벽을 이동해야 면적이 증가할 가능성이 있음

변형 문제와 팁

- **Trapping Rain Water**: 양쪽 최대 높이를 추적하는 변형

- 면접 팁: 입력이 정렬되어 있다면 Two Pointers를 가장 먼저 고려하세요

- 3Sum은 하나를 고정하고 나머지 두 개를 Two Pointers로 처리

4. Pattern 3 — Sliding Window

핵심 아이디어

**고정 또는 가변 크기의 윈도우**를 배열/문자열 위에서 슬라이드시키며, 윈도우 내의 최적값(최대합, 최소 길이, 조건 만족하는 부분 문자열 등)을 찾습니다. 새 원소를 추가하고 오래된 원소를 제거하면서 O(n)에 처리합니다.

시간/공간 복잡도

- 시간: O(n) — 각 원소가 윈도우에 최대 한 번 들어가고 한 번 나감

- 공간: O(k) — 윈도우 크기 또는 문자 종류 수

대표 문제

1. **Best Time to Buy and Sell Stock** (LeetCode 121) — Easy

2. **Longest Substring Without Repeating Characters** (LeetCode 3) — Medium

3. **Longest Repeating Character Replacement** (LeetCode 424) — Medium

4. **Minimum Window Substring** (LeetCode 76) — Hard

5. **Sliding Window Maximum** (LeetCode 239) — Hard

Python 풀이 — Longest Substring Without Repeating Characters (LeetCode 3)

def lengthOfLongestSubstring(s: str) -> int:

char_index = {} # 문자 -> 마지막 등장 인덱스

left = 0

max_len = 0

for right in range(len(s)):

if s[right] in char_index and char_index[s[right]] >= left:

중복 발견 시 윈도우 왼쪽을 중복 다음으로 이동

left = char_index[s[right]] + 1

char_index[s[right]] = right

max_len = max(max_len, right - left + 1)

return max_len

시간: O(n), 공간: O(min(n, 26))

핵심: 해시맵으로 중복 위치를 추적하며 윈도우 크기 갱신

변형 문제와 팁

- **Minimum Window Substring**: 필요 문자 카운트를 해시맵으로 관리하며 축소

- 고정 크기 윈도우: 윈도우 크기 k가 주어지면 right - left + 1 == k 유지

- 면접 팁: 부분 배열/문자열의 연속 조건이 있으면 Sliding Window를 고려하세요

5. Pattern 4 — Stack (Monotonic Stack)

핵심 아이디어

**LIFO(Last In First Out)** 특성을 활용합니다. 괄호 매칭, 수식 계산에는 기본 스택을, **Next Greater/Smaller Element** 문제에는 단조 스택(Monotonic Stack)을 사용합니다. 단조 스택은 스택 내 원소가 항상 증가 또는 감소 순서를 유지하도록 관리합니다.

시간/공간 복잡도

- 시간: O(n) — 각 원소가 스택에 최대 한 번 push, 한 번 pop

- 공간: O(n) — 스택 저장

대표 문제

1. **Valid Parentheses** (LeetCode 20) — Easy

2. **Min Stack** (LeetCode 155) — Medium

3. **Evaluate Reverse Polish Notation** (LeetCode 150) — Medium

4. **Daily Temperatures** (LeetCode 739) — Medium

5. **Largest Rectangle in Histogram** (LeetCode 84) — Hard

Python 풀이 — Daily Temperatures (LeetCode 739)

def dailyTemperatures(temperatures: list[int]) -> list[int]:

n = len(temperatures)

answer = [0] * n

stack = [] # 단조 감소 스택: (인덱스) 저장

for i in range(n):

현재 온도가 스택 top보다 높으면 pop하며 정답 기록

while stack and temperatures[i] > temperatures[stack[-1]]:

prev_idx = stack.pop()

answer[prev_idx] = i - prev_idx

stack.append(i)

return answer

시간: O(n), 공간: O(n)

핵심: 단조 감소 스택으로 다음 더 큰 원소까지의 거리를 O(n)에 계산

변형 문제와 팁

- **Largest Rectangle in Histogram**: 단조 증가 스택으로 높이별 최대 너비 계산

- **Next Greater Element**: 순환 배열이면 2n 순회로 처리

- 면접 팁: 현재 원소와 이전 원소의 대소 관계가 중요한 문제는 단조 스택을 생각하세요

6. Pattern 5 — Binary Search

핵심 아이디어

**정렬된 데이터에서 탐색 범위를 절반씩 줄여** O(log n)에 답을 찾습니다. 배열 탐색뿐 아니라 **결정 문제(최적화 문제를 이진 탐색으로 전환)** 에도 활용됩니다. "최소값의 최대화" 또는 "최대값의 최소화" 패턴이 대표적입니다.

시간/공간 복잡도

- 시간: O(log n)

- 공간: O(1) 반복문 / O(log n) 재귀

대표 문제

1. **Binary Search** (LeetCode 704) — Easy

2. **Search a 2D Matrix** (LeetCode 74) — Medium

3. **Koko Eating Bananas** (LeetCode 875) — Medium

4. **Find Minimum in Rotated Sorted Array** (LeetCode 153) — Medium

5. **Median of Two Sorted Arrays** (LeetCode 4) — Hard

Python 풀이 — Koko Eating Bananas (LeetCode 875)

def minEatingSpeed(piles: list[int], h: int) -> int:

이진 탐색: 먹는 속도의 범위 [1, max(piles)]

left, right = 1, max(piles)

while left < right:

mid = (left + right) // 2

mid 속도로 모든 바나나를 h시간 내에 먹을 수 있는지 확인

hours_needed = sum(math.ceil(pile / mid) for pile in piles)

if hours_needed <= h:

right = mid # 더 느린 속도도 가능한지 확인

else:

left = mid + 1 # 더 빠른 속도 필요

return left

시간: O(n * log(max(piles))), 공간: O(1)

핵심: "최소 속도"를 이진 탐색으로 찾는 결정 문제 패턴

변형 문제와 팁

- **Rotated Sorted Array**: 중간값과 양 끝을 비교하여 정렬된 쪽 판별

- 결정 문제 패턴: 조건 함수 canDo(x)가 단조적이면 이진 탐색 적용 가능

- 면접 팁: 정렬되어 있지 않더라도, 답의 범위가 단조적이면 이진 탐색을 고려하세요

7. Pattern 6 — Linked List

핵심 아이디어

연결 리스트는 포인터 조작이 핵심입니다. **역순, 병합, 사이클 탐지, 중간 노드 찾기** 등의 문제에서 반복적으로 등장합니다. fast/slow 포인터(Floyd 알고리즘)는 사이클 탐지와 중간 노드 찾기에 필수입니다.

시간/공간 복잡도

- 순회: O(n) 시간, O(1) 공간

- 재귀 방식: O(n) 시간, O(n) 스택 공간

대표 문제

1. **Reverse Linked List** (LeetCode 206) — Easy

2. **Merge Two Sorted Lists** (LeetCode 21) — Easy

3. **Linked List Cycle** (LeetCode 141) — Easy

4. **Reorder List** (LeetCode 143) — Medium

5. **Merge k Sorted Lists** (LeetCode 23) — Hard

Python 풀이 — Reverse Linked List (LeetCode 206)

class ListNode:

def __init__(self, val=0, next=None):

self.val = val

self.next = next

def reverseList(head: ListNode) -> ListNode:

prev = None

current = head

while current:

next_node = current.next # 다음 노드 저장

current.next = prev # 현재 노드의 방향을 역전

prev = current # prev를 한 칸 전진

current = next_node # current를 한 칸 전진

return prev

시간: O(n), 공간: O(1)

핵심: 세 개의 포인터(prev, current, next)로 제자리 역전

변형 문제와 팁

- **Reorder List**: 중간 찾기 + 후반 역전 + 병합의 3단계

- **Merge k Sorted Lists**: 최소 힙으로 k개 리스트의 head를 관리

- 면접 팁: dummy 노드를 활용하면 edge case 처리가 쉬워집니다

8. Pattern 7 — Trees (BFS/DFS)

핵심 아이디어

트리 문제는 **재귀적 DFS**(전위/중위/후위 순회)와 **BFS**(레벨 순회)로 나뉩니다. 대부분의 이진 트리 문제는 **"현재 노드에서 무엇을 하고, 자식에게 무엇을 위임할 것인가"** 를 정의하면 풀 수 있습니다.

시간/공간 복잡도

- DFS: O(n) 시간, O(h) 공간 (h = 트리 높이, 최악 O(n))

- BFS: O(n) 시간, O(w) 공간 (w = 최대 레벨 너비)

대표 문제

1. **Maximum Depth of Binary Tree** (LeetCode 104) — Easy

2. **Invert Binary Tree** (LeetCode 226) — Easy

3. **Binary Tree Level Order Traversal** (LeetCode 102) — Medium

4. **Validate Binary Search Tree** (LeetCode 98) — Medium

5. **Binary Tree Maximum Path Sum** (LeetCode 124) — Hard

Python 풀이 — Binary Tree Level Order Traversal (LeetCode 102)

from collections import deque

class TreeNode:

def __init__(self, val=0, left=None, right=None):

self.val = val

self.left = left

self.right = right

def levelOrder(root: TreeNode) -> list[list[int]]:

if not root:

return []

result = []

queue = deque([root])

while queue:

level_size = len(queue)

level = []

for _ in range(level_size):

node = queue.popleft()

level.append(node.val)

if node.left:

queue.append(node.left)

if node.right:

queue.append(node.right)

result.append(level)

return result

시간: O(n), 공간: O(n)

핵심: BFS에서 레벨 크기만큼 처리하여 레벨별 그룹화

변형 문제와 팁

- **BST 검증**: 중위 순회가 정렬 순서인지 확인하거나, 범위를 전달하는 DFS

- **Maximum Path Sum**: 후위 순회로 자식의 최대 기여값을 계산

- 면접 팁: 트리 문제에서는 base case(null 노드)를 먼저 처리하세요

9. Pattern 8 — Tries

핵심 아이디어

**Trie(트라이, 접두사 트리)** 는 문자열을 문자 단위로 저장하는 트리 구조입니다. 접두사 검색이 O(m) (m = 문자열 길이)에 가능하며, 자동완성, 사전 검색, 와일드카드 매칭에 활용됩니다.

시간/공간 복잡도

- 삽입/검색: O(m) — m은 문자열 길이

- 공간: O(총 문자 수 \* 알파벳 크기)

대표 문제

1. **Implement Trie (Prefix Tree)** (LeetCode 208) — Medium

2. **Design Add and Search Words** (LeetCode 211) — Medium

3. **Word Search II** (LeetCode 212) — Hard

Python 풀이 — Implement Trie (LeetCode 208)

class TrieNode:

def __init__(self):

self.children = {}

self.is_end = False

class Trie:

def __init__(self):

self.root = TrieNode()

def insert(self, word: str) -> None:

node = self.root

for ch in word:

if ch not in node.children:

node.children[ch] = TrieNode()

node = node.children[ch]

node.is_end = True

def search(self, word: str) -> bool:

node = self._find(word)

return node is not None and node.is_end

def startsWith(self, prefix: str) -> bool:

return self._find(prefix) is not None

def _find(self, prefix: str) -> TrieNode:

node = self.root

for ch in prefix:

if ch not in node.children:

return None

node = node.children[ch]

return node

시간: 삽입/검색 O(m), 공간: O(총 문자 수)

핵심: 각 노드가 자식 딕셔너리와 종료 플래그를 보유

변형 문제와 팁

- **Word Search II**: Trie + DFS 백트래킹 조합

- **Design Add and Search Words**: 와일드카드 `.`에 대해 재귀 DFS

- 면접 팁: 여러 문자열의 접두사를 반복 검색해야 할 때 Trie가 효율적입니다

10. Pattern 9 — Heap / Priority Queue

핵심 아이디어

**힙(Heap)** 은 최대/최소값을 O(1)에 조회하고 O(log n)에 삽입/삭제하는 자료구조입니다. Top K 문제, 스트리밍 데이터의 중간값, 작업 스케줄링 등에 핵심적으로 사용됩니다.

시간/공간 복잡도

- 삽입/삭제: O(log n)

- 최대/최소 조회: O(1)

- 힙 생성(heapify): O(n)

대표 문제

1. **Kth Largest Element in a Stream** (LeetCode 703) — Easy

2. **Last Stone Weight** (LeetCode 1046) — Easy

3. **K Closest Points to Origin** (LeetCode 973) — Medium

4. **Task Scheduler** (LeetCode 621) — Medium

5. **Find Median from Data Stream** (LeetCode 295) — Hard

Python 풀이 — Find Median from Data Stream (LeetCode 295)

class MedianFinder:

def __init__(self):

max_heap: 작은 쪽 절반 (음수로 저장하여 최대 힙 구현)

min_heap: 큰 쪽 절반

self.max_heap = [] # 왼쪽 절반

self.min_heap = [] # 오른쪽 절반

def addNum(self, num: int) -> None:

항상 max_heap에 먼저 추가

heapq.heappush(self.max_heap, -num)

max_heap의 최대값을 min_heap으로 이동

heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))

크기 균형: max_heap이 min_heap보다 크거나 같도록

if len(self.min_heap) > len(self.max_heap):

heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))

def findMedian(self) -> float:

if len(self.max_heap) > len(self.min_heap):

return -self.max_heap[0]

return (-self.max_heap[0] + self.min_heap[0]) / 2

시간: addNum O(log n), findMedian O(1)

핵심: 두 힙으로 데이터를 반반 나누어 중간값을 효율적으로 유지

변형 문제와 팁

- **Task Scheduler**: 최대 힙으로 가장 빈번한 작업부터 스케줄링

- Python의 heapq는 최소 힙이므로, 최대 힙이 필요하면 음수로 변환

- 면접 팁: Top K 문제는 크기 K의 최소 힙으로 O(n log k)에 해결 가능

11. Pattern 10 — Backtracking

핵심 아이디어

**가능한 모든 조합/순열/부분집합을 탐색**하되, **유효하지 않은 경로를 조기에 가지치기(pruning)** 합니다. 재귀 호출 + 선택/취소 패턴이 기본이며, 시간 복잡도가 지수적이므로 가지치기가 성능에 결정적입니다.

시간/공간 복잡도

- 부분집합: O(2^n)

- 순열: O(n!)

- 공간: O(n) — 재귀 깊이

대표 문제

1. **Subsets** (LeetCode 78) — Medium

2. **Combination Sum** (LeetCode 39) — Medium

3. **Permutations** (LeetCode 46) — Medium

4. **Word Search** (LeetCode 79) — Medium

5. **N-Queens** (LeetCode 51) — Hard

Python 풀이 — Combination Sum (LeetCode 39)

def combinationSum(candidates: list[int], target: int) -> list[list[int]]:

result = []

def backtrack(start: int, current: list[int], remaining: int):

if remaining == 0:

result.append(current[:]) # 현재 조합을 결과에 추가

return

if remaining < 0:

return # 가지치기

for i in range(start, len(candidates)):

current.append(candidates[i])

같은 원소 재사용 가능 -> start를 i로 유지

backtrack(i, current, remaining - candidates[i])

current.pop() # 선택 취소 (백트래킹)

backtrack(0, [], target)

return result

시간: O(2^t) (t = target / min(candidates)), 공간: O(target)

핵심: 선택 -> 재귀 -> 취소 패턴과 가지치기

변형 문제와 팁

- **Subsets**: 매 단계에서 현재 상태를 결과에 추가

- **Permutations**: visited 배열 또는 swap 기법 사용

- **N-Queens**: 행/열/대각선 충돌을 set으로 추적

- 면접 팁: 백트래킹 문제는 결정 트리를 그려보면 패턴이 보입니다

12. Pattern 11 — Graphs (BFS/DFS/Union-Find)

핵심 아이디어

그래프 문제는 **연결 요소, 최단 경로, 사이클 탐지, 위상 정렬** 등으로 나뉩니다. BFS는 최단 경로에, DFS는 경로 탐색과 사이클 탐지에, Union-Find는 연결 요소 관리에 적합합니다.

시간/공간 복잡도

- BFS/DFS: O(V + E) 시간, O(V) 공간

- Union-Find: O(alpha(n)) 거의 O(1) per operation

- 위상 정렬: O(V + E)

대표 문제

1. **Number of Islands** (LeetCode 200) — Medium

2. **Clone Graph** (LeetCode 133) — Medium

3. **Course Schedule** (LeetCode 207) — Medium (위상 정렬)

4. **Pacific Atlantic Water Flow** (LeetCode 417) — Medium

5. **Graph Valid Tree** (LeetCode 261) — Medium (Union-Find)

Python 풀이 — Number of Islands (LeetCode 200)

def numIslands(grid: list[list[str]]) -> int:

if not grid:

return 0

rows, cols = len(grid), len(grid[0])

count = 0

def dfs(r: int, c: int):

범위 초과 또는 물이면 리턴

if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':

return

grid[r][c] = '0' # 방문 표시 (섬을 물로 변경)

상하좌우 탐색

dfs(r + 1, c)

dfs(r - 1, c)

dfs(r, c + 1)

dfs(r, c - 1)

for r in range(rows):

for c in range(cols):

if grid[r][c] == '1':

count += 1

dfs(r, c)

return count

시간: O(m * n), 공간: O(m * n) 최악의 재귀 깊이

핵심: 새 섬을 발견할 때마다 DFS로 전체를 방문 처리

Union-Find 구현

class UnionFind:

def __init__(self, n: int):

self.parent = list(range(n))

self.rank = [0] * n

self.count = n # 연결 요소 개수

def find(self, x: int) -> int:

if self.parent[x] != x:

self.parent[x] = self.find(self.parent[x]) # 경로 압축

return self.parent[x]

def union(self, x: int, y: int) -> bool:

px, py = self.find(x), self.find(y)

if px == py:

return False

랭크 기반 합치기

if self.rank[px] < self.rank[py]:

px, py = py, px

self.parent[py] = px

if self.rank[px] == self.rank[py]:

self.rank[px] += 1

self.count -= 1

return True

변형 문제와 팁

- **Course Schedule**: 위상 정렬(Kahn 알고리즘)으로 사이클 탐지

- **Pacific Atlantic Water Flow**: 역방향 BFS — 바다에서 시작하여 내륙으로

- 면접 팁: 그래프 문제는 먼저 인접 리스트/행렬 표현을 결정하고, BFS/DFS/Union-Find 중 적합한 것을 선택하세요

13. Pattern 12 — Dynamic Programming (1D)

핵심 아이디어

**1차원 DP**는 단일 변수에 대한 최적 부분 구조를 활용합니다. 점화식 dp[i]를 정의하고, 이전 상태(dp[i-1], dp[i-2] 등)로부터 현재 상태를 계산합니다. 피보나치, 계단 오르기, 도둑질 문제가 전형적입니다.

시간/공간 복잡도

- 시간: O(n) ~ O(n \* k)

- 공간: O(n) (테이블) 또는 O(1) (공간 최적화 시)

대표 문제

1. **Climbing Stairs** (LeetCode 70) — Easy

2. **House Robber** (LeetCode 198) — Medium

3. **Coin Change** (LeetCode 322) — Medium

4. **Longest Increasing Subsequence** (LeetCode 300) — Medium

5. **Word Break** (LeetCode 139) — Medium

Python 풀이 — Coin Change (LeetCode 322)

def coinChange(coins: list[int], amount: int) -> int:

dp[i] = i 금액을 만들기 위한 최소 동전 수

dp = [float('inf')] * (amount + 1)

dp[0] = 0 # 0원은 0개의 동전으로 가능

for i in range(1, amount + 1):

for coin in coins:

if coin <= i and dp[i - coin] != float('inf'):

dp[i] = min(dp[i], dp[i - coin] + 1)

return dp[amount] if dp[amount] != float('inf') else -1

시간: O(amount * len(coins)), 공간: O(amount)

핵심: 각 금액에 대해 모든 동전을 시도하여 최소값 갱신

변형 문제와 팁

- **House Robber**: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) — 인접 집 조건

- **LIS**: O(n log n) 풀이는 이진 탐색 + 보조 배열 활용

- **Word Break**: dp[i] = 어떤 j에 대해 dp[j] and s[j:i] in wordSet

- 면접 팁: 1D DP는 공간을 O(1)로 줄일 수 있는 경우가 많으니 최적화도 언급하세요

14. Pattern 13 — Dynamic Programming (2D)

핵심 아이디어

**2차원 DP**는 두 변수(두 문자열, 격자 좌표 등)에 대한 상태를 정의합니다. dp[i][j]가 첫 번째 입력의 i번째까지, 두 번째 입력의 j번째까지 고려한 결과를 나타냅니다.

시간/공간 복잡도

- 시간: O(m \* n)

- 공간: O(m \* n) 또는 O(min(m, n)) (행 압축 시)

대표 문제

1. **Unique Paths** (LeetCode 62) — Medium

2. **Longest Common Subsequence** (LeetCode 1143) — Medium

3. **Best Time to Buy and Sell Stock with Cooldown** (LeetCode 309) — Medium

4. **Target Sum** (LeetCode 494) — Medium

5. **Edit Distance** (LeetCode 72) — Medium

Python 풀이 — Longest Common Subsequence (LeetCode 1143)

def longestCommonSubsequence(text1: str, text2: str) -> int:

m, n = len(text1), len(text2)

dp[i][j] = text1의 처음 i글자와 text2의 처음 j글자의 LCS 길이

dp = [[0] * (n + 1) for _ in range(m + 1)]

for i in range(1, m + 1):

for j in range(1, n + 1):

if text1[i - 1] == text2[j - 1]:

dp[i][j] = dp[i - 1][j - 1] + 1

else:

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

return dp[m][n]

시간: O(m * n), 공간: O(m * n)

핵심: 문자가 같으면 대각선 +1, 다르면 위/왼쪽 최대값

변형 문제와 팁

- **Edit Distance**: 삽입/삭제/교체 3가지 연산을 각각 고려

- **Target Sum**: 배낭 문제(Knapsack)로 변환하여 풀이

- 공간 최적화: 이전 행만 필요하면 1D 배열로 압축 가능

- 면접 팁: 2D DP 점화식을 명확히 정의한 후 코딩을 시작하세요

15. Pattern 14 — Greedy

핵심 아이디어

**각 단계에서 지역적으로 최적인 선택**이 전역적으로도 최적인 결과를 보장하는 문제에 적용합니다. DP와 달리 이전 선택을 되돌리지 않으며, 올바른 Greedy 전략을 세우는 것이 핵심입니다. 증명이 어려운 경우가 많으므로, 패턴을 외우는 것이 효율적입니다.

시간/공간 복잡도

- 보통 O(n) 또는 O(n log n) (정렬 필요 시)

- 공간: O(1) ~ O(n)

대표 문제

1. **Maximum Subarray** (LeetCode 53) — Medium

2. **Jump Game** (LeetCode 55) — Medium

3. **Jump Game II** (LeetCode 45) — Medium

4. **Gas Station** (LeetCode 134) — Medium

5. **Hand of Straights** (LeetCode 846) — Medium

Python 풀이 — Jump Game (LeetCode 55)

def canJump(nums: list[int]) -> bool:

goal: 도달해야 하는 위치 (뒤에서 앞으로)

goal = len(nums) - 1

for i in range(len(nums) - 2, -1, -1):

if i + nums[i] >= goal:

goal = i # 현재 위치에서 goal에 도달 가능하면 goal 갱신

return goal == 0

시간: O(n), 공간: O(1)

핵심: 뒤에서부터 도달 가능 여부를 Greedy하게 판단

변형 문제와 팁

- **Maximum Subarray (Kadane)**: 현재까지의 합이 음수면 버리고 새로 시작

- **Jump Game II**: BFS 방식으로 레벨별 최소 점프 수 계산

- 면접 팁: Greedy가 맞는지 확신이 없으면, 작은 반례로 검증해보세요

16. Pattern 15 — Intervals and Math

핵심 아이디어

**구간(Interval) 문제**는 시작점/끝점으로 정렬한 후 겹침을 처리하는 것이 핵심입니다. 병합, 삽입, 최소 회의실 수 등이 대표적입니다. 수학 문제는 비트 연산, 모듈러 연산, 기하학적 계산 등이 포함됩니다.

시간/공간 복잡도

- 정렬: O(n log n)

- 스캔: O(n)

- 공간: O(n) (결과 저장)

대표 문제

1. **Merge Intervals** (LeetCode 56) — Medium

2. **Insert Interval** (LeetCode 57) — Medium

3. **Non-overlapping Intervals** (LeetCode 435) — Medium

4. **Meeting Rooms II** (LeetCode 253) — Medium

5. **Rotate Image** (LeetCode 48) — Medium

Python 풀이 — Merge Intervals (LeetCode 56)

def merge(intervals: list[list[int]]) -> list[list[int]]:

시작점 기준 정렬

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)

핵심: 정렬 후 겹치는 구간을 순차적으로 병합

변형 문제와 팁

- **Meeting Rooms II**: 시작/끝 시간을 분리하여 정렬 후 카운팅

- **Non-overlapping Intervals**: 끝점 기준 정렬 후 Greedy로 최소 제거

- **Rotate Image**: 전치(transpose) 후 좌우 반전

- 면접 팁: 구간 문제는 먼저 정렬 기준(시작점 vs 끝점)을 결정하세요

17. 75문제 선별 체크리스트

아래는 NeetCode 150 기반으로 선별한 **핵심 75문제** 체크리스트입니다.

| # | 문제 | 난이도 | 패턴 | 빈출 기업 |

| --- | --------------------------------------------- | ------ | -------------------- | -------------------- |

18. 실전 면접 팁

45분 시간 배분

| 단계 | 시간 | 활동 |

| ----------- | ---- | ---------------------------------- |

| 문제 이해 | 5분 | 요구사항 확인, 예제 검토, 질문 |

| 접근법 논의 | 10분 | brute force 언급 후 최적 해법 설명 |

| 코딩 | 20분 | 클린 코드 작성 |

| 테스트 | 5분 | 예제 실행, 에지 케이스 확인 |

| 질의응답 | 5분 | 복잡도 분석, 최적화 논의 |

UMPIRE 방법론

코딩 인터뷰에서 체계적으로 문제를 풀기 위한 프레임워크입니다.

1. **U - Understand**: 문제를 완전히 이해합니다. 입출력 예시를 확인하고, 모호한 점을 질문합니다.

2. **M - Match**: 알고 있는 패턴과 매칭합니다. 이 15가지 패턴 중 어떤 것이 적합한지 판단합니다.

3. **P - Plan**: 구체적인 풀이 계획을 세웁니다. 의사코드를 작성합니다.

4. **I - Implement**: 계획에 따라 깔끔하게 코딩합니다.

5. **R - Review**: 코드를 한 줄씩 리뷰하며 버그를 찾습니다.

6. **E - Evaluate**: 시간/공간 복잡도를 분석하고, 최적화 가능 여부를 논의합니다.

에지 케이스 체크리스트

면접에서 놓치기 쉬운 에지 케이스들입니다.

- 빈 입력 (빈 배열, 빈 문자열, null/None)

- 단일 원소 입력

- 모든 원소가 같은 경우

- 음수 값이 포함된 경우

- 매우 큰 입력 (오버플로 확인)

- 정렬되지 않은 입력 (정렬을 전제하지 마세요)

- 중복 원소가 있는 경우

AI 코파일럿 시대의 면접 변화

2025년 코딩 면접에서 주목할 변화들입니다.

1. **시스템 디자인 비중 증가**: AI가 코딩을 대신할 수 있으므로, 아키텍처 설계 능력이 더 중요해짐

2. **코드 리뷰 역량 평가**: 주어진 코드의 버그/성능 문제를 찾는 문제 유형 증가

3. **변형 문제 증가**: 기존 문제의 조건을 바꾸어 외운 풀이가 통하지 않게 함

4. **실시간 협업 코딩**: 면접관과 페어 프로그래밍 형태로 진행하는 케이스 증가

5. **알고리즘 + 시스템 디자인 복합 문제**: 알고리즘 최적화를 시스템 수준에서 논의

19. 퀴즈

배운 내용을 점검해보세요.

**정답: O(n)**

배열을 한 번 순회하면서, 각 원소에 대해 complement(target - num)가 해시맵에 있는지 O(1)에 확인합니다. 전체 시간 복잡도는 O(n)이고, 공간 복잡도도 O(n)입니다. brute force의 O(n^2) 대비 큰 개선입니다.

**정답: 연속적인 부분 배열 또는 부분 문자열에 대한 최적값을 찾는 문제**

Sliding Window는 배열이나 문자열에서 연속적인 구간(subarray/substring)의 최대값, 최소값, 특정 조건을 만족하는 길이 등을 구할 때 사용합니다. "연속적" 조건이 핵심이며, 각 원소가 윈도우에 한 번 들어가고 한 번 나가므로 O(n)에 해결됩니다.

**정답: Next Greater Element / Next Smaller Element 유형의 문제**

단조 스택은 각 원소에 대해 다음으로 큰(또는 작은) 원소를 찾는 문제에 사용됩니다. 스택 내 원소가 항상 증가 또는 감소 순서를 유지하도록 관리하여, O(n)에 모든 원소의 Next Greater/Smaller를 계산합니다. Daily Temperatures, Largest Rectangle in Histogram이 대표 문제입니다.

**정답: 거의 O(1) — 정확히는 O(alpha(n))**

alpha(n)은 아커만 함수의 역함수로, 실질적으로 모든 입력에 대해 5 이하의 값을 가집니다. 경로 압축은 find 시 부모를 루트로 직접 연결하고, 랭크 기반 합치기는 트리 높이가 낮은 쪽을 높은 쪽에 합칩니다. 두 최적화를 함께 적용하면 거의 상수 시간에 동작합니다.

**정답: Understand, Match, Plan, Implement, Review, Evaluate**

1. **Understand**: 문제를 완전히 이해하고 명확화 질문을 합니다

2. **Match**: 알고 있는 알고리즘 패턴과 매칭합니다

3. **Plan**: 구체적인 풀이 계획과 의사코드를 작성합니다

4. **Implement**: 계획에 따라 깔끔하게 코딩합니다

5. **Review**: 코드를 리뷰하고 버그를 찾습니다

6. **Evaluate**: 시간/공간 복잡도를 분석합니다

20. 참고 자료

1. [NeetCode 150 로드맵](https://neetcode.io/roadmap) — 패턴별 체계적 문제 분류

2. [Blind 75 문제 리스트](https://www.teamblind.com/post/New-Year-Gift---Curated-List-of-Top-75-LeetCode-Questions-to-Save-Your-Time-OaM1orEU) — 원조 큐레이션 리스트

3. [Grind 75 by Yangshun](https://www.techinterviewhandbook.org/grind75) — 맞춤형 스케줄링

4. [LeetCode](https://leetcode.com/) — 온라인 코딩 문제 플랫폼

5. [Introduction to Algorithms (CLRS)](https://mitpress.mit.edu/books/introduction-algorithms-fourth-edition) — 알고리즘의 바이블

6. [알고리즘 문제 해결 전략 (구종만)](https://book.algospot.com/) — 한국어 알고리즘 교재

7. [Grokking the Coding Interview](https://www.designgurus.io/course/grokking-the-coding-interview) — 패턴 기반 학습

8. [Tech Interview Handbook](https://www.techinterviewhandbook.org/) — 면접 전반 가이드

9. [Competitive Programmer's Handbook (Antti Laaksonen)](https://cses.fi/book/book.pdf) — 무료 알고리즘 교재

10. [VisuAlgo](https://visualgo.net/) — 알고리즘 시각화 도구

11. [Big-O Cheat Sheet](https://www.bigocheatsheet.com/) — 시간/공간 복잡도 정리

12. [Python collections 공식 문서](https://docs.python.org/3/library/collections.html) — Counter, deque, defaultdict

13. [Python heapq 공식 문서](https://docs.python.org/3/library/heapq.html) — 힙 연산

14. [Back to Back SWE (YouTube)](https://www.youtube.com/channel/UCmJz2DV1a3yfgrR7GqRtUUA) — 알고리즘 해설

15. [Abdul Bari Algorithms (YouTube)](https://www.youtube.com/watch?v=0IAPZzGSbME&list=PLDN4rrl48XKpZkf03iYFl-O29szjTrs_O) — 알고리즘 강의

16. [System Design Interview (Alex Xu)](https://www.amazon.com/System-Design-Interview-insiders-Second/dp/B08CMF2CQF) — 시스템 디자인 면접 가이드