[항해99 취업리부트 TIL] 4주차 3일

### 학습한 내용 🧑‍💻

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 등 다양한 접근 방법을 통해 문제를 해결할 수 있음.

이러한 내용을 통해 알고리즘 문제 해결에 대한 이해를 높이고, 적절한 알고리즘을 선택하여 문제를 해결하는 능력을 향상시킬 수 있습니다. 🥷💻