탐욕 알고리즘 (Greedy Algorithm) 이란??

알고리즘 공부순서가 뒤죽박죽.. ㅎㅎ 개념을 알고난 뒤 다시 정리해야겠다.

이번 포스팅과 다음 포스팅은 탐욕 알고리즘과 다이나이믹 프로그래밍에 대해서 하겠습니다. 

1. 탐욕 알고리즘이란

  - 현재 상황에서 가장 좋아보이는 답을 선택합니다.

  - 각 부분에서 최적을 선택하면 전체에서 최적이 될 것이라는 가정을 전제로 합니다.

  - 기본적으로 값이 큰 경우대로 극단적으로 문제를 접근합니다.

2. 탐욕 알고리즘의 사용 예

  ① 분할 가능 배낭문제

     - 여행가가 가지고 있는 배낭에는 담을 수 있는 무게의 최댓값이 정해져있고, 

       일정 가치와 무게가 있는 짐들을 배낭을 넣을 때 가치의 합이 최대가 되도록 짐을 고르는 문제

  ② 최소수의 동전으로 거스름돈 내주기

     - 거스름돈을 내줄때 가장 적은 양의 동전을 내주는 문제

     ex 1) 930원의 거스름돈을 500원, 200원, 50원, 10원의 동전으로 내줄 때,

              500원 동전 1개 + 200원 동전 2개 + 10원 동전 3개 = 총 6개

              총 6개의 동전으로 가장 적은 양의 동전으로 내줄 수 있다.

     

     ex 2) 동전의 단위가 다르게 바뀐다면?

             930원의 거스름돈을 500원, 300원, 30원, 10원의 동전으로 내줄 때,

             500원 동전 1개 + 300원 동전 1개 + 30원 동전 4개 + 10원 동전 1개 = 총 7개 이지만

             300원 동전 3개 + 30원 동전 1개 = 총 4개의 더 작은 동전의 양으로 내줄 수 있다.

  * 이렇게 동전의 단위가 바뀌었을 때 그리디알고리즘으로 푼다면 성립하지 않게되는데, 이때 동적 프로그래밍이 필요합니다.

  

3. 탐욕 알고리즘 vs 동적 프로그래밍

탐욕 알고리즘	동적 프로그래밍
하위 문제를 풀기전에 선택합니다.	하위 문제를 풀고 나서 선택합니다.
항상 하나의 문제만을 고려합니다.	동시에 여러 개의 하위 문제를 고려합니다.

4. 탐욕 알고리즘 구현