[패스트캠퍼스 수강 후기] {코딩테스트인강} 100% 환급 챌린지 43회차 미션

탐욕 알고리즘의 이해

 

1. 탐욕 알고리즘 이란?
- Greedy algorithm 또는 탐욕 알고리즘 이라고 불리움
- 최적의 해에 가까운 값을 구하기 위해 사용됨
- 여러 경우 중 하나를 결정해야할 때마다, **매순간 최적이라고 생각되는 경우를 선택**하는 방식으로 진행해서, 최종적인 값을 구하는 방식

 

2. 탐욕 알고리즘 예
문제1: 동전 문제
  - 지불해야 하는 값이 4720원 일 때 1원 50원 100원, 500원 동전으로 동전의 수가 가장 적게 지불하시오.
    - 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현 가능
    - 탐욕 알고리즘으로 매순간 최적이라고 생각되는 경우를 선택하면 됨

 

 

 문제2: 부분 배낭 문제 (Fractional Knapsack Problem)
  - 무게 제한이 k인 배낭에 최대 가치를 가지도록 물건을 넣는 문제
    - 각 물건은 무게(w)와 가치(v)로 표현될 수 있음
    - 물건은 쪼갤 수 있으므로 물건의 일부분이 배낭에 넣어질 수 있음, 그래서 Fractional Knapsack Problem 으로 부름
      - Fractional Knapsack Problem 의 반대로 물건을 쪼개서 넣을 수 없는 배낭 문제도 존재함 (0/1 Knapsack Problem 으로 부름)

 

탐욕 알고리즘 

정의: 미리 정한 기준에 따라서 매번 가장 좋아 보이는 답을 선택하는 알고리즘

 

동적 계획법과 마찬가지로 최적화 문제를 푸는데 사용 

근시안적으로 해를 구할 당시에 가장 최적인 해를 구함

탐욕 알고리즘은 동적 계획법보다 효율적이긴 하지만 동적 계획법처럼 반드시 최적의 해를 구한다는 보장을 하지 못한다

알고리즘

1. 해선택: 지금 당시에 가장 최적인 해를 구한뒤 , 이를 부분해 집합에 추가

2. 적절성 검사: 새로운 부분해 집합이 적절한지 검사 

3. 해검사 : 부분해 집합이 거슬러 줄 금액과 일치하는지 검사. 액수가 모자라면 다시 1로 돌아가서 부분해 집합에 추가한 동전을 고른다 

 이렇게 만든 알고르짐에 꽤 쓸만해 보이지만 항상 최적의 해를 구해주는 것은 아닙니다. 대부분의 국가에서 사용하는 화폐들의 단위는 이 알고리즘이 항상 최적을 해를 구할 수 있도록 되어있습니다. 우리나라의 동전은 500원, 100원, 50원, 10원 이렇게 4가지가 있습니다. 이 중 아무것이나 두 개를 골라서 최대공약수를 구하면 항상 작은 값의 동전 단위가 나옵니다. 예를 들어 500과 50의 최대공약수는 50이고 100과 10의 최대공약수는 10입니다.

이런 시스템에서는 가장 최소수의 동전으로 이루어진 거스름돈을 만들기가 쉽습니다. 예를들어 물건 금액이 3,800원이고 손님이 5,000원을 지불했다면 500원짜리 두개와 100원짜리 두개를 거슬러 주면 됩니다. 이것은 위의 알고리즘으로도 같은 결과를 얻을 수 있습니다.

하지만 여기에 400원짜리 동전이 생긴다면 어떻게 될까요 400은 500과 최대공약수가 100으로 작은 값의 동전 단위가 나오지 않습니다. 이 때 거스름돈을 1200원 거슬러 주어야 한다면 400원짜리 동전 3개를 거슬러 주는 것이 가장 최적의 방법이지만, 위의 알고리즘대라면 500원짜리 2개와 100원짜리 2개를 거슬러주게 될 것입니다.

강의에 대해 정확하게 알고 싶다면 

https://bit.ly/2FgOONG