[알고리즘] 그리디 알고리즘과 예제

그리디 알고리즘: 탐욕법. 현재 상황에서 지금 당장 좋은 것만 고르는 방법. 

문제 유형 파악 어려울 때는 그리디 알고리즘을 의심하고, 탐욕적 해결법이 존재하는지 고민한다. 그럼에도 없다면 DP, 그래프 등을 고민한다.

 

 

#예제1. 거스름돈. 500/100/50/10원 무한히 존재. 거슬러줘야할 동전의 최소 개수 구하기.
#--> 가장 큰 화폐 단위부터 거슬러 주기.

n = input()
count = 0

coins = [500, 100, 50, 10];

for coin in coins:
  count += n //coin
  n %= coin

print(count);

 

# 예제2. 큰수의법칙
# n개의 수에서 k만큼 반복할 수 있고, m번 더해서 가장 큰 수 구하기.

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

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

count = int(m/(k+1))
result = 0
result = first*(count*k + m%(k+1)) + second*count

print(result)

 

# 예제3. 숫자 카드 게임
# N행 M열. 선택된 행에 포함된 카드 중 가장 숫자 낮은 카드 뽑아야 한다. 이 때, 뽑을 수 있는 가장 높은 숫자를 구하라.

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)

 

 

#예제4. 1이 될 때까지

# N에서 1 뺀다 / N K로 나눈다. 이 두 과정을 N이 1이 될 때까지 수행해야 하는 최소 횟수.

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

while 1:
    if n < k:
        break
    if n%k == 0:
        n //= k
        count+=1
    else:
        count += n%k
        n -= n%k
        
        
count += n-1

print(count)

 

 

 

 

 

참고자료 : 이것이 바로 취업을 위한 코딩테스트다 (나동빈)