[알고리즘/그리디] 그리디 알고리즘

그리디 알고리즘이란?

현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘

 

! 탐욕법으로 얻은 해가 최적의 해가 되는 상황인지, 추론할 수 있어야 함.

 

수행과정

1. 현재 상태에서 최선의 해 선택

2. 현재 선택한 해의 적절성 검사

3. 현재까지의 해 집합이 문제를 해결할 수 있는지 검사

 

 

백준 : 1715

https://www.acmicpc.net/problem/1715

priority queue를 활용해 가장 적은 카드묶음 순으로 뽑는다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    int N;
    std::cin >> N;
    std::priority_queue<int, std::vector<int>, std::greater<int>> cards;
    int count = 0;
    for (int i = 0; i < N; ++i) {
        int card;
        std::cin >> card;
        cards.push(card);
    }
    while (!cards.empty()) {
        int tmp = cards.top();
        cards.pop();
        if (!cards.empty()) {
            tmp += cards.top();
            cards.pop();
            count += tmp;
            cards.push(tmp);
        }
    }
    std::cout << count;
}

 

 

 

[참고]

주홍철, <면접을 위한 CS 전공지식 노트>, 길벗(2022), p202