[알고리즘] 알고리즘 설계 기법(Algorithm Design Paradigms)

🧠 알고리즘 설계 기법(Algorithm Design Paradigms) 정리

문제를 해결하기 위한 다양한 전략,
바로 알고리즘 설계 기법이다.

---

🔍 알고리즘 설계 기법이란?

알고리즘 설계 기법은 복잡한 문제를 구조적으로 해결하기 위한 방법론을 말합니다.
문제 유형에 따라 적절한 전략을 선택하면 효율적인 해결이 가능합니다.

---

📚 주요 알고리즘 설계 기법

1. 완전 탐색 (Brute Force)

• 가능한 모든 경우를 시도
• 구현은 쉽지만 시간 복잡도가 높음
• ex) 모든 조합, 순열 생성

2. 그리디(Greedy)

• 매 순간 가장 좋아 보이는 선택을 하는 방식
• 국지적 최적이 전역 최적을 보장할 때만 사용 가능
• ex) 거스름돈 문제, 회의실 배정

3. 분할 정복(Divide and Conquer)

• 문제를 쪼개고 해결한 뒤 병합
• 보통 재귀 구조로 구현됨
• ex) 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort)

4. 동적 계획법(DP, Dynamic Programming)

• 중복되는 부분 문제를 메모이제이션으로 최적화
• 점화식 기반, 하향식(top-down) or 상향식(bottom-up)
• ex) 피보나치 수열, 배낭 문제(Knapsack)

5. 백트래킹(Backtracking)

• 모든 가능성을 시도하면서 조건이 맞지 않으면 가지치기
• DFS 기반으로 구현됨
• ex) N-Queen, 스도쿠

6. 탐색 알고리즘 (BFS / DFS)

• 그래프나 트리 구조에서 경로를 찾는 데 사용
• BFS는 최단거리, DFS는 깊이 우선 탐색에 유리
• ex) 미로 찾기, 단지 번호 붙이기

7. 최단 경로 알고리즘

• 그래프에서 두 정점 사이의 최소 거리 계산
• ex)
  • 다익스트라: 양의 가중치
  • 벨만-포드: 음수 가중치 허용
  • 플로이드-워셜: 모든 정점 간 거리

---

💡 정리 표

방법론	핵심 아이디어	대표 알고리즘 / 문제 예시
완전 탐색	모든 경우 시도	순열, 조합
그리디	현재 최선 선택	회의실 배정, 최소 동전 개수
분할 정복	쪼개고 합치기	퀵 정렬, 병합 정렬
동적 계획법	중복 계산 방지 + 메모이제이션	피보나치, 배낭 문제
백트래킹	조건 안 맞으면 되돌리기	N-Queen, 스도쿠
BFS/DFS	그래프 탐색	미로, 경로 찾기
최단 경로	그래프 최단 거리	다익스트라, 플로이드-워셜

---

✨ 마무리

알고리즘 문제를 마주했을 때,
"이건 그리디로 풀 수 있을까? DP가 맞을까?"
이렇게 설계 기법을 기준으로 접근하는 습관을 들이면 문제 해결력이 크게 향상됩니다.

알고리즘은 속도가 아니라 사고의 구조화다.