[Algorithm] Greedy algorithm

그리디 알고리즘 (Greedy Algorithm)

"바로 눈앞의 이익만을 쫓는 알고리즘"

• 글로벌 최적을 찾기 위해 각 단계에서 로컬 최적의 선택을 하는 알고리즘

  • 합리적인 시간 내에 최적에 가까운 답을 찾을 수 있음

• 탐욕 선택 속성을 갖고 있는 최적 부분 구조인 문제들

  • 탐욕 선택 속성 : 앞의 선택이 이후 선택에 영향을 주지 않는 것
  • 최적 부분 구조 : 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우

그리디 알고리즘 vs 다이나믹 프로그래밍

• 그리디 알고리즘

  • 각 단계마다 로컬 최적해를 찾는 문제로 접근해 문제를 더 작게 줄여나가는 형태

• 다이나믹 프로그래밍

  • 하위 문제에 대한 최적의 솔루션을 찾은 다음 이 결과들을 결합해 전역 최적 솔루션 선택

배낭 문제 (Knapsack Problem)

• 조합 최적화(combinatorial optimization) 분야의 문제
• 배낭에 담을 수 있는 무게의 최댓값이 정해져 있을 때, 가치의 합이 최대가 되도록 만드는 방법

• 분할 가능 배낭 문제

  • 그리디 알고리즘으로 해결
  • 단가(가격 / 무게)가 높은 순으로 그리디 알고리즘으로 계산

• 0-1 배낭 문제 (분할 불가능)

  • 다이나믹 프로그래밍으로 해결

동전 바꾸기 문제 (Coin-Change Problem)

• 동전이 이전 액면의 배수 이상으로 증가하는 경우만 가능

  • 10원, 50원, 100원처럼 증가하는 경우
  • 배수가 아닌 경우 다이나믹 프로그래밍으로 품

---

참고 : 「파이썬 알고리즘 인터뷰」