패턴 인식 요약표
15가지 일반적인 문제 신호(정렬된 배열, 모든 조합 필요, 제약이 있는 값의 최대화 등)를 이를 가장 빠르게 해결하는 알고리즘 패턴에 연결합니다.
패턴 인식 요약표은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 1번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
60초 패턴 인식 게임
실제 면접에서는 문제를 읽은 후 대략 60초 안에 어떤 알고리즘 패턴을 적용할지 파악해야 면접관이 코딩을 시작하길 기대하는 시점에 맞출 수 있습니다. 개발해야 할 가장 중요한 능력은 구현을 암기하는 것이 아니라 어떤 도구를 사용해야 할지 알아보는 것입니다.
패턴 인식은 문제 설명의 문제 신호(문제에 사용된 단어와 제약 조건)를 이미 알고 있는 알고리즘 계열에 대응시키는 데서 나옵니다. 패턴을 파악하면 구현은 템플릿을 채우는 작업이 됩니다. 이 수업은 가장 흔한 문제 신호 15가지와 그에 대응하는 패턴을 체계적으로 정리한 요약표입니다.
# The recognition process
recognition_steps = [
'1. Read the problem once fully (do not start coding)',
'2. Identify the data structure: array, string, tree, graph, matrix?',
'3. Identify the ask: find min/max, count ways, enumerate, detect cycle...?',
'4. Note the constraint: n<=20 (bitmask), sorted (binary search), DAG (topo sort)?',
'5. Map signal -> pattern',
'6. State the pattern and complexity to the interviewer before coding',
'7. Handle edge cases mentally before writing',
]
for step in recognition_steps:
print(step)신호 1~3: 배열 및 문자열 패턴
배열과 문자열에서 가장 자주 나타나는 문제 신호는 다음과 같습니다:
- 정렬된 배열 + 목표 찾기 → 이진 탐색 O(log n)
- 합이 목표값이 되는 쌍 또는 세 원소 찾기 → 정렬되어 있으면 두 포인터 O(n), 정렬되어 있지 않으면 해시 맵 O(n)
- 조건을 만족하는 가장 긴/짧은 부분 배열/부분 문자열 → 슬라이딩 윈도 O(n)
- 연속 부분 배열의 최대/최소 합 → 카다네 알고리즘 O(n)
- 중복 탐지 → 해시 집합 O(n) 또는 sort(정렬) O(n log n)
배열이 정렬되어 있다면 항상 이진 탐색을 먼저 고려하십시오. 정렬되지 않음 + 목표 합 + O(n) = 거의 항상 여집합 조회를 위한 해시 맵입니다.
# Quick recognition: array/string signals
signals = [
('Sorted array, find element', 'Binary search O(log n)'),
('Find two elements summing to K', 'Sort+two-ptr O(n log n) or hash O(n)'),
('Longest subarray with property P', 'Sliding window (variable size) O(n)'),
('Max sum contiguous subarray', 'Kadane algorithm O(n)'),
('Anagram/permutation check', 'Frequency map (Counter) O(n)'),
('Contains duplicate', 'Hash set O(n)'),
('Merge two sorted arrays/lists', 'Two pointers O(n+m)'),
('Rotate / shift array', 'Reverse trick O(n) in-place'),
('Next permutation', 'Find rightmost ascent + swap + reverse'),
('Maximum product subarray', 'Track max and min (handles negatives)'),
]
for signal, pattern in signals:
print(f'{signal:45s} => {pattern}')신호 4~6: 트리 및 그래프 패턴
트리와 그래프 문제의 신호 및 그 패턴은 다음과 같습니다:
- 레벨별 순회 / 가중치가 없는 그래프에서의 최단 경로 → 덱을 사용하는 BFS O(V+E)
- 모든 경로 탐색 / 사이클 탐지 / DFS 순서 → 재귀 또는 반복 DFS O(V+E)
- BST + 중위 순회 속성(k번째 원소, 정렬 순서) → 중위 순회 DFS O(n)
- 최저 공통 조상 → 경로 추적을 포함한 재귀 하강 O(n)
- 연결 요소 / 두 그룹 합치기 → DSU O(n × alpha(n))
# Tree/graph signal recognition
tree_graph_signals = [
('Level-order / minimum depth / word ladder', 'BFS with deque'),
('All paths / path sum / all permutations tree', 'DFS recursive'),
('Cycle detection (undirected)', 'DFS with parent / DSU'),
('Cycle detection (directed) / course schedule', 'DFS three-color / Kahn topo sort'),
('Shortest path weighted graph', 'Dijkstra (non-neg) / Bellman-Ford (neg)'),
('All-pairs shortest path', 'Floyd-Warshall O(V^3)'),
('Topological order', 'Kahn BFS topo sort'),
('Min spanning tree', 'Kruskal (DSU) / Prim (heap)'),
('Dynamic connectivity / union-find', 'DSU path compression + union by rank'),
('Autocomplete / prefix search', 'Trie'),
('BST kth smallest / range sum', 'In-order DFS'),
]
for signal, pattern in tree_graph_signals:
print(f'{signal:50s} => {pattern}')신호 7~9: 동적 프로그래밍 신호
DP 신호는 인식하기 가장 어렵습니다. 다음과 같은 핵심 표현을 찾아보십시오:
- '...하는 방법의 수' → 경우의 수 세기 DP(하위 문제의 개수를 더함)
- '...을 달성하는 최소/최대 비용' → 최적화 DP(하위 문제의 최솟값/최댓값을 선택함)
- '...을 달성할 수 있는가?' (가능성) → 불리언 DP(하위 문제의 OR)
- 두 문자열 인덱스로 정의되는 하위 문제 → 2차원 DP(LCS, 편집 거리)
- 용량 제약 아래에서 항목을 선택하거나 건너뛰기 → 배낭 DP
- 최적 부분 구조 + 겹치는 하위 문제 → 반복 호출이 있는지 재귀 트리를 확인 → DP
# DP signal recognition
dp_signals = [
('Number of ways to climb stairs / decode string', '1D DP (Fibonacci-like)'),
('Minimum cost to reach end / coin change', '1D DP (greedy fails)'),
('Longest increasing subsequence', '1D DP O(n^2) or patience sort O(n log n)'),
('Longest common subsequence of two strings', '2D DP O(mn)'),
('Edit distance between two strings', '2D DP O(mn) (LCS variant)'),
('Partition array into two equal subsets', '0/1 knapsack boolean DP'),
('Fill knapsack with max value under weight limit', '0/1 knapsack optimisation DP'),
('Burst balloons / matrix chain multiplication', 'Interval DP'),
('Palindrome partitioning minimum cuts', 'Interval DP + prefix palindrome'),
('Rob houses in circle', '1D DP × 2 (linear sub-problems)'),
]
for signal, pattern in dp_signals:
print(f'{signal:55s} => {pattern}')신호 10~12: 힙, 스택 및 그리디 신호
힙, 단조 스택 및 그리디 문제의 신호는 다음과 같습니다:
- 상위 K개 원소 / k번째로 큰 원소 또는 작은 원소 → 힙(상위 K개의 큰 원소에는 최소 힙, k번째로 작은 원소에는 최대 힙) O(n log k)
- 데이터 스트림의 중앙값 → 두 힙(작은 절반의 최대 힙 + 큰 절반의 최소 힙)
- 다음으로 큰/작은 원소 → 단조 스택 O(n)
- 가장 큰 직사각형 넓이 / 빗물 가두기 → 단조 스택 O(n)
- 구간 스케줄링 / 겹치지 않는 구간 최대화 → 그리디(sort로 종료 time을 기준으로 정렬)
# Heap / stack / greedy signals
heap_stack_greedy = [
('Top-K frequent elements', 'Min-heap size K: O(n log k)'),
('Kth largest in array', 'Max-heap pop K times: O(n + k log n)'),
('Streaming median', 'Two heaps (max + min): O(log n) per insert'),
('Merge K sorted lists', 'Min-heap of (val, list_idx): O(n log k)'),
('Next greater element', 'Monotonic decreasing stack: O(n)'),
('Largest rectangle in histogram', 'Monotonic increasing stack: O(n)'),
('Sliding window maximum', 'Monotonic decreasing deque: O(n)'),
('Trapping rain water', 'Two pointers OR monotonic stack: O(n)'),
('Jump game reachability / minimum jumps', 'Greedy range expansion: O(n)'),
('Merge overlapping intervals', 'Sort by start, linear scan: O(n log n)'),
('Gas station circular', 'Greedy: start from reset point: O(n)'),
('Task scheduler with cooldown', 'Greedy: sort by frequency: O(n log n)'),
]
for signal, pattern in heap_stack_greedy:
print(f'{signal:45s} => {pattern}')신호 13~15: 백트래킹 및 비트 조작
백트래킹과 비트 조작의 신호는 다음과 같습니다:
- 모든 부분집합 / 순열 / 조합 생성 → 백트래킹 O(2^n 또는 n!)
- 제약 조건 만족(N-퀸, 스도쿠) → 가지치기를 포함한 백트래킹
- 누락된 원소 하나 또는 유일한 원소 찾기 → XOR O(n), 공간 O(1)
- 작은 집합의 모든 부분집합 열거(n ≤ 20) → 비트마스크를 이용한 2^n 열거
- 집합 비트 개수 세기 / 2의 거듭제곱 확인 → 비트 트릭(n & (n-1))
- 작은 집합을 사용하는 상태 압축 DP → 비트마스크 DP O(2^n × n)
# Backtracking and bit signals
bt_bit_signals = [
('Generate all subsets of array', 'Backtracking O(n * 2^n) / bitmask'),
('Generate all permutations', 'Backtracking O(n * n!)'),
('Combination sum with target', 'Backtracking with pruning'),
('Word search in grid', 'Backtracking DFS on grid O(m*n*4^L)'),
('N-queens placement', 'Backtracking with column/diag sets'),
('Find single unique element (all others x2)', 'XOR all: O(n) O(1)'),
('Missing number in 0..n', 'XOR or sum formula: O(n) O(1)'),
('Count set bits in n', 'n &= n-1 loop or DP O(n)'),
('Check power of two', 'n > 0 and n & (n-1) == 0'),
('Travelling salesman (n<=20)', 'Bitmask DP O(2^n * n^2)'),
('Number with max XOR in array', 'Trie on binary representation'),
]
for signal, pattern in bt_bit_signals:
print(f'{signal:50s} => {pattern}')제약 조건 분석: N이 알려 주는 것
입력 크기 제약 조건인 n은 허용되는 time(시간) 복잡도를 직접 알려 주며, 따라서 사용할 알고리즘 계열도 알려 줍니다:
- n ≤ 20: O(2^n) 또는 O(n!) 허용 — 비트마스크 DP, 백트래킹
- n ≤ 500: O(n³) 허용 — 플로이드-워셜, 완전 탐색 DP
- n ≤ 5000: O(n²) 허용 — 단순 DP, 2차 sort(정렬)
- n ≤ 10^6: O(n log n) 필요 — 병합 sort(정렬), 힙, 이진 탐색
- n ≤ 10^8: O(n) 필요 — 두 포인터, 슬라이딩 윈도, 선형 DP
이 제약 조건 분석은 문제를 읽은 직후, 어떤 알고리즘을 선택하기 전에 가장 먼저 수행해야 할 단계입니다.
# Constraint -> acceptable complexity -> algorithm family
complexity_map = [
('n <= 20', 'O(2^n) or O(n!)', 'Bitmask DP, backtracking/permutations'),
('n <= 500', 'O(n^3)', 'Floyd-Warshall, cubic DP, brute force'),
('n <= 5000', 'O(n^2)', 'Quadratic DP, bubble/insertion sort'),
('n <= 100000', 'O(n log n)', 'Merge sort, heap, binary search, topo sort'),
('n <= 1000000', 'O(n)', 'Linear DP, two pointers, sliding window, hash'),
('n <= 10^8', 'O(n) tight', 'Only simplest O(n) — no large constants'),
('n <= 10^18', 'O(log n) or O(1)', 'Math / number theory, binary search on answer'),
]
print(f'{'Constraint':15s} {'Complexity':15s} {'Algorithm Family'}')
print('-'*70)
for constraint, complexity, algorithms in complexity_map:
print(f'{constraint:15s} {complexity:15s} {algorithms}')문제 → 패턴: 신속 연습
이 대응을 자동으로 할 수 있을 때까지 연습하십시오. 각 문제 설명을 읽고 풀이를 보기 전에 패턴을 파악하십시오. 속도가 중요합니다. 면접에서는 60초 안에 패턴을 파악해야 합니다:
- '정렬된 배열이 주어졌을 때, 어떤 두 원소의 합이 K인지 찾으십시오'
- '트리가 주어졌을 때, 지름(두 노드 사이의 가장 긴 경로)을 찾으십시오'
- '냉각 시간 k가 있는 n개의 작업이 주어졌을 때, 필요한 최소 CPU 구간을 찾으십시오'
- '문자열이 주어졌을 때, 가장 긴 회문 부분 문자열을 찾으십시오'
- '1..n에서 하나가 빠졌을 때, 빠진 수를 찾으십시오'
# Quick-fire pattern recognition answers
problems = [
('Sorted array: two elements sum to K',
'Two pointers (left from start, right from end): O(n)'),
('Tree diameter (longest path)',
'DFS returning (height, max_diameter) pair: O(n)'),
('Task scheduler with cooldown k',
'Greedy: (max_freq - 1)*(k+1) + count_of_max_freq: O(n log n)'),
('Longest palindromic substring',
'Expand around centre OR Manacher: O(n^2) or O(n)'),
('Missing number in 1..n',
'XOR all indices and values: O(n) O(1)'),
('Number of islands in binary grid',
'BFS/DFS flood fill counting connected components: O(m*n)'),
('Decode string like 3[a2[bc]] -> aaabcbcaabcbc',
'Stack to handle nested brackets: O(n)'),
('Valid parentheses [(){[]}]',
'Stack push open, pop+match on close: O(n)'),
]
for problem, solution in problems:
print(f'Q: {problem}\nA: {solution}\n')위험 신호: 패턴이 실패하는 경우
경험이 많은 엔지니어도 처음에는 잘못된 패턴을 선택할 수 있습니다. 현재 접근법이 잘못되었음을 알려 주는 다음 신호를 인식하고 방향을 전환하십시오:
- O(n²) 방법이 작은 테스트에서는 통과하지만 큰 입력에서는 시간 초과가 발생함 → 해시 맵, 이진 탐색 또는 단조 구조가 필요합니다
- 그리디 방법이 반례에서 실패함 → DP를 시도하십시오
- DP 상태 공간이 너무 큼 → 그리디 증명이나 더 효율적인 상태 정의를 찾아보십시오
- BFS가 잘못된 답을 반환함 → BFS(가중치가 없음) 대신 다익스트라(가중치가 있음)가 필요한지 확인하십시오
- 널 포인터 예외가 발생함 → 구현하기 전에 기저 사례와 경계 사례 검사를 추가하십시오
# Red flags and recovery strategies
red_flags = [
('TLE on large n', 'Check complexity; switch from O(n^2) to O(n log n) or O(n)'),
('WA with greedy', 'Find a counter-example; switch to DP or prove exchange arg'),
('DP table huge', 'State compression (bitmask/rolling array) or different state'),
('BFS gives wrong shortest path', 'Check if edges have weights; use Dijkstra instead'),
('Stack overflow in recursion', 'Add memoisation or convert to iterative with explicit stack'),
('Off-by-one in binary search', 'Use half-open intervals [lo, hi); verify with 2-element test'),
('DSU wrong answer', 'Check 0-indexed vs 1-indexed; check union direction'),
('Backtracking TLE', 'Add pruning conditions; ensure undo step is correct'),
]
print('Pattern | Recovery')
print('-'*70)
for flag, recovery in red_flags:
print(f'{flag:40s} => {recovery}')면접에서 패턴 인식 전달하기
면접에서 패턴을 인식한 과정을 말로 설명하면 전문성을 보여 줄 수 있고, 잘못된 방향으로 가고 있을 때 면접관이 안내할 기회도 얻을 수 있습니다. 다음과 같은 말하기 구조를 사용하십시오:
- '배열이 정렬되어 있으므로 이진 탐색을 생각하고 있습니다...'
- '문제에서 최대 부분 배열을 요구하므로 전형적인 카다네 알고리즘 문제입니다...'
- '가능한 모든 부분집합이 필요하므로 재귀 트리를 사용하는 백트래킹을 적용할 수 있습니다...'
- '제약 조건 n ≤ 20에서 2^n = 1M은 허용 가능하므로 비트마스크 DP를 사용할 수 있습니다...'
패턴을 말한 후 코드 한 줄을 작성하기 전에 time(시간) 및 공간 복잡도를 언급하십시오. 이는 구현 전에 효율성을 고려하고 있음을 보여 줍니다.
# Interview communication template
def communicate_approach(problem, pattern, time_complexity, space_complexity, edge_cases):
print(f'Problem: {problem}')
print(f'Pattern: {pattern}')
print(f'Time: {time_complexity}, Space: {space_complexity}')
print(f'Edge cases to handle: {", ".join(edge_cases)}')
print()
# Example communications
communicate_approach(
problem='Find longest substring without repeating characters',
pattern='Sliding window with a set tracking current window characters',
time_complexity='O(n)',
space_complexity='O(min(n, alphabet_size))',
edge_cases=['empty string', 'all same characters', 'all unique characters']
)
communicate_approach(
problem='Given sorted matrix, find if target exists',
pattern='Binary search or staircase search (top-right corner): eliminate row or column each step',
time_complexity='O(m + n)',
space_complexity='O(1)',
edge_cases=['empty matrix', 'single element', 'target at corners']
)패턴 인식 어휘 구축
패턴 인식 능력을 기르는 가장 빠른 방법은 무작위로 문제를 풀지 않고 주제별 묶음으로 문제를 푸는 것입니다. 일주일 동안 슬라이딩 윈도 문제만 풀어 보십시오. 그다음에는 두 포인터 문제를 풀고, 이어서 DP 문제를 푸십시오. 같은 유형의 문제 20개를 빠르게 풀면 해당 패턴을 한눈에 알아보는 직관이 크게 향상됩니다.
각 문제를 푼 뒤에는 한 줄짜리 '패턴 메모'를 작성하십시오. 문제의 신호와 그 신호가 떠올리게 한 패턴을 적으면 됩니다. 자신만의 요약표를 만드십시오. 주제별 묶음으로 200문제를 풀고 나면 면접 문제의 약 90%를 30초 안에 인식할 수 있습니다. 나머지 10%는 경험이 많은 엔지니어에게도 신중한 분석이 필요합니다.
# Personal pattern note template
pattern_notes = [
{'signal': 'sorted array + two sum', 'pattern': 'two pointers', 'example': 'LC 167 Two Sum II'},
{'signal': 'longest X without repeating', 'pattern': 'sliding window + set', 'example': 'LC 3 Longest Substring'},
{'signal': 'max sum subarray', 'pattern': 'Kadane', 'example': 'LC 53 Max Subarray'},
{'signal': 'permutations/subsets', 'pattern': 'backtracking', 'example': 'LC 46 Permutations'},
{'signal': 'tree path sum', 'pattern': 'DFS with accumulator', 'example': 'LC 112 Path Sum'},
{'signal': 'course schedule', 'pattern': 'Kahn topo sort', 'example': 'LC 207 Course Schedule'},
{'signal': 'top-K elements', 'pattern': 'min-heap size K', 'example': 'LC 215 Kth Largest'},
]
print(f'{'Signal':40s} {'Pattern':30s} {'Example'}')
print('-'*90)
for note in pattern_notes:
print(f'{note["signal"]:40s} {note["pattern"]:30s} {note["example"]}')빠른 확인
이 수업에서 다룬 자료구조 및 알고리즘 & 코딩 면접 준비 개념에 대한 이해도를 확인해 보세요.
수업 요약
이 수업에서는 패턴 인식이 문제 신호를 알고리즘 계열에 대응시킨다는 점을 배웠습니다. 정렬된 배열은 이진 탐색을, '모든 부분집합'은 백트래킹을, '최소 비용'은 DP를 의미합니다. 또한 제약 조건 n은 허용되는 복잡도를 알려 줍니다. n ≤ 20에서는 O(2^n)이 가능하고, n ≤ 10^6에서는 O(n log n) 또는 그보다 나은 복잡도가 필요합니다. 그리고 코딩 전에 패턴과 복잡도를 말로 설명하면 전문성을 보여 주고 면접관의 피드백을 받을 수 있습니다. 다음으로는 쉬운 난이도와 중간 난이도의 시간 제한 모의 면접 문제를 통해 패턴 인식을 연습합니다.
자주 묻는 질문
“패턴 인식 요약표” 강의는 무료인가요?
네 — “패턴 인식 요약표” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“패턴 인식 요약표”에서 뭘 배우나요?
15가지 일반적인 문제 신호(정렬된 배열, 모든 조합 필요, 제약이 있는 값의 최대화 등)를 이를 가장 빠르게 해결하는 알고리즘 패턴에 연결합니다. 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 1번째 강의입니다.
“패턴 인식 요약표” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.