FAANG 코딩 인터뷰 완전 정복: 백트래킹, 힙, 고급 패턴

이 글에서는 FAANG 인터뷰에서 자주 출제되는 백트래킹, 힙/우선순위 큐, 단조 스택, 트라이, 비트 조작 패턴을 다룹니다.

1. Backtracking 패턴

백트래킹 핵심 템플릿

백트래킹은 결정 트리를 탐색하여 조건을 만족하는 모든 해를 찾는 기법입니다.

def backtrack(state, choices):
    # 기저 사례: 유효한 해를 찾았으면 결과에 추가
    if is_solution(state):
        result.append(state[:])  # 복사본을 저장
        return

    for choice in choices:
        # Choose: 선택
        make_choice(state, choice)

        # Explore: 탐색 (재귀)
        backtrack(state, remaining_choices)

        # Unchoose: 되돌리기 (핵심!)
        undo_choice(state, choice)

핵심 원칙:

현재 상태의 복사본을 결과에 저장 (참조가 아닌 값)
선택 전후의 상태가 동일하게 유지되어야 함
가지치기(Pruning)로 불필요한 탐색 제거

Subsets (LeetCode 78)

def subsets(nums: list) -> list:
    result = []

    def backtrack(start, current):
        result.append(current[:])  # 현재 부분집합 저장
        for i in range(start, len(nums)):
            current.append(nums[i])    # Choose
            backtrack(i + 1, current)  # Explore
            current.pop()              # Unchoose

    backtrack(0, [])
    return result

시간 복잡도: O(n * 2^n)
공간 복잡도: O(n) (재귀 스택)

Subsets II - 중복 처리 (LeetCode 90)

def subsetsWithDup(nums: list) -> list:
    nums.sort()  # 중복 처리를 위해 정렬
    result = []

    def backtrack(start, current):
        result.append(current[:])
        for i in range(start, len(nums)):
            # 같은 레벨에서 중복 건너뛰기
            if i > start and nums[i] == nums[i-1]:
                continue
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()

    backtrack(0, [])
    return result

Permutations (LeetCode 46)

def permute(nums: list) -> list:
    result = []

    def backtrack(current, remaining):
        if not remaining:
            result.append(current[:])
            return
        for i in range(len(remaining)):
            current.append(remaining[i])                  # Choose
            backtrack(current, remaining[:i] + remaining[i+1:])  # Explore
            current.pop()                                  # Unchoose

    backtrack([], nums)
    return result

# 방문 배열 사용 방법 (더 효율적)
def permute_v2(nums: list) -> list:
    result = []
    visited = [False] * len(nums)

    def backtrack(current):
        if len(current) == len(nums):
            result.append(current[:])
            return
        for i in range(len(nums)):
            if visited[i]:
                continue
            visited[i] = True
            current.append(nums[i])
            backtrack(current)
            current.pop()
            visited[i] = False

    backtrack([])
    return result

Permutations II - 중복 처리 (LeetCode 47)

def permuteUnique(nums: list) -> list:
    nums.sort()
    result = []
    visited = [False] * len(nums)

    def backtrack(current):
        if len(current) == len(nums):
            result.append(current[:])
            return
        for i in range(len(nums)):
            if visited[i]:
                continue
            # 중복 건너뛰기: 같은 값의 이전 원소가 아직 방문되지 않았으면 건너뜀
            if i > 0 and nums[i] == nums[i-1] and not visited[i-1]:
                continue
            visited[i] = True
            current.append(nums[i])
            backtrack(current)
            current.pop()
            visited[i] = False

    backtrack([])
    return result

Combination Sum (LeetCode 39)

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

    def backtrack(start, current, remaining):
        if remaining == 0:
            result.append(current[:])
            return
        if remaining < 0:
            return
        for i in range(start, len(candidates)):
            current.append(candidates[i])
            backtrack(i, current, remaining - candidates[i])  # 같은 원소 재사용 가능
            current.pop()

    backtrack(0, [], target)
    return result

Combination Sum II (LeetCode 40)

def combinationSum2(candidates: list, target: int) -> list:
    candidates.sort()
    result = []

    def backtrack(start, current, remaining):
        if remaining == 0:
            result.append(current[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break
            if i > start and candidates[i] == candidates[i-1]:
                continue
            current.append(candidates[i])
            backtrack(i + 1, current, remaining - candidates[i])
            current.pop()

    backtrack(0, [], target)
    return result

N-Queens (LeetCode 51)

def solveNQueens(n: int) -> list:
    result = []
    cols = set()
    diag1 = set()  # row - col (우하향 대각선)
    diag2 = set()  # row + col (좌하향 대각선)

    def backtrack(row, board):
        if row == n:
            result.append([''.join(r) for r in board])
            return
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            board[row][col] = 'Q'
            backtrack(row + 1, board)
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)
            board[row][col] = '.'

    board = [['.' for _ in range(n)] for _ in range(n)]
    backtrack(0, board)
    return result

Word Search (LeetCode 79)

def exist(board: list, word: str) -> bool:
    rows, cols = len(board), len(board[0])

    def backtrack(r, c, idx):
        if idx == len(word):
            return True
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False
        if board[r][c] != word[idx]:
            return False

        temp = board[r][c]
        board[r][c] = '#'  # 방문 표시 (백트래킹 시 복원)

        found = (
            backtrack(r+1, c, idx+1) or
            backtrack(r-1, c, idx+1) or
            backtrack(r, c+1, idx+1) or
            backtrack(r, c-1, idx+1)
        )

        board[r][c] = temp  # 복원
        return found

    for r in range(rows):
        for c in range(cols):
            if backtrack(r, c, 0):
                return True
    return False

2. Heap / Priority Queue 패턴

Python heapq 완전 정복

import heapq

# 최소 힙 (기본)
min_heap = []
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 2)
print(heapq.heappop(min_heap))  # 1 (최솟값)

# 최대 힙 (음수로 변환)
max_heap = []
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -2)
print(-heapq.heappop(max_heap))  # 3 (최댓값)

# 리스트로 힙 구성
nums = [3, 1, 4, 1, 5, 9]
heapq.heapify(nums)  # O(n)

# n번째 최댓값
heapq.nlargest(3, nums)   # 상위 3개
heapq.nsmallest(3, nums)  # 하위 3개

# 튜플 힙 (우선순위, 값) 형태로 복잡한 정렬
heap = [(1, 'task_a'), (3, 'task_b'), (2, 'task_c')]
heapq.heapify(heap)
priority, task = heapq.heappop(heap)  # (1, 'task_a')

Kth Largest Element (LeetCode 215)

def findKthLargest(nums: list, k: int) -> int:
    # 크기 k의 최소 힙 유지
    min_heap = []
    for num in nums:
        heapq.heappush(min_heap, num)
        if len(min_heap) > k:
            heapq.heappop(min_heap)
    return min_heap[0]  # k번째 최댓값

# 또는 QuickSelect O(n) 평균
import random

def findKthLargest_quickselect(nums: list, k: int) -> int:
    def quickselect(left, right, k_smallest):
        pivot = nums[random.randint(left, right)]
        lo, hi, mid = left, right, left
        while mid <= hi:
            if nums[mid] < pivot:
                nums[lo], nums[mid] = nums[mid], nums[lo]
                lo += 1
                mid += 1
            elif nums[mid] > pivot:
                nums[hi], nums[mid] = nums[mid], nums[hi]
                hi -= 1
            else:
                mid += 1
        if k_smallest < lo:
            return quickselect(left, lo - 1, k_smallest)
        elif k_smallest >= mid:
            return quickselect(mid, right, k_smallest)
        else:
            return nums[lo]

    return quickselect(0, len(nums) - 1, len(nums) - k)

Top K Frequent Elements (LeetCode 347)

from collections import Counter

def topKFrequent(nums: list, k: int) -> list:
    count = Counter(nums)
    # (빈도수, 값) 쌍으로 최소 힙 유지
    heap = []
    for num, freq in count.items():
        heapq.heappush(heap, (freq, num))
        if len(heap) > k:
            heapq.heappop(heap)
    return [num for freq, num in heap]

# 버킷 정렬 방법 O(n)
def topKFrequent_bucket(nums: list, k: int) -> list:
    count = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]
    for num, freq in count.items():
        buckets[freq].append(num)
    result = []
    for i in range(len(buckets) - 1, -1, -1):
        result.extend(buckets[i])
        if len(result) >= k:
            return result[:k]
    return result

Merge K Sorted Lists (LeetCode 23)

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

def mergeKLists(lists: list) -> ListNode:
    heap = []
    # 각 리스트의 첫 번째 노드를 힙에 추가
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))

    dummy = ListNode(0)
    curr = dummy

    while heap:
        val, i, node = heapq.heappop(heap)
        curr.next = node
        curr = curr.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))

    return dummy.next

시간 복잡도: O(N log k), N = 총 노드 수, k = 리스트 수

Find Median from Data Stream (LeetCode 295)

두 힙(최대 힙 + 최소 힙)을 사용하는 핵심 패턴입니다.

class MedianFinder:
    def __init__(self):
        self.small = []  # 최대 힙 (하위 절반, 음수로 저장)
        self.large = []  # 최소 힙 (상위 절반)

    def addNum(self, num: int) -> None:
        # small 힙에 추가 후 균형 조정
        heapq.heappush(self.small, -num)
        # small의 최댓값 > large의 최솟값이면 이동
        if self.small and self.large and (-self.small[0] > self.large[0]):
            heapq.heappush(self.large, -heapq.heappop(self.small))
        # 크기 균형 조정
        if len(self.small) > len(self.large) + 1:
            heapq.heappush(self.large, -heapq.heappop(self.small))
        if len(self.large) > len(self.small):
            heapq.heappush(self.small, -heapq.heappop(self.large))

    def findMedian(self) -> float:
        if len(self.small) > len(self.large):
            return -self.small[0]
        return (-self.small[0] + self.large[0]) / 2

Task Scheduler (LeetCode 621)

from collections import Counter

def leastInterval(tasks: list, n: int) -> int:
    count = Counter(tasks)
    max_heap = [-c for c in count.values()]
    heapq.heapify(max_heap)

    time = 0
    queue = []  # (count, available_time)

    while max_heap or queue:
        time += 1
        if max_heap:
            cnt = 1 + heapq.heappop(max_heap)
            if cnt:
                queue.append((cnt, time + n))
        if queue and queue[0][1] == time:
            heapq.heappush(max_heap, queue.pop(0)[0])

    return time

3. Monotonic Stack 패턴

단조 스택 개념

단조 스택은 스택 내 원소들이 단조증가 또는 단조감소를 유지하는 스택입니다.

단조 증가 스택: 이전보다 작거나 같은 원소가 오면 pop (다음 작은 원소 문제)
단조 감소 스택: 이전보다 크거나 같은 원소가 오면 pop (다음 큰 원소 문제)

Daily Temperatures (LeetCode 739)

def dailyTemperatures(temperatures: list) -> list:
    n = len(temperatures)
    result = [0] * n
    stack = []  # (온도, 인덱스) 또는 인덱스만 저장

    for i, temp in enumerate(temperatures):
        # 스택 top보다 현재 온도가 높으면 pop (더 따뜻한 날 발견)
        while stack and temperatures[stack[-1]] < temp:
            idx = stack.pop()
            result[idx] = i - idx
        stack.append(i)

    return result

Next Greater Element (LeetCode 496)

def nextGreaterElement(nums1: list, nums2: list) -> list:
    next_greater = {}
    stack = []

    for num in nums2:
        while stack and stack[-1] < num:
            next_greater[stack.pop()] = num
        stack.append(num)

    # 스택에 남은 원소들은 다음 큰 원소 없음
    while stack:
        next_greater[stack.pop()] = -1

    return [next_greater[n] for n in nums1]

Largest Rectangle in Histogram (LeetCode 84)

def largestRectangleArea(heights: list) -> int:
    stack = []  # 단조 증가 스택 (인덱스)
    max_area = 0
    heights = heights + [0]  # 마지막에 0을 추가해 스택 비우기

    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)

    return max_area

Trapping Rain Water - Stack 방식 (LeetCode 42)

def trap(height: list) -> int:
    stack = []  # 단조 감소 스택
    water = 0

    for i, h in enumerate(height):
        while stack and height[stack[-1]] < h:
            bottom = stack.pop()
            if not stack:
                break
            bounded_height = min(height[stack[-1]], h) - height[bottom]
            width = i - stack[-1] - 1
            water += bounded_height * width
        stack.append(i)

    return water

4. Trie (Prefix Tree) 패턴

Trie 구현

class TrieNode:
    def __init__(self):
        self.children = {}  # 또는 [None] * 26
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

Design Add and Search Words (LeetCode 211)

class WordDictionary:
    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word: str) -> bool:
        def dfs(node, i):
            if i == len(word):
                return node.is_end
            char = word[i]
            if char == '.':
                # 와일드카드: 모든 자식 탐색
                for child in node.children.values():
                    if dfs(child, i + 1):
                        return True
                return False
            if char not in node.children:
                return False
            return dfs(node.children[char], i + 1)

        return dfs(self.root, 0)

Word Search II (LeetCode 212)

def findWords(board: list, words: list) -> list:
    # Trie 구성
    root = TrieNode()
    for word in words:
        node = root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    rows, cols = len(board), len(board[0])
    result = set()

    def dfs(r, c, node, path):
        if node.is_end:
            result.add(path)
            # 찾은 후에도 계속 탐색 (더 긴 단어 가능)

        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        char = board[r][c]
        if char not in node.children or char == '#':
            return

        board[r][c] = '#'  # 방문 표시
        for dr, dc in [(0,1), (0,-1), (1,0), (-1,0)]:
            dfs(r+dr, c+dc, node.children[char], path+char)
        board[r][c] = char  # 복원

    for r in range(rows):
        for c in range(cols):
            dfs(r, c, root, '')

    return list(result)

5. Bit Manipulation 패턴

XOR 트릭과 비트 연산 기초

# 기본 비트 연산
a = 0b1010  # 10
b = 0b1100  # 12

print(a & b)    # AND: 0b1000 = 8
print(a | b)    # OR:  0b1110 = 14
print(a ^ b)    # XOR: 0b0110 = 6
print(~a)       # NOT: -11 (2의 보수)
print(a << 1)   # 왼쪽 시프트: 0b10100 = 20
print(a >> 1)   # 오른쪽 시프트: 0b0101 = 5

# 유용한 비트 연산 트릭
n = 12
print(n & (n-1))    # 최하위 비트 제거: 8
print(n & (-n))     # 최하위 세트 비트만 남기기: 4
print(n ^ n)        # 자기 자신과 XOR = 0
print(0 ^ n)        # 0과 XOR = n

Single Number (LeetCode 136)

def singleNumber(nums: list) -> int:
    # 모든 숫자를 XOR: 짝수 번 나타나는 숫자는 상쇄됨
    result = 0
    for num in nums:
        result ^= num
    return result

Counting Bits (LeetCode 338)

def countBits(n: int) -> list:
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        # i의 1 비트 수 = (i >> 1)의 1 비트 수 + 최하위 비트
        dp[i] = dp[i >> 1] + (i & 1)
    return dp

Reverse Bits (LeetCode 190)

def reverseBits(n: int) -> int:
    result = 0
    for _ in range(32):
        result = (result << 1) | (n & 1)
        n >>= 1
    return result

Number of 1 Bits (LeetCode 191) - Hamming Weight

def hammingWeight(n: int) -> int:
    count = 0
    while n:
        n &= (n - 1)  # 최하위 1 비트 제거
        count += 1
    return count

# 또는 Python 내장 함수
def hammingWeight_v2(n: int) -> int:
    return bin(n).count('1')

6. 인터뷰 실전 전략

막혔을 때 힌트 요청하는 법

막혔을 때 아무 말도 안 하는 것이 가장 나쁩니다. 다음과 같이 대화하세요:

"현재 이 접근법에서 [구체적인 문제]가 발생하고 있습니다.
제가 놓치고 있는 부분이 있을까요?"

"[특정 자료구조/알고리즘]을 사용해 볼 생각인데,
올바른 방향으로 가고 있나요?"

히든 규칙: 면접관이 힌트를 주더라도 그것을 어떻게 활용하는지가 중요합니다.

코드 최적화 대화법

면접에서 최적화를 요청받으면:

"현재 솔루션은 O(n^2) 시간과 O(n) 공간을 사용합니다.
[특정 자료구조/알고리즘]을 사용하면 O(n log n)으로 개선할 수 있을 것 같습니다.
구현해 봐도 될까요?"

시간/공간 복잡도 설명 방법

항상 분석 근거를 함께 설명하세요:

"시간 복잡도는 O(n log n)입니다.
외부 루프가 n번 실행되고, 각 반복에서 힙 연산이 O(log n)이기 때문입니다.

공간 복잡도는 O(k)입니다.
크기 k의 힙을 유지하기 때문입니다."

인터뷰 진행 프레임워크

1. 문제 이해 (5분)
   - 예제 직접 만들어 확인
   - 엣지 케이스 질문

2. 접근법 설명 (5분)
   - 브루트 포스 먼저
   - 최적화 방향 설명

3. 코딩 (15-20분)
   - 말하면서 코딩
   - 변수명 의미 있게

4. 테스트 (5분)
   - 직접 만든 예제로 추적
   - 엣지 케이스 확인

7. 연습 문제 퀴즈

퀴즈 1: Subsets II에서 중복을 제거하기 위해 "i > start" 조건이 필요한 이유는?

정답: 같은 레벨(depth)에서만 중복을 건너뛰어야 하기 때문입니다.

설명: "i > 0" 조건이면 이전 재귀 호출에서 이미 사용된 원소를 자식 노드에서도 건너뛰어버려 유효한 조합이 누락됩니다. "i > start" 조건은 현재 재귀 호출의 시작 인덱스 이후에만 중복을 건너뛰므로, 같은 레벨에서 같은 값이 두 번 선택되는 경우만 제거합니다.

퀴즈 2: Find Median from Data Stream에서 두 힙을 사용하는 이유는?

정답: 중앙값을 O(1)에 조회하고 삽입을 O(log n)에 처리하기 위해서입니다.

설명: 정렬된 배열을 유지하면 삽입이 O(n), 정렬만 하면 조회가 O(n)입니다. 두 힙(하위 절반의 최대 힙 + 상위 절반의 최소 힙)을 균형 있게 유지하면 중앙값은 두 힙의 top을 보면 되므로 O(1), 삽입은 힙 연산이므로 O(log n)이 됩니다.

퀴즈 3: Largest Rectangle in Histogram에서 heights 배열 끝에 0을 추가하는 이유는?

정답: 루프 종료 후 스택에 남은 원소들을 모두 처리하기 위해서입니다.

설명: 마지막에 0을 추가하면 모든 이전 높이보다 작으므로 스택의 모든 원소가 pop됩니다. 이를 통해 루프 후 별도의 처리 없이 스택을 비울 수 있습니다. 같은 효과를 위해 별도의 후처리 루프를 사용해도 됩니다.

퀴즈 4: Single Number에서 XOR을 사용하는 수학적 원리는?

정답: XOR의 두 가지 핵심 성질: a XOR a = 0 (같은 수 두 번 XOR = 0), a XOR 0 = a (0과 XOR = 자기 자신)

설명: 배열에서 두 번씩 나타나는 숫자들을 모두 XOR하면 0이 됩니다. 한 번만 나타나는 숫자를 XOR하면 그 숫자가 남습니다. XOR은 교환법칙과 결합법칙이 성립하므로, 순서에 관계없이 동일한 결과가 나옵니다.

퀴즈 5: Word Search II에서 Trie를 사용하는 이유는?

정답: 여러 단어를 동시에 탐색하고 공통 접두사를 공유함으로써 효율을 높이기 위해서입니다.

설명: 각 단어를 개별적으로 DFS로 탐색하면 O(words _ board_cells _ 4^word_length)의 복잡도가 됩니다. Trie를 사용하면 공통 접두사를 가진 단어들의 탐색을 공유할 수 있으며, 현재 경로가 어떤 단어의 접두사도 되지 않을 때 즉시 가지치기가 가능합니다.

마무리

복잡도 요약:

패턴	시간	공간
Backtracking Subsets	O(n * 2^n)	O(n)
Backtracking Permutations	O(n * n!)	O(n)
Heap - K번째 원소	O(n log k)	O(k)
Merge K Lists	O(N log k)	O(k)
Monotonic Stack	O(n)	O(n)
Trie Insert/Search	O(L)	O(ALPHABET _ N _ L)
Bit XOR trick	O(n)	O(1)

인터뷰 준비 로드맵:

Backtracking: Subsets → Permutations → Combination Sum → N-Queens
Heap: Kth Largest → Top K → Merge K Lists → Median Finder
Monotonic Stack: Daily Temperatures → Largest Rectangle
Trie: Implement → Word Search II
Bit: Single Number → Counting Bits → Power of Two