알고리즘
기술노트
📘 알고리즘 개요
🤔 알고리즘이란?
- **알고리즘(Algorithm)**이란 어떤 문제를 해결하기 위한 절차적 방법 또는 명확한 규칙들의 집합입니다.
- 쉽게 말해, **"입력 → 처리 → 출력"** 과정을 수행하는 정확한 단계입니다.
예시:
- 요리를 만들기 위한 **레시피**, 주어진 숫자들을 정렬하는 **방법**, 목적지까지 최단경로를 찾는 **길찾기 방식** 등
🔎 알고리즘의 구성 요소
| 항목 | 설명 |
|---|---|
| 입력(Input) | 처리할 데이터 |
| 처리(Process) | 문제를 해결하기 위한 논리적 단계 |
| 출력(Output) | 원하는 결과 |
| 명확성(정확한 정의) | 각 단계는 모호하지 않고 명확해야 함 |
| 종료성(Finiteness) | 반드시 일정 횟수 내에 끝나야 함 |
📏 좋은 알고리즘의 조건
- ⏱️ **시간 효율성**: 빠르게 실행될수록 좋음
- 💾 **공간 효율성**: 적은 메모리 자원을 사용할수록 좋음
- 🔁 **단순성**: 읽기 쉽고 구현이 쉬워야 함
- 📦 **확장성**: 입력이 커져도 잘 작동해야 함
💡 알고리즘의 성능은 주로 **시간 복잡도**와 **공간 복잡도**로 평가합니다.
⏳ 시간 복잡도
시간 복잡도(Time Complexity)는 **입력 크기(n)**에 따라 알고리즘이 수행하는 연산 횟수를 수학적으로 표현한 것입니다.
| 표기법 | 설명 | 예시 |
|---|---|---|
| O(1) | 입력 크기에 관계없이 일정한 시간 | 배열에서 인덱스로 접근 |
| O(log n) | 로그에 비례 | 이진 탐색 |
| O(n) | 입력 크기에 비례 | 선형 탐색 |
| O(n log n) | 선형보다 느리지만 효율적인 정렬 | 병합 정렬, 퀵 정렬(평균) |
| O(n²) | 이중 반복문 | 버블 정렬, 선택 정렬 |
| O(2ⁿ) | 지수적 증가, 매우 비효율적 | 재귀적 피보나치 |
📚 알고리즘 분류
📂 **문제 해결 방식**에 따라 다양한 알고리즘이 존재합니다:
| 유형 | 설명 | 예시 |
|---|---|---|
| 탐색(Search) | 원하는 데이터를 찾는 방법 | 선형 탐색, 이진 탐색 |
| 정렬(Sort) | 데이터를 정해진 순서로 재배열 | 버블 정렬, 퀵 정렬, 병합 정렬 |
| 그리디(Greedy) | 매 순간 최선의 선택 | 거스름돈 문제, 최소 신장 트리(Kruskal) |
| 분할 정복(Divide & Conquer) | 문제를 쪼개고 해결 후 결합 | 병합 정렬, 퀵 정렬 |
| 동적 계획법(DP) | 작은 문제의 결과를 저장해서 재활용 | 피보나치 수열, 배낭 문제 |
| 백트래킹(Backtracking) | 모든 경우를 탐색하되 조건에 따라 중간에 포기 | N-Queen, 퍼즐 |
| 그래프(Graph) | 정점과 간선으로 표현되는 문제 처리 | BFS, DFS, 다익스트라, 플로이드 |
💡 알고리즘 실전 예시
예제 1: **최댓값 찾기**
```python def find_max(arr):
max_val = arr[0]
for num in arr:
if num > max_val:
max_val = num
return max_val
