### 학습한 내용 🧑💻
1. **그리디 알고리즘(Greedy Algorithm)**:
- 각 단계에서 최적의 선택을 하여 최종 해답에 도달하는 근시안적인 방법론.
- 주요 속성:
- **탐욕 선택 속성(Greedy Choice Property)**: 각 단계의 최적 선택이 전체 최적해를 보장함.
- **최적 부분 구조(Optimal Substructure)**: 전체 문제의 최적해가 부분 문제의 최적해로 구성됨.
- 주요 예시:
- **거스름돈 문제**: 가장 큰 동전부터 선택하여 거스름돈을 최소 동전 개수로 계산.
- **체육복 문제**: 체육복을 잃어버린 학생들에게 여벌 체육복을 빌려주는 문제.
- 그리디 알고리즘이 항상 최적해를 보장하지 않는 경우도 있으며, 동적 계획법(DP)을 통해 해결하는 방법도 있음.
2. **동적 계획법(Dynamic Programming)**:
- 작은 문제의 해를 메모이제이션하여 중복 계산을 피하고, 이를 이용하여 큰 문제를 해결.
- 조건:
- **중복 부분 문제**: 동일한 부분 문제가 여러 번 계산됨.
- **최적 부분 구조**: 전체 문제의 최적해가 부분 문제의 최적해로 구성됨.
- 예시:
- **동전 문제**: 그리디 알고리즘이 최적해를 보장하지 않는 경우, 동적 계획법을 통해 최적해를 구함.
3. **구현 예시**:
- **거스름돈 문제**: 가장 큰 동전부터 사용하여 거스름돈을 계산하는 코드.
- **체육복 문제**: 체육복을 잃어버린 학생들에게 여벌 체육복을 빌려주는 문제를 해결하는 코드.
- **A → B 문제**: 두 가지 연산을 이용하여 A를 B로 바꾸는 최소 연산 횟수를 구하는 BFS 알고리즘.
- **우유 축제 문제**: 우유를 특정 순서대로 마시는 규칙을 지키며 최대한 많은 우유를 마시는 문제를 해결하는 그리디 알고리즘.
### 얻은 인사이트 💡
1. **그리디 알고리즘의 강점과 한계**:
- **강점**: 구현이 간단하고 빠르며, 문제를 직관적으로 해결할 수 있음.
- **한계**: 항상 최적해를 보장하지 않으며, 문제의 성질에 따라 부적합할 수 있음.
- **적용 가능성**: 탐욕 선택 속성과 최적 부분 구조를 만족하는 문제에 적합.
2. **동적 계획법의 유용성**:
- **유용성**: 중복 계산을 피하고 최적해를 보장하는 문제에 적합.
- **비용**: 메모리와 시간 자원이 많이 소요될 수 있음.
- **적용 예시**: 그리디 알고리즘이 최적해를 보장하지 않는 경우, 동적 계획법을 통해 문제를 해결.
3. **BFS를 통한 최적 경로 찾기**:
- **BFS의 장점**: 최단 경로를 찾는 문제에 적합하며, 모든 가능한 경로를 탐색하여 최적해를 보장.
- **적용 예시**: A를 B로 바꾸는 문제에서 두 가지 연산을 통해 최적 경로를 찾는 알고리즘.
4. **문제 해결의 다양성**:
- 각 문제의 특성과 조건에 따라 적합한 알고리즘을 선택하는 것이 중요함.
- 그리디 알고리즘, 동적 계획법, BFS 등 다양한 접근 방법을 통해 문제를 해결할 수 있음.
이러한 내용을 통해 알고리즘 문제 해결에 대한 이해를 높이고, 적절한 알고리즘을 선택하여 문제를 해결하는 능력을 향상시킬 수 있습니다. 🥷💻
어제 오늘 그리고 내일