Python을 활용한 코딩테스트 준비 저장소입니다.
문제를 많이 푸는 것에 그치지 않고, 문제 유형 분류 / 해결 방법 / 시간 복잡도 / 실수 포인트까지 함께 정리하는 것을 목표로 합니다.
이 저장소는 다음을 위한 공간입니다.
- 코딩테스트 문제 풀이 기록
- 알고리즘 유형별 정리
- 시간 복잡도 감각 익히기
- 자주 틀리는 실수 정리
- 다시 봤을 때 빠르게 복습할 수 있는 개인 알고리즘 노트 구축
- Python
각 문제는 다음 기준으로 정리합니다.
- 문제
- 해결 방법
- 핵심 아이디어
- 시간 복잡도
- 실수 포인트
- 다시 풀 때 체크할 점
코드는 별도 파일로 관리하고, 문제 설명과 풀이 아이디어는 각 문제의 README.md에 정리합니다.
문제를 보면 아래 순서대로 생각합니다.
- 입력 크기(
N)를 먼저 확인한다. - 시간 제한 내에 가능한 시간 복잡도를 추정한다.
- 완전탐색이 가능한지 먼저 판단한다.
- 더 효율적인 알고리즘이 필요한지 확인한다.
- 구현 전에 풀이 아이디어를 한 줄로 설명해본다.
- 구현 후 예외 케이스와 반례를 점검한다.
입력 크기에 따라 허용 가능한 시간 복잡도를 대략적으로 판단합니다.
| 입력 크기 | 고려할 수 있는 시간 복잡도 |
|---|---|
N <= 20 |
O(2^N), O(N!) 가능할 수 있음 |
N <= 100 |
O(N^3) 정도까지 가능 |
N <= 1,000 |
O(N^2) 가능 |
N <= 100,000 |
O(N log N) 권장 |
N <= 1,000,000 |
O(N) 권장 |
| 매우 큰 수 | O(log N) 또는 수학적 접근 필요 |
위 기준은 절대적인 값이 아니라, 문제를 처음 봤을 때 빠르게 판단하기 위한 기준입니다.
O(1): 상수 시간O(log N): 이진 탐색O(N): 순차 탐색, 한 번 순회O(N log N): 정렬, 힙O(N^2): 이중 반복문O(N^3): 삼중 반복문, 플로이드 워셜O(2^N): 부분집합, 백트래킹 일부O(N!): 순열 완전탐색
시간 복잡도만큼 공간 복잡도도 중요합니다.
예시:
- 길이
N의 리스트 사용 →O(N) N x M2차원 배열 사용 →O(NM)- 재귀 호출 사용 → 호출 깊이만큼 스택 사용
문제를 풀 때는 항상
시간 복잡도 + 공간 복잡도를 함께 확인합니다.
- 현재 최선의 선택이 전체 최적해로 이어지는가?
- 반례가 없는가?
- 조건을 빠짐없이 구현했는가?
- 인덱스, 범위, 방향 처리를 정확히 했는가?
- 그래프를 어떤 방식으로 표현할 것인가?
- 방문 처리를 올바르게 했는가?
- 정렬 기준을 무엇으로 잡아야 하는가?
- 정렬 후 어떤 판단을 빠르게 할 수 있는가?
- 정렬이 필요한가?
- 값을 찾는 문제인가, 조건의 경계를 찾는 문제인가?
- 점화식을 만들 수 있는가?
- 작은 문제의 답으로 큰 문제를 해결할 수 있는가?
- 입력 조건을 끝까지 읽지 않음
- 시간 복잡도를 계산하지 않고 바로 구현함
<=와<범위를 혼동함- 정렬 후 인덱스를 잘못 참조함
- 방문 처리를 빼먹음
- 재귀 종료 조건을 빠뜨림
- 예외 케이스를 확인하지 않음
문제를 푼 뒤 아래 내용을 짧게라도 남깁니다.
- 이 문제는 어떤 유형인가?
- 핵심 아이디어는 무엇인가?
- 왜 이 방법으로 풀 수 있는가?
- 시간 복잡도는 얼마인가?
- 어떤 부분에서 실수했는가?
- 다시 풀 때 가장 먼저 떠올려야 할 포인트는 무엇인가?