코딩 테스트 패턴 완전 정복: FAANG 합격을 위한 알고리즘 15 패턴 + 75문제 로드맵

• 1. 2025 코딩 인터뷰 현황
  • FAANG 출제 빈도와 트렌드
  • AI-Aware 코딩 라운드의 등장
  • NeetCode 150 vs Blind 75 vs Grind 75 비교
  • 언어 선택: Python vs Java vs TypeScript
  • 12주 학습 로드맵 개요
• 2. Pattern 1 — Arrays and Hashing
  • 핵심 아이디어
  • 시간/공간 복잡도
  • 대표 문제
  • Python 풀이 — Two Sum (LeetCode 1)
  • 변형 문제와 팁
• 3. Pattern 2 — Two Pointers
  • 핵심 아이디어
  • 시간/공간 복잡도
  • 대표 문제
  • Python 풀이 — Container With Most Water (LeetCode 11)
  • 변형 문제와 팁
• 4. Pattern 3 — Sliding Window
  • 핵심 아이디어
  • 시간/공간 복잡도
  • 대표 문제
  • Python 풀이 — Longest Substring Without Repeating Characters (LeetCode 3)
  • 변형 문제와 팁
• 5. Pattern 4 — Stack (Monotonic Stack)
  • 핵심 아이디어
  • 시간/공간 복잡도
  • 대표 문제
  • Python 풀이 — Daily Temperatures (LeetCode 739)
  • 변형 문제와 팁
• 6. Pattern 5 — Binary Search
  • 핵심 아이디어
  • 시간/공간 복잡도
  • 대표 문제
  • Python 풀이 — Koko Eating Bananas (LeetCode 875)
  • 변형 문제와 팁
• 7. Pattern 6 — Linked List
  • 핵심 아이디어
  • 시간/공간 복잡도
  • 대표 문제
  • Python 풀이 — Reverse Linked List (LeetCode 206)
  • 변형 문제와 팁
• 8. Pattern 7 — Trees (BFS/DFS)
  • 핵심 아이디어
  • 시간/공간 복잡도
  • 대표 문제
  • Python 풀이 — Binary Tree Level Order Traversal (LeetCode 102)
  • 변형 문제와 팁
• 9. Pattern 8 — Tries
  • 핵심 아이디어
  • 시간/공간 복잡도
  • 대표 문제
  • Python 풀이 — Implement Trie (LeetCode 208)
  • 변형 문제와 팁
• 10. Pattern 9 — Heap / Priority Queue
  • 핵심 아이디어
  • 시간/공간 복잡도
  • 대표 문제
  • Python 풀이 — Find Median from Data Stream (LeetCode 295)
  • 변형 문제와 팁
• 11. Pattern 10 — Backtracking
  • 핵심 아이디어
  • 시간/공간 복잡도
  • 대표 문제
  • Python 풀이 — Combination Sum (LeetCode 39)
  • 변형 문제와 팁
• 12. Pattern 11 — Graphs (BFS/DFS/Union-Find)
  • 핵심 아이디어
  • 시간/공간 복잡도
  • 대표 문제
  • Python 풀이 — Number of Islands (LeetCode 200)
  • Union-Find 구현
  • 변형 문제와 팁
• 13. Pattern 12 — Dynamic Programming (1D)
  • 핵심 아이디어
  • 시간/공간 복잡도
  • 대표 문제
  • Python 풀이 — Coin Change (LeetCode 322)
  • 변형 문제와 팁
• 14. Pattern 13 — Dynamic Programming (2D)
  • 핵심 아이디어
  • 시간/공간 복잡도
  • 대표 문제
  • Python 풀이 — Longest Common Subsequence (LeetCode 1143)
  • 변형 문제와 팁
• 15. Pattern 14 — Greedy
  • 핵심 아이디어
  • 시간/공간 복잡도
  • 대표 문제
  • Python 풀이 — Jump Game (LeetCode 55)
  • 변형 문제와 팁
• 16. Pattern 15 — Intervals and Math
  • 핵심 아이디어
  • 시간/공간 복잡도
  • 대표 문제
  • Python 풀이 — Merge Intervals (LeetCode 56)
  • 변형 문제와 팁
• 17. 75문제 선별 체크리스트
• 18. 실전 면접 팁
  • 45분 시간 배분
  • UMPIRE 방법론
  • 에지 케이스 체크리스트
  • AI 코파일럿 시대의 면접 변화
• 19. 퀴즈
• 20. 참고 자료

1. 2025 코딩 인터뷰 현황

FAANG 출제 빈도와 트렌드

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

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

AI-Aware 코딩 라운드의 등장

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

NeetCode 150 vs Blind 75 vs Grind 75 비교

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

언어 선택: Python vs Java vs TypeScript

• Python: 코드가 간결하고 빠른 풀이 가능. FAANG 면접에서 가장 인기 있는 언어. 내장 라이브러리(heapq, collections, itertools)가 강력
• Java: 타입 안전성과 성능이 장점. Amazon, Google에서 선호. TreeMap, PriorityQueue 등 자료구조가 풍부
• TypeScript: 프론트엔드 직군 면접에서 유리. 하지만 알고리즘 문제에서는 Python 대비 장점이 적음

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

12주 학습 로드맵 개요

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)

import math

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)

import heapq

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분 시간 배분

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. 퀴즈

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

20. 참고 자료

1. NeetCode 150 로드맵 — 패턴별 체계적 문제 분류
2. Blind 75 문제 리스트 — 원조 큐레이션 리스트
3. Grind 75 by Yangshun — 맞춤형 스케줄링
4. LeetCode — 온라인 코딩 문제 플랫폼
5. Introduction to Algorithms (CLRS) — 알고리즘의 바이블
6. 알고리즘 문제 해결 전략 (구종만) — 한국어 알고리즘 교재
7. Grokking the Coding Interview — 패턴 기반 학습
8. Tech Interview Handbook — 면접 전반 가이드
9. Competitive Programmer's Handbook (Antti Laaksonen) — 무료 알고리즘 교재
10. VisuAlgo — 알고리즘 시각화 도구
11. Big-O Cheat Sheet — 시간/공간 복잡도 정리
12. Python collections 공식 문서 — Counter, deque, defaultdict
13. Python heapq 공식 문서 — 힙 연산
14. Back to Back SWE (YouTube) — 알고리즘 해설
15. Abdul Bari Algorithms (YouTube) — 알고리즘 강의
16. System Design Interview (Alex Xu) — 시스템 디자인 면접 가이드