Greedy

Lee Sang Hyuk·2022년 1월 8일

Algorithm

목록 보기

1/6

그리디(Greedy)

영어 단어로 "탐욕"이라는 뜻으로, 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미합니다. 알고리즘 문제에서는 최소한의 아이디어를 떠올릴 수 있는 능력을 발휘하는지 판단하는 경우가 있어, 이럴 경우 "Greedy" 방법을 이용해서 해결합니다.

가장 좋은 것만 선택하는 것이므로, "가장 큰 순서대로", "가장 작은 순서대로"와 같은 기준을 유의해야 합니다!

추가적으로, 그리디로 문제를 해결했으면 그에 대한 '정당성'에 대해서 확인할 필요있습니다.

문제 및 풀이

문제 1. 거스름돈

def solution(money):
    count = 0
    coin_types = [500, 100, 50, 10]
    for coin in coin_types:
        count += money // coin
        money %= coin
    return count

solution(1260)
solution(2830)

문제 2. 큰 수의 법칙

n, m, k = map(int, input().split())
num_data = list(map(int, input().split()))

num_data.sort()
first = num_data[n - 1]
second = num_data[n - 2]

count = int(m / (k + 1)) * k
count += m % (k + 1)

result = 0
result += (count) * first
result += (m - count) * second

print(result)

const solution = (n, m, k, arr) => {
    arr.sort((a, b) => b - a);
    let first = arr[0];
    let second = arr[1];

    let result = 0;

    let count = Math.floor(m / k) * k;
    result += count * first;
    result += (m - count) * second;

    return result;
}

let arr = [2, 4, 5, 4, 6];
console.log(solution(5, 8, 3, arr));

sanghyuk-2i/Algorithm

Algorithm/greedy_2.js at main · sanghyuk-2i/Algorithm

문제 3. 숫자 카드 게임

n, m = map(int, input().split())

result = 0

for i in range(n):
    data = list(map(int, input().split()))
    min_value = min(data)
    result = max(result, min_value)

print(result)

const solution = (n, m, arr) => {
    let check = [];
    arr.forEach((a) => {
        check.push(Math.min(...a));
    });
    let result = Math.max(...check);
    return result;
}

let arr = [[3, 1, 2], [4, 1, 4], [2, 2, 2]];
console.log(solution(3, 3, arr));

sanghyuk-2i/Algorithm

Algorithm/greedy_3.js at main · sanghyuk-2i/Algorithm

문제 4. 1이 될 때까지

n, k = map(int, input().split())
count = 0

while(n != 1):
    if(n % k == 0):
        n /= k
    else:
        n -= 1
    count += 1

print(count)

const solution = (n, m) => {
    let count = 0;
    while (n > 1) {
        if (n % m !== 0) {
            count += 1;
            n -= 1;
        } else {
            count += 1;
            n = n / m;
        }
    }
    return count;
}

console.log(solution(17, 4));