1. 정렬 (Sorting)
- 버블 정렬: 인접한 두 개를 비교하며 정렬하는 방식 (비효율적)
- 선택 정렬: 가장 작은(혹은 큰) 값을 선택해 앞으로 보내는 방식
- 삽입 정렬: 이미 정렬된 부분에 새로운 데이터를 삽입하는 방식
- 퀵 정렬: 피벗(pivot)을 기준으로 작은 값과 큰 값을 나누며 정렬
- 병합 정렬: 데이터를 반으로 쪼개 정렬한 후 합치는 방식
💡 코딩테스트에서는 보통 sorted()나 sort()를 활용하면 됨
2. 탐색 (Search)
- 선형 탐색 (Linear Search): 데이터를 하나씩 확인하는 방식 (O(N))
- 이진 탐색 (Binary Search): 정렬된 배열에서 중간값을 기준으로 찾는 방식 (O(logN))
- DFS (깊이 우선 탐색): 한 방향으로 계속 탐색하다가 더 이상 갈 곳이 없으면 되돌아옴 (스택 or 재귀)
- BFS (너비 우선 탐색): 가까운 노드부터 탐색 (큐 사용)
💡 DFS/BFS는 그래프 탐색, 최단 경로 문제에서 자주 나옴
3. 그래프 알고리즘
- 최단 경로 알고리즘
- 다익스트라 (Dijkstra): 한 지점에서 모든 지점까지 최단 거리 (우선순위 큐 활용)
- 플로이드-워셜 (Floyd-Warshall): 모든 지점에서 모든 지점까지 최단 거리
- 최소 신장 트리 (MST, Minimum Spanning Tree)
- 크루스칼 (Kruskal): 간선을 가중치 순으로 정렬 후 최소 비용 그래프 구성
- 프림 (Prim): 하나의 노드에서 출발해 최소 비용으로 연결
💡 네트워크, 지도 문제에서 자주 등장
4. 완전 탐색 & 백트래킹
- 완전 탐색 (Brute Force): 가능한 모든 경우를 다 탐색하는 방식
- 백트래킹 (Backtracking): 불가능한 경로를 미리 가지치기하여 효율적으로 탐색
💡 N-Queen, 순열/조합 문제에서 자주 등장
5. 동적 계획법 (DP, Dynamic Programming)
- 큰 문제를 작은 문제로 쪼개서 해결하고, 결과를 저장해 다시 활용하는 방식
- 대표적인 문제
- 피보나치 수열 (O(N)으로 최적화 가능)
- 배낭 문제 (Knapsack)
- 계단 오르기 (점화식 활용)
💡 DP는 점화식(재귀 관계) 찾는 게 핵심!
6. 그리디 (Greedy) 알고리즘
- 매 순간 최선의 선택을 하는 방식
- 대표적인 문제
- 거스름돈 문제
- 회의실 배정 문제
- 다익스트라 알고리즘 (그리디 + 우선순위 큐 활용)
💡 "항상 최적의 해를 보장하는가?" 체크 필요!
7. 문자열 알고리즘
- KMP (Knuth-Morris-Pratt): 문자열 패턴 찾기 알고리즘
- 트라이 (Trie): 문자열을 트리 형태로 저장하는 자료구조
💡 문자열 검색 문제에서 자주 등장
8. 기타 알고리즘
- 비트마스크: 비트 연산을 활용한 최적화
- 유니온 파인드 (Disjoint Set): 집합을 효율적으로 관리하는 알고리즘
- 투 포인터 (Two Pointer): 정렬된 리스트에서 두 개의 포인터를 이동하며 최적화
어떤 알고리즘을 공부해야 할까?
- 기본적으로 정렬, 탐색, DP, 그리디는 필수!
- 그래프, 완전 탐색, 문자열 알고리즘은 문제 유형을 보고 필요하면 익히기
- 코딩테스트에서는 빠른 구현력이 중요하니, 라이브러리를 적극 활용
나중에 공부하려고 GPT한테 물어봄.
여기 있는 거 다 공부해야지!
지금 나의 원씽은 알고리즘이 아니니 next14, ts 공부, 정처기 실기, 웹디기능사 실기 합격 끝나면 시작해볼 예정