그리디(Greedy) 알고리즘?

• 그리디 알고리즘이란 어떠한 문제가 있을 때 단순 무식하게, 탐욕적(greedy)으로 문제를 푸는 알고리즘을 말합니다. 여기서 탐욕적이라는 말은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미합니다.

그리디 알고리즘은 정렬, 최단경로 등의 다른 알고리즘과 비교했을 때 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 유형이라는 특징이 있습니다. 따라서 코딩테스트에서 그리디 알고리즘 유형의 문제는 창의력, 즉 문제를 풀기위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구합니다.

그리디 알고리즘은 (가장 큰/작은 순서대로오와 같이) 기준에 따라 좋은 것을 선택하는 알고리즘이므로 대체로 정렬 알고리즘과 자주 짝을 지어 출제되는 경향이 있습니다.

문제 풀이

1. 만들 수 없는 금액

from itertools import combinations

n = int(input())
coins = list(map(int, input().split()))
coins.sort()

storage = set()
expectValue = 1
for i in range(1, len(coins)+1):
    for nCi in combinations(coins, i):
        sum = 0
        for num in nCi:
            sum += num
        if (expectValue == sum) | (expectValue in storage):
            expectValue += 1
        elif expectValue < sum:
            storage.add(sum)

print(expectValue)

코드설명

2. 무지의 먹방 라이브 (문제풀기)

풀이 1) 정확성 테스트는 모두 통과했지만, 무식한 방법이므로 효용성 테스트는 시간초과로 0점이다.

def solution(food_times, k):
    answer = 0
    lastIndex = len(food_times) -1
    i, time = 0, 0
    
    # 더 섭취할 음식이 없는 경우 확인
    if sum(food_times) <= k:
        return -1
    
    while time <= k:
        if food_times[i] > 0:
            if time == k: # 통신이 끊긴 후 음식을 먹으면 안되므로 break
                break
            food_times[i] -= 1  
            time += 1
        if i == lastIndex:
            i = 0
        else:  
            i += 1
            
    answer = i + 1
                   
    return answer

코드설명

(효용성 테스트도 통과하도록 다시 생각해봐야겠다!)

Ref

이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈)

#알고리즘