Ch.12 모의 면접 & 종합 전략
모의면접 3 — Hard 2문제 실전
Hard 문제가 나오면 포기해야 할까?
Hard 문제를 완벽하게 풀지 못해도 접근 과정을 보여주면 합격할 수 있습니다. 면접관은 사고의 깊이를 봅니다.
Hard는 어떻게 분해하면 풀 수 있을까?
Hard = 핵심 자료구조의 특수 성질 활용. Deque, Trie 같은 도구의 본질을 알면 됩니다.
핵심 개념
Sliding Window Maximum
크기 k인 슬라이딩 윈도우에서 각 위치의 최댓값을 구하는 문제
Monotonic Deque
항상 감소하는 순서를 유지하는 덱 — O(1)에 최댓값 조회
핵심 내용
Hard 모의면접을 시작합니다. 침착하게 분해부터 하세요
Sliding Window Maximum 정수 배열 `nums`와 윈도우 크기 `k`가 주어집니다. 크기 k인 윈도우를 한 칸씩 이동하며 각 위치의 최댓값을 구하세요. 예시: nums = [1,3,-1,-3,5,3,6,7], k = 3 → [3,3,5,5,6,7]
브루트포스: 매 윈도우마다 max → O(n·k) 최적화: Monotonic Deque → O(n)
핵심 아이디어: 덱에 감소 순서만 유지하면 맨 앞이 항상 최댓값!
Monotonic Deque로 O(n) 풀이를 구현합니다
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # 인덱스 저장 (값은 감소 순서)
result = []
for i in range(len(nums)):
# 1. 윈도우 밖으로 나간 원소 제거
if dq and dq[0] < i - k + 1:
dq.popleft()
# 2. 현재 값보다 작은 원소 모두 제거 (감소 순서 유지)
while dq and nums[dq[-1]] < nums[i]:
dq.pop()
dq.append(i)
# 3. 윈도우가 완성되면 최댓값 추가
if i >= k - 1:
result.append(nums[dq[0]])
return result시간 O(n) — 각 원소가 덱에 한 번 들어가고 한 번 나옴. 공간 O(k)
두 번째 Hard 문제입니다. Trie + DFS 결합입니다
Word Search II m×n 보드와 단어 목록 `words`가 주어집니다. 보드에서 상하좌우로 연결하여 만들 수 있는 단어를 모두 찾으세요. 예시: board = [['o','a','a','n'], ['e','t','a','e'], ['i','h','k','r']] words = ['oath','pea','eat','rain'] → ['oath','eat']
브루트포스: 각 단어마다 DFS → O(w·m·n·4^L) 최적화: Trie에 모든 단어 삽입 → 한 번 탐색으로 모든 단어 찾기
Trie가 접두사 공유를 처리하므로 중복 탐색이 제거됩니다
Trie 구축 → DFS로 보드를 탐색합니다
class TrieNode:
def __init__(self):
self.children = {}
self.word = None # 단어 끝이면 해당 단어 저장
def find_words(board, words):
# 1. Trie 구축
root = TrieNode()
for word in words:
node = root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.word = word
rows, cols = len(board), len(board[0])
result = []
# 2. DFS 탐색
def dfs(r, c, node):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
ch = board[r][c]
if ch == '#' or ch not in node.children:
return
next_node = node.children[ch]
if next_node.word: # 단어 발견!
result.append(next_node.word)
next_node.word = None # 중복 방지
board[r][c] = '#' # 방문 표시
for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
dfs(r + dr, c + dc, next_node)
board[r][c] = ch # 복원
for r in range(rows):
for c in range(cols):
dfs(r, c, root)
return result핵심 포인트: • Trie로 접두사 공유 → 중복 탐색 제거 • 보드 셀 '#' 마킹 → 재방문 방지 • word 발견 시 None 처리 → 중복 결과 방지
면접에서 Hard를 완벽히 못 풀어도 이 접근 과정을 설명하면 높은 점수를 받습니다
Hard 문제를 만났을 때의 마인드셋이 중요합니다
Hard 문제 생존 전략: 1. 포기하지 마세요 — 접근 과정도 평가 대상 2. 브루트포스부터 — 일단 동작하는 풀이 제시 3. 병목 파악 — 어디가 느린지 분석 4. 자료구조 교체 — 그 병목을 해결할 자료구조 찾기 5. 부분 구현도 OK — 설계만 완벽해도 합격 가능
Hard를 30분 만에 완벽히 풀 필요 없습니다. 사고 과정의 품질이 합격을 결정합니다
Sliding Window Maximum에서 Monotonic Deque를 사용하는 이유는?
Word Search II에서 Trie를 사용하면 각 단어마다 따로 DFS를 할 필요가 없다
Hard 도전 완료!
정리 노트
모의면접 3 — Hard 실전
문제별 핵심
- Sliding Window Max
- Monotonic Deque — 감소 순서 유지, O(n)
- Word Search II
- Trie + DFS — 접두사 공유로 중복 탐색 제거
Hard 생존 전략
- 첫 단계
- 브루트포스 먼저 제시
- 핵심
- 병목 파악 → 자료구조 교체
- 마인드셋
- 사고 과정의 품질이 합격을 결정
Hard가 나와도 당황하지 마세요. 브루트포스→최적화 과정을 보여주는 것이 핵심!
핵심 정리
- 1Sliding Window Maximum — Monotonic Deque
- 2Word Search II — Trie + DFS 결합
- 3Hard = 핵심 자료구조의 특수 성질 활용
- 4완벽한 풀이보다 사고 과정이 중요
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작