Greedy

그리디 알고리즘

: 매 단계에서 가장 최선이라고 생각되는 선택을 하는 알고리즘. 이때 "최선"이란 현재 상황에서 가장 좋아보이는 선택(예: 가장 큰 값, 가장 작은 비용 등)을 의미하며, 이런 선택을 반복한 결과가 전체 문제의 최적해(Optimal Solution)로 이어지는 방식.

---

✅ 그리디 알고리즘의 핵심 특징

• 탐욕적 선택 속성
  : 현재 상황에서 가장 좋아 보이는 선택이 전체 문제에서도 최적이라는 보장이 있어야 함.
• 최적 부분 구조
  : 전체 문제의 최적해가 부분 문제의 최적해로 구성될 수 있어야 함.

---

✅ 그리디 알고리즘 동작 방식 예시

1. 항상 현재 상태에서 가장 좋은 선택을 한다.
2. 이 선택이 전체적으로도 최저의 해가 될 것이라 가정한다.
3. 선택을 확정하고, 문제를 줄여 나간다.

---

💡 예시 문제들

1. 동전 거스름돈 문제
   • 목표 금액을 거슬러 줄 때, 가장 큰 단위의 동전부터 최대한 사용하는 방식
   • 단, 모든 경우에 최적이 되는 것은 아니므로 "단위가 특정 조건을 만족할 때만" 적용 가능
2. 회의실 배정 문제
   • 회의 종료 시간이 가장 빠른 회의를 먼저 선택하면, 가장 많은 회의를 배정할 수 있음
3. 프림 알고리즘 / 크루스칼 알고리즘 (최소 신장 트리)
   • 대표적인 그리디 기반 알고리즘

---

✅ 그리디 알고리즘의 일반적인 단계

1. 문제 이해 및 최적 부분 구조 확인
   • 문제를 정확히 이해하고, 문제를 작은 부분 문제로 나눌 수 있으며 그 부분 문제의 최적해들이 모여 전체 문제의 최적해가 되는지 확인한다.
2. 탐욕적 선택 조건 정의
   • 매 단계에서 "어떤 기준으로 선택할 것인가"를 정의한다.
     예) 가장 작은 값, 가장 이른 종료 시간, 가장 적은 비용 등
3. 선택 정렬 기준 결정 및 정렬
   • 효율적인 선택을 위해 필요한 정보를 정렬한다.
     예) 종료 시간 기준 정렬, 무게 대비 가치 정렬 등
4. 선택하고 가능한지 판단
   • 각 단계에서 정의한 기준에 따라 선택하고, 그 선택이 문제 조건에 부합하는지 확인한다.
     예) 겹치는 회의인지 확인, 무게 초과인지 확인 등
5. 선택을 확정하고 문제 상태 갱신
   • 선택을 결과에 추가하고, 문제 상태를 해당 선택 기준에 맞게 업데이트한다.
     예) 남은 용량, 선택된 시간대 등
6. 종료 조건까지 반복
   • 더 이상 선택할 것이 없을 때까지 위 과정 반복
7. 결과 출력 및 검증
   • 최종 선택된 결과가 문제의 요구 사항을 충족하는지 확인하고 반환한다.

---

💡 간단한 예시: 회의실 배정 문제
1. 각 회의의 시작/ 종료 시간이 주어짐 → 최적 부분 구조 존재
2. 종료 시간이 빠른 회의를 우선 선택
3. 종료 시간 기준으로 회의 리스트 정렬
4. 회의가 이전 회의와 겹치지 않으면 선택
5. 선택한 회의는 확정, 그 다음 가능한 회의로 넘어감
6. 모든 회의를 확인할 때까지 반복
7. 최종 선택된 회의 개수 반환

---

➕ 그리디와 유사한 알고리즘

• 동적 계획법 (Dynamic Programming, DP)
• 백트래킹 (Backtracking)

1. 동적 계획법

• 공통점
  • 둘 다 최적 부분 구조를 갖는 문제에 적용된다.
    즉, 큰 문제를 작은 문제로 나눌 수 있고, 그 부분 문제들의 결과를 활용해서 전체 문제를 해결한다.
• 차이점

항목	그리디 알고리즘	동적 계획법
선택 기준	현재 최선의 선택	모든 경우를 고려한 선택
중복 계산	없음 (과거 선택을 기억하지 않음)	있음 →메모이제이션 or 테이블 사용
적용 조건	탐욕적 선택이 항상 최적해로 이어져야 함	중복 부분 문제 + 최적 부분 구조
속도/메모리	빠르고 간단 (보통 O(n) ~ O(n log n)	느릴 수 있음, 메모리 많이 사용 (보통 O(n^2) 이상
예시 문제	회의실 배정, 최소 동전 개수, Kruskal	피보나치 수, 배낭 문제, 최장 증가 부분 수열

• 핵심 차이:
  • 그리디는 '지금 당장 좋아 보이는 것'을 선택하고 미래를 고려하지 않음.
  • DP는 '모든 경우'를 비교하고, 미래까지 고려해 최적의 선택을 저장하며 진행.

2. 백트래킹

• 공통점
  • 둘 다 단계별로 선택지를 탐색하면서 해를 구함.
• 차이점

항목	그리디 알고리즘	백트래킹
전략	하나의 선택지를 따라 끝까지 진행	모든 경우를 고려한 선택
선택 방식	한 번 선택하면 되돌아가지 않음	되돌아갈 수 있음 (재귀적으로 모든 경우 탐색)
탐색 범위	제한적, 빠름	전체 탐색, 느림 (최악 O(2^n))
예시 문제	동전 거스름돈, 활동 선택 문제	N-Queen, 미로 찾기, 순열 생성

• 핵심 차이:
  • 그리디는 '이거면 되겠지'하며 한 길만 감.
  • 백트래킹은 '이게 안 되면 돌아가자' 하며 모든 경우를 시도.