알고리즘 벼락치기, 알고리즘 공부 좀 할껄... 너무 아쉽다. 😭

알고리즘 입문 로드맵

🧭 알고리즘 실습 순서 (코드 중심)

1. 탐색 (Search)
   • 선형 탐색
   • 이진 탐색
   • DFS / BFS (그래프 탐색)
2. 정렬 (Sorting)
   • 선택, 삽입, 버블
   • 퀵 정렬, 병합 정렬
   • 힙 정렬
3. 재귀와 분할 정복
   • 재귀 기본
   • 분할 정복 문제 (퀵, 병합 활용)
4. 그래프 이론
   • 인접리스트/행렬 구현
   • DFS/BFS 활용 문제
   • 최단 경로 (다익스트라 등)
5. 탐욕(Greedy) & 정렬 응용
   • 거스름돈, 회의실 배정 등
6. 동적 계획법(DP)
   • 피보나치, 배낭, LIS
7. 백트래킹
   • N-Queen, 순열/조합 생성

---

 

✅ 1. 탐색(Search)

원하는 데이터를 찾는 알고리즘

알고리즘	설명	시간 복잡도
선형 탐색 (Linear Search)	처음부터 끝까지 하나씩 찾음	O(n)
이진 탐색 (Binary Search)	정렬된 배열에서 반씩 쪼개며 탐색	O(log n)
DFS / BFS	그래프나 트리에서 경로/전체 탐색	O(V + E)

 

---

✅ 2. 정렬(Sorting)

데이터를 특정 기준에 맞춰 순서대로 나열

알고리즘	특징	시간 복잡도
선택 정렬	가장 작은 걸 앞으로	O(n²)
버블 정렬	인접 요소 비교해서 스왑	O(n²)
삽입 정렬	앞부분은 정렬된 상태 유지	O(n²)
퀵 정렬	분할 정복 기반, 평균 빠름	O(n log n)
병합 정렬	안정적 정렬, 분할 합치기	O(n log n)
힙 정렬	힙 자료구조 기반	O(n log n)
계수 정렬	값 범위가 작을 때만 가능	O(n)

 

---

✅ 3. 탐욕(Greedy)

매 순간 최선의 선택을 해서 전체에서 최적을 도출하려는 알고리즘

• ex) 거스름돈 최소 개수, 회의실 배정, Kruskal 최소 신장 트리
• 항상 최적을 보장하진 않음
• O(n log n) ~ O(n)

---

✅ 4. 분할 정복(Divide & Conquer)

문제를 작게 쪼개서 각각 해결한 뒤, 합쳐서 전체 문제 해결

• 대표: 퀵 정렬, 병합 정렬, 이진 탐색, 분할 정복 DP
• 시간복잡도: O(n log n) 또는 O(log n)

 

---

✅ 5. 동적 프로그래밍(DP)

중복되는 하위 문제를 저장해가며 푸는 방식 (Memoization)

• 피보나치, 배낭 문제, 최장 증가 수열(LIS)
• 탑다운(재귀 + 메모) / 바텀업(반복문)
• 시간복잡도: O(n), O(n²), O(n·W) 등

---

✅ 6. 백트래킹(Backtracking)

모든 경우의 수를 시도하되, 조건에 맞지 않으면 되돌아가서 재탐색

• 대표: N-Queen, 스도쿠, 순열 생성, 조합 찾기
• DFS 기반이 많음
• 시간복잡도: O(2^n), O(n!) 등 (비효율적일 수 있음)

---

✅ 7. 그래프 알고리즘

노드와 간선으로 구성된 구조를 탐색 또는 분석

알고리즘	설명
DFS / BFS	경로 탐색, 연결 컴포넌트 찾기
다익스트라	최단 거리 (음수 가중치 ❌)
벨만-포드	음수 간선 허용, 느림
플로이드-워셜	모든 쌍 최단 거리
크루스칼 / 프림	최소 신장 트리 (MST)
위상 정렬	방향 그래프의 순서 정하기

 

---

✅ 8. 문자열 알고리즘

문자열 내에서 특정 패턴을 찾거나 변형

• KMP (부분 일치), Rabin-Karp (해시)
• 트라이(Trie), 접미사 배열, 롤링 해시

---

✅ 9. 수학/기하 알고리즘

분야	알고리즘
수학	에라토스테네스의 체, 유클리드 호제법(GCD), 소수 판별
기하	CCW, Convex Hull, 스위핑, 볼록 다각형 판별 등

 

---

🎯 보너스: 어디에 쓰는지 예시

문제 예시	분류
미로 찾기, 연결된 정점 찾기	BFS / DFS
최단 경로	다익스트라, BFS
최대 이익 구하기	DP, 그리디
가능한 모든 조합	백트래킹
주어진 문자열 안에서 패턴 찾기	KMP, 슬라이딩 윈도우
데이터를 순서대로 정렬	퀵, 병합, 힙 정렬