모각코 6회차 : 그리디 알고리즘 [Greedy Algorithm]

그리디 알고리즘 [Greedy Algorithm]

"직역하면 탐욕, 욕심쟁이 알고리즘으로 미래를 고려하지 않고

오직 현재의 시점에서 가장 좋아보이는 선택을 하는 것이다."

앞서 말했듯이 현재의 시점에서 가장 빠른, 가장 저렴한,

가장 가치있는 선택을 하고 뒤도 돌아보지 않는다.

 

그렇기 때문에 그리디 알고리즘이

무조건 최적의 결과를 도출한다는 보장이 없다.

 

따라서 100% 최적의 해를 보장해야

되지 않는 경우에만 사용하는 경우가 많다.

예를 들어 네비게이션은 최적값의 근사치 (10분) 이내에 포함되는

경우의 수도 고려를 한다.

이처럼 근사치에도 만족할 수 있는 경우에는

성능을 개선하기 위해서 사용되곤 한다.

 

예시 1 : 13305 : 주유소

 

코드

#include <stdio.h>

int main() {
    long long int n, minOil, result = 0;

    scanf("%lld", &n);
    long long int distance[n-1];
    long long int oil[n];

    for (int i = 0; i < n-1; i++) {
        scanf("%lld", &distance[i]);
    }

    for (int i = 0; i < n; i++) {
        scanf("%lld", &oil[i]);
    }
    minOil = oil[0];

    for (int i = 0; i < n-1; i++) {
        if (minOil > oil[i]) minOil = oil[i];
        result += minOil * distance[i];
    }

    printf("%lld", result);

    return 0;
}

//
// Created by Leehyuntae on 2025-07-29.
//