[이취코] Chapter 03. 그리디

* 해당 게시글은 [이것이 취업을 위한 코딩테스트다, 나동빈] 교재를 학습하고 정리한 글입니다.

 

1. 그리디 알고리즘

• 현재 상황에서 지금 가장 좋은 것을 골라나가는 방법
• 현재의 선택이 나중에 미칠 영향은 고려하지 않음
• 예) 다익스트라 알고리즘, 크루스칼 알고리즘

 

2. 언제 사용할까?

• 문제를 보고 현재 상황에서 가장 좋아보이는 것을 선택할 때 문제가 풀릴 지를 파악할 수 있어야 함
• 그리디로 판단할 때는 정당한지(= 다른 방법이 불가능한 지) 검토할 수 있어야 함 
• '가장 큰 순서대로', '가장 작은 순서대로' 와 같은 기준을 알게 모르게 제시해주는 편
• 정렬 알고리즘과 함께 결함된 문제가 많음

 

3. 예제

#include <iostream>

using namespace std;

int coins[4] = {500, 100, 50, 10};

int main() {
    int N;
    cin >> N;

    int count = 0;
    for(int coin : coins) {
        count += (N / coin);
        N %= coin;
    }

    cout << count;

    return 0;
}