코딩 테스트 완벽 대비 가이드 | 알고리즘부터 실전 팁까지
이 글의 핵심
코딩 테스트 완벽 대비 가이드입니다. 필수 알고리즘, 문제 풀이 전략, 실전 팁을 상세히 설명합니다.
들어가며: 코딩 테스트는 준비가 전부
”알고리즘을 몰라서 떨어졌어요”
코딩 테스트는 패턴 인식입니다. 자주 나오는 패턴을 익히고, 반복 연습하면 누구나 통과할 수 있습니다.
이 글에서 다루는 것:
- 필수 알고리즘 및 자료구조
- 문제 풀이 패턴
- 시간 관리 전략
- 언어 선택 가이드
- 실전 팁
목차
1. 필수 알고리즘
우선순위별 학습 순서
graph TB
A[코딩 테스트 알고리즘] --> B[1단계: 필수]
A --> C[2단계: 중요]
A --> D[3단계: 고급]
B --> B1[투 포인터]
B --> B2[슬라이딩 윈도우]
B --> B3[이진 탐색]
B --> B4[BFS/DFS]
C --> C1[동적 프로그래밍]
C --> C2[그리디]
C --> C3[백트래킹]
D --> D1[최단 경로]
D --> D2[위상 정렬]
D --> D3[트라이]
1단계: 필수 알고리즘 (출제 빈도 높음)
투 포인터 (Two Pointers):
# 예제: 정렬된 배열에서 두 수의 합
def two_sum(arr, target):
left, right = 0, len(arr) - 1
while left < right:
current_sum = arr[left] + arr[right]
if current_sum == target:
return [left, right]
elif current_sum < target:
left += 1
else:
right -= 1
return None
# 시간복잡도: O(n)슬라이딩 윈도우 (Sliding Window):
# 예제: 길이 k인 부분 배열의 최대 합
def max_sum_subarray(arr, k):
window_sum = sum(arr[:k])
max_sum = window_sum
for i in range(k, len(arr)):
window_sum += arr[i] - arr[i - k]
max_sum = max(max_sum, window_sum)
return max_sum
# 시간복잡도: O(n)이진 탐색 (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
# 시간복잡도: O(log n)BFS/DFS (너비/깊이 우선 탐색):
from collections import deque
# BFS
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft()
print(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# DFS (재귀)
def dfs(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
print(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(graph, neighbor, visited)2단계: 중요 알고리즘
동적 프로그래밍 (DP):
# 예제: 피보나치 수열
def fibonacci(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
# 시간복잡도: O(n)
# 공간복잡도: O(n)그리디 (Greedy):
# 예제: 동전 거스름돈
def coin_change(coins, amount):
coins.sort(reverse=True)
count = 0
for coin in coins:
if amount >= coin:
count += amount // coin
amount %= coin
return count if amount == 0 else -12. 필수 자료구조
우선순위별 학습
| 우선순위 | 자료구조 | 출제 빈도 | 난이도 |
|---|---|---|---|
| 1 | 배열 (Array) | 매우 높음 | 쉬움 |
| 2 | 해시맵 (HashMap) | 매우 높음 | 쉬움 |
| 3 | 스택 (Stack) | 높음 | 쉬움 |
| 4 | 큐 (Queue) | 높음 | 쉬움 |
| 5 | 힙 (Heap) | 중간 | 중간 |
| 6 | 트리 (Tree) | 중간 | 중간 |
| 7 | 그래프 (Graph) | 중간 | 어려움 |
자료구조별 핵심 연산
배열:
# 필수 연산
arr = [1, 2, 3, 4, 5]
arr.append(6) # 뒤에 추가 O(1)
arr.pop() # 뒤에서 제거 O(1)
arr.insert(0, 0) # 앞에 추가 O(n)
arr.remove(3) # 값 제거 O(n)
arr.sort() # 정렬 O(n log n)해시맵:
# 필수 연산
d = {}
d['key'] = 'value' # 삽입 O(1)
val = d.get('key') # 조회 O(1)
del d['key'] # 삭제 O(1)
'key' in d # 존재 확인 O(1)스택:
# 스택 (LIFO)
stack = []
stack.append(1) # push
stack.append(2)
top = stack.pop() # pop (2)큐:
from collections import deque
# 큐 (FIFO)
queue = deque()
queue.append(1) # enqueue
queue.append(2)
front = queue.popleft() # dequeue (1)힙:
import heapq
# 최소 힙
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
min_val = heapq.heappop(heap) # 1
# 최대 힙 (음수 사용)
max_heap = []
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -1)
max_val = -heapq.heappop(max_heap) # 33. 문제 풀이 패턴
패턴 인식 플로우차트
flowchart TD
A[문제 읽기] --> B{정렬된 배열?}
B -->|예| C[이진 탐색 or 투 포인터]
B -->|아니오| D{부분 배열/부분 문자열?}
D -->|예| E[슬라이딩 윈도우]
D -->|아니오| F{그래프/트리?}
F -->|예| G[BFS/DFS]
F -->|아니오| H{최적화 문제?}
H -->|예| I[DP or 그리디]
H -->|아니오| J[해시맵 or 스택/큐]
패턴별 예제
패턴 1: 투 포인터
# LeetCode 15. 3Sum
def three_sum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]:
continue
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total == 0:
result.append([nums[i], nums[left], nums[right]])
left += 1
right -= 1
while left < right and nums[left] == nums[left-1]:
left += 1
elif total < 0:
left += 1
else:
right -= 1
return result패턴 2: 슬라이딩 윈도우
# LeetCode 3. Longest Substring Without Repeating Characters
def length_of_longest_substring(s):
char_set = set()
left = 0
max_length = 0
for right in range(len(s)):
while s[right] in char_set:
char_set.remove(s[left])
left += 1
char_set.add(s[right])
max_length = max(max_length, right - left + 1)
return max_length패턴 3: BFS
# LeetCode 102. Binary Tree Level Order Traversal
from collections import deque
def level_order(root):
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 result4. 시간 관리
시험 시간 배분 (2시간, 4문제 기준)
총 시간: 120분
문제 1 (Easy): 20분
문제 2 (Medium): 30분
문제 3 (Medium): 35분
문제 4 (Hard): 35분
예비 시간: 10분 (검토 및 디버깅)문제 풀이 프로세스
flowchart LR
A[문제 읽기 3분] --> B[예제 분석 2분]
B --> C[접근법 설계 5분]
C --> D[코드 작성 15분]
D --> E[테스트 3분]
E --> F[디버깅 2분]
각 단계별 체크리스트:
1. 문제 읽기 (3분):
- 입력 형식 확인
- 출력 형식 확인
- 제약 조건 확인 (n의 범위, 시간 제한)
- 엣지 케이스 파악
2. 예제 분석 (2분):
- 예제 입력/출력 손으로 따라가기
- 패턴 인식
- 예외 케이스 생각
3. 접근법 설계 (5분):
- 브루트포스 시간복잡도 계산
- 최적화 방법 고민
- 자료구조 선택
- 슈도코드 작성
4. 코드 작성 (15분):
- 함수 시그니처 작성
- 핵심 로직 구현
- 엣지 케이스 처리
5. 테스트 (3분):
- 예제 입력으로 테스트
- 엣지 케이스 테스트 (빈 배열, 크기 1, 최대 크기)
- 출력 형식 확인
6. 디버깅 (2분):
- 에러 메시지 확인
- print 디버깅
- 논리 오류 수정
5. 언어 선택
언어별 장단점
| 언어 | 장점 | 단점 | 추천 대상 |
|---|---|---|---|
| Python | 간결한 문법, 빠른 구현 | 느린 속도 (TLE 가능) | 대부분의 경우 |
| C++ | 빠른 속도, STL | 긴 코드, 디버깅 어려움 | 성능 중요 문제 |
| Java | 안정적, 풍부한 API | 장황한 문법 | 엔터프라이즈 배경 |
| JavaScript | 웹 개발자 친숙 | 타입 안전성 부족 | 웹 개발자 |
Python 추천 이유
1. 간결한 문법:
# Python (5줄)
def reverse_string(s):
return s[::-1]
# C++ (10줄)
#include <string>
#include <algorithm>
string reverseString(string s) {
reverse(s.begin(), s.end());
return s;
}2. 풍부한 내장 함수:
# 정렬
arr.sort()
# 최대/최소
max_val = max(arr)
min_val = min(arr)
# 합계
total = sum(arr)
# 카운트
from collections import Counter
count = Counter(arr)3. 슬라이싱:
arr = [1, 2, 3, 4, 5]
arr[1:4] # [2, 3, 4]
arr[::-1] # [5, 4, 3, 2, 1] (역순)
arr[::2] # [1, 3, 5] (2칸씩)C++ 사용 시기
TLE (Time Limit Exceeded) 발생 시:
문제 제약: n ≤ 10^6, 시간 제한 1초
Python: 10^6 연산 → 1초 (아슬아슬)
C++: 10^6 연산 → 0.1초 (여유)
→ Python으로 풀다가 TLE 나면 C++로 전환6. 실전 팁
팁 1: 템플릿 준비
Python 템플릿:
# 입력 처리
n = int(input())
arr = list(map(int, input().split()))
# 또는
import sys
input = sys.stdin.readline
# 출력
print(result)C++ 템플릿:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
// 로직
cout << result << endl;
return 0;
}팁 2: 시간복잡도 체크
n의 범위로 시간복잡도 추정:
n ≤ 10: O(n!) 가능
n ≤ 20: O(2^n) 가능
n ≤ 100: O(n³) 가능
n ≤ 1,000: O(n²) 가능
n ≤ 10,000: O(n² / 2) 가능
n ≤ 100,000: O(n log n) 필요
n ≤ 1,000,000: O(n) 필요
n > 1,000,000: O(log n) 또는 O(1) 필요팁 3: 디버깅 전략
# print 디버깅
def solve(arr):
print(f"DEBUG: arr = {arr}") # 입력 확인
result = []
for i in range(len(arr)):
print(f"DEBUG: i = {i}, arr[i] = {arr[i]}") # 중간 과정
result.append(arr[i] * 2)
print(f"DEBUG: result = {result}") # 출력 확인
return result팁 4: 엣지 케이스 체크
# 항상 테스트해야 할 케이스
test_cases = [
[], # 빈 배열
[1], # 크기 1
[1, 1, 1], # 모두 같은 값
[1, 2, 3], # 정렬된 배열
[3, 2, 1], # 역순
[-1, 0, 1], # 음수 포함
[10**9], # 최대값
]7. 정리
3개월 학습 플랜
1개월차: 기초 다지기
- 배열, 해시맵, 스택, 큐
- 투 포인터, 슬라이딩 윈도우
- LeetCode Easy 50문제
2개월차: 중급 알고리즘
- BFS/DFS, 이진 탐색
- 동적 프로그래밍 기초
- LeetCode Medium 50문제
3개월차: 고급 알고리즘
- 동적 프로그래밍 고급
- 그래프 알고리즘
- LeetCode Medium 50문제 + Hard 20문제
학습 자료
온라인 저지:
추천 문제집:
- LeetCode Top 100 Liked
- LeetCode Blind 75
- 백준 단계별로 풀어보기
다음 단계
알고리즘별 자세한 설명은 아래 시리즈를 참고하세요:
- 알고리즘 시리즈 #1: 배열과 리스트
- 알고리즘 시리즈 #10: BFS/DFS
- 알고리즘 시리즈 #12: 동적 프로그래밍
관련 주제:
- 시간복잡도 최적화 체크리스트
- 투 포인터 패턴
- 슬라이딩 윈도우 패턴