경쟁 프로그래밍(Competitive Programming)은 알고리즘 문제를 제한 시간과 메모리 내에 정확하게 해결하는 프로그래밍 스포츠다. 알고리즘 설계, 자료구조 활용, 수학적 사고력을 기르는 데 효과적이다.
주요 플랫폼
| 플랫폼 | 특징 | URL |
|---|
| Codeforces | 러시아 기반, 잦은 콘테스트 | codeforces.com |
| AtCoder | 일본 기반, 수학 문제 중심 | atcoder.jp |
| BOJ (백준) | 한국 최대 OJ | acmicpc.net |
| LeetCode | 취업 코딩 테스트 특화 | leetcode.com |
| USACO | 미국 올림피아드 | usaco.org |
문제 유형별 핵심 알고리즘
그래프 이론
├── BFS/DFS
├── 최단 경로 (Dijkstra, Bellman-Ford, Floyd)
├── 최소 신장 트리 (Kruskal, Prim)
└── 네트워크 플로우
동적 프로그래밍
├── 배낭 문제 계열
├── 구간 DP
├── 트리 DP
└── 비트마스크 DP
문자열
├── KMP, Z-알고리즘
├── 아호-코라식
└── 접미사 배열/오토마톤
수학
├── 정수론 (소수, GCD, 모듈러)
├── 조합론
└── 선형 대수 (행렬 거듭제곱)
복잡도 빠른 참조
입력 크기 n에 따른 허용 복잡도 (1초 기준):
n ≤ 10 → O(n!) 팩토리얼 가능
n ≤ 20 → O(2^n) 비트마스크 DP
n ≤ 500 → O(n³) 삼중 루프
n ≤ 5,000 → O(n²) 이중 루프
n ≤ 100,000 → O(n log n) 정렬, 세그트리
n ≤ 1,000,000 → O(n) 선형
입출력 최적화
python
import sys
input = sys.stdin.readline # 빠른 입력
# PyPy 사용 시 일반 Python보다 3~5배 빠름
# C++ 기준 I/O 최적화:
# ios_base::sync_with_stdio(false);
# cin.tie(NULL);
디버깅 전략
python
# 스트레스 테스트: 무작위 입력으로 정답 코드와 비교
import random
def brute_force(arr):
return sorted(arr)
def my_solution(arr):
return sorted(arr) # 실제 솔루션으로 교체
for _ in range(1000):
arr = [random.randint(1, 100) for _ in range(random.randint(1, 20))]
if brute_force(arr) != my_solution(arr):
print("틀림!", arr)
break
관련 개념
