알고리즘 종류 및 공부 순서 정리
알고리즘은 문제 해결을 위한 논리적인 절차입니다.
효율적인 문제 해결을 위해 다양한 알고리즘 기법이 존재하며, 학습 순서에 따라 구조적으로 접근하는 것이 중요합니다.
1️⃣ 기초 개념 및 자료구조 (입문 필수)
| 주제 | 설명 |
|---|---|
| 시간/공간 복잡도 | Big-O 표기법, 성능 분석 기본 |
| 배열(Array), 문자열(String) | 가장 기본적인 자료 구조 |
| 스택(Stack), 큐(Queue) | 선입선출(FIFO), 후입선출(LIFO) |
| 해시(Hash Table) | 빠른 검색 및 중복 제거 |
| 연결 리스트(Linked List) | 동적 메모리 관리 이해 |
| 트리(Tree), 그래프(Graph) 기초 | 자료구조 이해의 확장 |
2️⃣ 기본 알고리즘 패턴 (코테 기본기)
| 유형 | 설명 및 예시 문제 유형 |
|---|---|
| 완전 탐색(Brute Force) | 가능한 모든 경우 탐색 (예: 비밀번호 조합 찾기) |
| 그리디(Greedy) | 매 순간 최적 선택 (예: 거스름돈 문제, 회의실 배정) |
| 정렬(Sorting) | 기본: 선택/삽입/버블 / 고급: 퀵, 머지, 힙 정렬 |
| 이분 탐색(Binary Search) | 정렬된 배열에서 탐색 (예: 특정 값 존재 여부) |
| 투 포인터(Two Pointer) | 연속 구간 탐색 (예: 부분합, 정렬된 배열 쌍 찾기) |
| 슬라이딩 윈도우 | 고정 길이 윈도우로 최댓값, 평균 등 계산 |
| 해시 활용 | 중복 검사, 빈도 계산 등 (예: 전화번호 목록, 애너그램) |
3️⃣ 재귀와 탐색 알고리즘 (중급 이상)
| 주제 | 설명 |
|---|---|
| 재귀(Recursion) | 자기 자신 호출, 백트래킹의 기초 |
| 백트래킹(Backtracking) | 모든 경우의 수 탐색 + 가지치기 |
| DFS/BFS | 깊이/너비 우선 탐색 (그래프 탐색 핵심) |
| 그래프(Graph) | 인접 리스트/행렬, 방향성, 사이클 탐지 등 |
| 유니온 파인드(Disjoint Set) | 서로소 집합 알고리즘 (네트워크 연결 여부 판단 등) |
| 위상 정렬(Topology Sort) | 선후 관계가 있는 작업 정렬 (예: 선수 과목 문제) |
4️⃣ 동적 계획법 & 탐욕 알고리즘 (심화)
| 유형 | 설명 |
|---|---|
| 동적 계획법(DP) | 이전 결과 저장하여 중복 연산 제거 (피보나치, 배낭 문제) |
| 메모이제이션 vs. 탑다운/보텀업 | DP 구현 방식 |
| LIS (최장 증가 수열) | DP + 이분 탐색 병용 |
| 그리디 고급 | 최적의 해가 항상 전체 최적인가 판단 필수 |
5️⃣ 그래프 심화
| 유형 | 설명 |
|---|---|
| 최단 경로 알고리즘 | Dijkstra, Floyd-Warshall, Bellman-Ford |
| MST (최소 신장 트리) | Kruskal, Prim |
| 강한 연결 요소(SCC) | Kosaraju, Tarjan |
| 네트워크 플로우 | Ford-Fulkerson, Edmonds-Karp |
6️⃣ 기타 고급 주제
| 주제 | 설명 |
|---|---|
| 트라이(Trie) | 문자열 검색 최적화 자료구조 |
| 세그먼트 트리 | 구간 쿼리 처리 (최솟값, 합 등) |
| 비트마스킹 | 조합, 상태 저장 등에서 메모리 최적화 |
| 정규표현식, 문자열 알고리즘 | KMP, Rabin-Karp 등 |
| 확장 유클리드 호제법 | GCD, 모듈러 연산 응용 |
📌 추천 학습 순서
- 자료구조 & 기본 알고리즘 패턴
- DFS/BFS → 백트래킹 → 정렬/탐색 응용
- DP (탑다운/보텀업)
- 그래프 이론 (유니온 파인드, 위상 정렬 포함)
- 최단 경로 → MST → 네트워크 플로우
- 고급 자료구조 & 문자열 알고리즘
📝 학습 팁
- 문제 유형별로 최소 3~5문제 이상은 반복 풀이
- 쉬운 문제를 여러 번 → 패턴 익숙해지기
- 풀이 후 반드시 다른 사람 풀이와 비교
- 가능한 경우 직접 구현보단 패턴화 연습이 핵심
꾸준히