그리디 - 1. 그리디 알고리즘 개요

📌 1. 그리디 알고리즘 개요

✅ 학습 목표

이 단원에서는 그리디 알고리즘(Greedy Algorithm)이 무엇인지 배우고, 언제 사용할 수 있는지를 학습합니다.
학습을 마치면 다음 개념을 이해할 수 있습니다.

1. 알고리즘이란 무엇인가?
   • 알고리즘의 정의와 중요성을 이해합니다.
2. 그리디 알고리즘의 개념과 특징
   • 그리디 알고리즘이 무엇이며, 어떤 방식으로 동작하는지 알아봅니다.
3. 그리디 알고리즘이 사용될 수 있는 조건
   • 그리디 알고리즘이 적용 가능한 문제의 특징을 학습합니다.

---

✅ 학습 내용

1. 알고리즘이란?

알고리즘(Algorithm)은 어떤 문제를 해결하기 위한 절차나 방법을 의미합니다.
즉, 특정한 문제를 해결하는 데 필요한 명령어들의 집합입니다.

🔹 알고리즘의 핵심 요소

• 입력(Input): 문제 해결을 위해 주어진 값
• 출력(Output): 알고리즘이 도출하는 결과
• 명확성(Definiteness): 알고리즘의 각 단계가 명확해야 함
• 유한성(Finiteness): 정해진 단계 내에 반드시 종료해야 함
• 효율성(Efficiency): 실행 속도가 빠르고 자원(메모리)을 적게 사용해야 함

2. 그리디 알고리즘이란?

그리디 알고리즘(Greedy Algorithm)은 매 순간 가장 최적(최선)의 선택을 하면서 문제를 해결하는 알고리즘입니다.
즉, 전체 최적해를 구하기 위해 각 단계에서 최적의 선택을 반복적으로 수행합니다.

✅ 특징

• 현재 상황에서 가장 좋은 선택을 함
• 앞으로의 결과를 깊이 고려하지 않음
• 일반적으로 빠르고 구현이 간단함

✅ 예제: 거스름돈 문제

예를 들어, 거스름돈을 줄 때 가장 큰 단위의 동전부터 사용하면
최소 개수의 동전으로 거스름돈을 줄 수 있습니다.

하지만 모든 경우에서 그리디 알고리즘이 정답을 보장하는 것은 아닙니다!
이를 판단하는 중요한 두 가지 조건이 있습니다.

---

3. 그리디 알고리즘이 적용 가능한 경우

그리디 알고리즘이 항상 정답을 보장하지는 않습니다.
그러므로 그리디 알고리즘을 적용할 수 있는 문제인지 판단하는 것이 중요합니다.

그리디 알고리즘이 적용되려면 다음 두 가지 조건이 충족되어야 합니다.

✅ 1) 탐욕적 선택 속성(Greedy Choice Property)

각 단계에서의 최적해 선택이 전체 최적해를 보장해야 함
즉, 현재 선택이 미래의 선택에 영향을 주지 않고, 항상 최적의 결과를 만들어야 합니다.

🔹 예제: 동전 거스름돈 문제

• 500원, 100원, 50원, 10원 단위의 동전이 있을 때, 가장 큰 동전부터 선택하는 방식이 항상 최적해를 보장합니다.
• 하지만 만약 400원 동전이 있다면?
  • 500원 → 100원 4개 (5개 사용) vs 400원 1개 (1개 사용)
  • 이 경우, 그리디 알고리즘은 잘못된 해를 도출할 수 있습니다.

---

✅ 2) 최적 부분 구조(Optimal Substructure)

전체 문제의 최적해가 부분 문제의 최적해를 조합해서 만들어질 수 있어야 함
즉, 부분 문제를 해결하는 방법이 전체 문제에도 적용될 수 있어야 함

🔹 예제: 최단 경로 문제 (다익스트라 알고리즘)

• 특정 지점에서 다른 모든 지점까지 가는 최단 경로를 구하는 문제에서, 부분적으로 가장 가까운 곳을 선택하는 방식이 전체 최적해를 만들 수 있음.

---

✅ 정리

그리디 알고리즘은 매 순간 가장 좋은 선택을 하는 방식으로 문제를 해결합니다.
하지만 모든 문제에서 최적해를 보장하지 않으며, 다음 두 가지 조건을 만족해야만 사용할 수 있습니다.

1. 탐욕적 선택 속성(Greedy Choice Property)
   → 부분 최적해가 전체 최적해를 보장해야 함.
2. 최적 부분 구조(Optimal Substructure)
   → 부분 문제의 최적해를 조합해서 전체 문제의 최적해를 만들 수 있어야 함.