알고리즘 문제 접근법 — 막혀도 풀어나가는 사고 프레임

문제 풀이 5단계 프레임

면접관은 코드 결과보다 사고 과정을 봅니다. 이 5단계를 소리 내어 말하면서 진행하면 막히는 구간에서도 좋은 인상을 줄 수 있습니다.

Step 1. 문제 이해 (2~3분)
- 입력/출력 형태 파악
- 제약 조건 확인 (n의 최대값, 음수 여부, 중복 여부)
- 예시 입력으로 직접 손으로 계산해보기
- "제가 제대로 이해한 게 맞나요?" 확인 질문

Step 2. 접근법 도출 (3~5분)
- 가장 단순한 방법(Brute Force) 먼저 생각
- 시간복잡도 계산: n=10^5이면 O(n log n) 이하 필요
- 패턴 인식: 이 문제가 어떤 유형인가?

Step 3. 설계 / 의사 코드 (2~3분)
- 코드 작성 전 주요 변수, 로직 흐름 설명
- "이렇게 접근하려고 하는데 어떻게 생각하세요?"

Step 4. 코드 작성 (15~20분)
- 깔끔하게 변수명 작성, 주석 최소화
- 동작하는 코드 먼저 완성 후 개선

Step 5. 검증 / 최적화 (5분)
- 예시 입력으로 디버깅
- 엣지 케이스 확인 (빈 배열, 단일 원소, 최댓값)
- "더 최적화할 수 있을 것 같습니다" 언급

시간복잡도별 n 크기 가이드

n 크기	허용 복잡도	대표 알고리즘
n <= 20	O(2^n), O(n!)	완전 탐색, 순열
n <= 500	O(n^3)	플로이드-워셜
n <= 5,000	O(n^2)	버블/선택 정렬, DP 일부
n <= 100,000	O(n log n)	병합 정렬, 힙, 이분 탐색
n <= 1,000,000	O(n)	투 포인터, 슬라이딩 윈도우, 해시
n > 10^8	O(log n), O(1)	이분 탐색, 수학 공식

코딩 테스트에서 시간 초과가 나면 복잡도를 한 단계 낮출 방법을 찾으세요. O(n^2)이면 해시맵, 투 포인터, 이분 탐색으로 O(n) 또는 O(n log n)으로 줄일 수 있는지 확인합니다.

패턴 1 — 투 포인터(Two Pointers)

언제 쓰나:
정렬된 배열에서 두 원소의 합/조건 탐색
O(n^2) Brute Force를 O(n)으로 줄일 때

예제: "정렬된 배열에서 합이 target인 두 수 찾기"

Brute Force O(n^2):
for i in range(n):
  for j in range(i+1, n):
    if arr[i] + arr[j] == target: return [i, j]

투 포인터 O(n):
left, right = 0, len(arr) - 1
while left < right:
  s = arr[left] + arr[right]
  if s == target: return [left, right]
  elif s < target: left += 1
  else: right -= 1

핵심 아이디어:
합이 target보다 작으면 left를 오른쪽으로 (값 증가)
합이 target보다 크면 right를 왼쪽으로 (값 감소)

패턴 2 — 슬라이딩 윈도우(Sliding Window)

언제 쓰나:
연속된 부분 배열/문자열에서 최대/최소/조건 탐색
O(n^2)을 O(n)으로 줄일 때

예제: "길이 k인 연속 부분 배열의 최대 합"

Brute Force O(n*k):
max_sum = 0
for i in range(n - k + 1):
  max_sum = max(max_sum, sum(arr[i:i+k]))

슬라이딩 윈도우 O(n):
window_sum = sum(arr[:k])
max_sum = window_sum
for i in range(k, n):
  window_sum += arr[i] - arr[i - k]  # 오른쪽 추가, 왼쪽 제거
  max_sum = max(max_sum, window_sum)

핵심 아이디어:
매번 새로 계산하지 않고 이전 합에서 +/-만 처리

패턴 3 — 이분 탐색(Binary Search)

언제 쓰나:
정렬된 배열에서 값 탐색
단조 증가/감소 함수에서 경계값 탐색

기본 구현:
def binary_search(arr, target):
  left, right = 0, len(arr) - 1
  while left <= right:
    mid = (left + right) // 2
    if arr[mid] == target: return mid
    elif arr[mid] < target: left = mid + 1
    else: right = mid - 1
  return -1

응용 — 매개변수 탐색:
"최소 시간으로 n개 만들기" 유형
조건(x)이 단조 증가 함수이면 이분 탐색으로 경계 탐색
left = 최솟값, right = 최댓값
while left < right:
  mid = (left + right) // 2
  if can_do(mid): right = mid
  else: left = mid + 1

패턴 4 — 해시맵 활용

언제 쓰나:
빈도 카운트, 중복 탐지, O(1) 검색이 필요할 때

예제: "배열에서 합이 k인 쌍의 수"

O(n^2) Brute Force:
count = 0
for i in range(n):
  for j in range(i+1, n):
    if arr[i] + arr[j] == k: count += 1

O(n) 해시맵:
seen = {}
count = 0
for num in arr:
  complement = k - num
  if complement in seen:
    count += seen[complement]
  seen[num] = seen.get(num, 0) + 1

패턴 5 — DFS/BFS 선택 기준

BFS 사용:
- 최단 경로 (가중치 없는 그래프)
- 레벨 단위 탐색 (트리 레벨 순회)
- 미로 최단 거리

DFS 사용:
- 경로 탐색 (모든 경로 나열)
- 사이클 감지
- 연결 요소 카운트
- 위상 정렬

BFS 구현 (큐 사용):
from collections import deque
q = deque([start])
visited = {start}
while q:
  node = q.popleft()
  for next_node in graph[node]:
    if next_node not in visited:
      visited.add(next_node)
      q.append(next_node)

패턴 6 — 동적 프로그래밍(DP) 입문

언제 쓰나:
같은 부분 문제가 반복되는 최적화 문제

판별 조건:
1. 최적 부분 구조: 전체 최적 = 부분 최적의 조합
2. 겹치는 부분 문제: 같은 계산 반복

피보나치로 이해하는 DP:
재귀(지수 시간): fib(n) = fib(n-1) + fib(n-2)

메모이제이션 O(n):
memo = {}
def fib(n):
  if n in memo: return memo[n]
  if n <= 1: return n
  memo[n] = fib(n-1) + fib(n-2)
  return memo[n]

바텀업 DP O(n), O(1):
dp = [0] * (n+1)
dp[1] = 1
for i in range(2, n+1):
  dp[i] = dp[i-1] + dp[i-2]

관련 검색어  ·  알고리즘 면접, 투 포인터, 슬라이딩 윈도우, 이분 탐색, 동적 프로그래밍, BFS DFS, 코딩 테스트 패턴