그리디 - 6. 실전 문제 풀이 및 최종 프로젝트

📌 6. 실전 문제 풀이 및 최종 프로젝트

✅ 학습 목표

이번 단원에서는 그리디 알고리즘을 실전에서 적용하는 방법을 학습합니다.
백준, 프로그래머스 등의 온라인 저지 사이트에서 문제를 직접 풀어보고,
그리디 알고리즘을 활용한 응용 프로젝트를 수행해 실력을 향상시킵니다.

1. 온라인 문제 풀이를 통해 실전 감각 익히기
2. 그리디 알고리즘을 활용한 실전 문제 해결 연습
3. 응용 프로젝트를 통해 실전에서의 활용 방법 이해

---

✅ 실전 연습 사이트

🔹 온라인 문제 풀이 사이트

1. 백준 온라인 저지 - https://www.acmicpc.net/
   • 다양한 알고리즘 문제 제공
   • 단계별 문제 풀이 가능
   • 코딩 테스트 대비 필수 사이트
2. 프로그래머스 - https://programmers.co.kr/
   • 기업 코딩 테스트 대비 가능
   • 난이도별 문제 제공
   • 실전 프로젝트 문제 제공

---

✅ 프로젝트 아이디어

1️⃣ 배달 최적화 문제 (가장 빠른 경로 찾기)

여러 지역에 배달을 해야 할 때, 가장 빠른 경로를 찾아 최적의 배달 경로를 결정하는 문제.
그리디 알고리즘을 활용하여 경로를 결정할 수 있는가?

✅ 문제 해결 방식

• 현재 가장 가까운 위치를 선택하며 경로 탐색 → 그리디 알고리즘 적용
• 다익스트라 알고리즘과 비교하여 최적해를 보장할 수 있는지 분석
• 현실적으로 최적의 경로를 찾는 알고리즘(예: A* 알고리즘)과 비교

---

2️⃣ 최소 비용 네트워크 연결 문제 (크루스칼 알고리즘과 비교)

여러 개의 도시를 연결할 때, 최소 비용으로 모든 도시를 연결하는 방법을 찾는 문제.
대표적인 예: 전기 케이블 최소 비용 연결, 도로 건설 비용 최소화

✅ 문제 해결 방식

• 그리디 알고리즘 적용 가능 여부 판단
• 크루스칼 알고리즘 (최소 신장 트리 MST) 과 비교하여 효율 분석
• 현실적인 문제(인터넷 망 연결, 송전선 설치 등)와 연관 지어 해결

---

✅ 정리

1. 온라인 저지(백준, 프로그래머스)에서 실전 문제 풀이 연습
2. 배달 최적화 문제에서 그리디를 적용할 수 있는지 분석
3. 최소 비용 네트워크 연결 문제에서 그리디 방식과 크루스칼 알고리즘 비교
4. 실전 프로젝트를 통해 응용 능력 향상