[Algorythm] 그리디 알고리즘

Greedy algorythm

: 지역 최적해를 추구하는 알고리즘. 매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 결과를 도출한다.

 

1) 최적해를 보장하는 상황

1. 최적 부분 구조: 부분해를 푸는 과정이 최적해를 구하는 과정과 일치
2. 그리디 선택 속성: 선택 과정이 다른 과정에 영향을 주지 않음

 

2) 최소신장 구조

: 그리디 알고리즘을 사용하는 대표적 트리형태 자료구조로, 신장 트리 중 간선 가중치 합이 최소인 것. 그리디 알고리즘 중에서도 1) 프림 알고리즘과 2) 크루스칼 알고리즘을 사용

신장트리: 모든 정점이 간선으로 연결되어 있고 간선 구조가 정점 갯수보다 하나 적은 그래프

1. 프림 알고리즘 O(E*logV)
   1. 임의의 정점 하나를 선택해 최소 신장트리에 추가
   2. 최소 신장트리와 연결된 정점 중 가장 가중치가 적고, 순환을 형성하지 않는(차라리 한 정점을 다수 정점과 연결) 정점을 최소 신장 트리 확장(그리디 선택적 추가)
   3. 신장 트리 조건 만족 시까지 위 조건 반복
2. 크루스칼 알고리즘 O(E*logV)
   1. 그래프 모든 간선을 가중치 기준 오름차순 정렬
   2. 다음으로 최소 가중치를 갖으면서 순환을 형성하지 않는(차라리 한 정점을 다수 정점과 연결) 정점을 최소 신장 트리에 추가(그리디 선택적 추가)
   3. 신장 트리 조건 만족 시까지 위 조건 반복

 

1. 11047번 동전 0

# five_mil = m//50000
# one_mil = m%50000//10000
# five_tho = m%10000//5000
# one_tho = m%5000//1000
# five_hun = m%1000//500
# one_hun = m%500//100
# fifty = m%100//50
# ten = m%50//10
# five = m%10//5
# one = m%10%5

#0
import sys

n, m = map(int, sys.stdin.readline().split())
arr = list(map(int, list(sys.stdin.readline() for _ in range(n))))
sorted_arr = sorted(arr, reverse = True)

result = 0

for i in sorted_arr:
    temp = m//i
    result.append(temp)
    m -= temp*i

print(sum(result))


#0-1
import sys

n, m = map(int, sys.stdin.readline().split())
arr = [int(sys.stdin.readline()) for _ in range(n) ]
arr.reverse()

result = 0

for i in arr:
    result += m//i
    m = m % i

print(result)


#1
N, K = map(int, input().split())
coins = [int(input()) for _ in range(N)]
coins.reverse()
cnt = 0

for each_coin in coins:
    cnt += K//each_coin # K%pre_coin//post_coin. 간결하고 멋지다
    K = K%each_coin 

print(cnt)


#2 그리디
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
coins = [int(input()) for _ in range(N)]
count = 0

for coin in coins[::-1]:
    pos = K // coin
    if pos:
        K -= coin * pos
        count += pos
    if K == 0:
        print(count)
        break


#3 그리디
from sys import stdin

coin = []
count = 0

N, M = map(int,stdin.readline().split())

for i in range(N):
    coin.append(int(stdin.readline()))

coin.sort(reverse=True)

for value in coin:
    count = count + (M//value) # 필요한 코인수 count
    M = M % value # 쓰고 남은 돈 
    if(M <=0):
        break

print(count)

 

• 처음에는 동전 유형을 정해준 줄 알았는데 그것마저 변수였어서 틀렸다(하지만 이 때 찾은 규칙이 오히려 풀이에 도움이 됐다).

  

• reverse(), reverse=True, int(sys.stdin.readline())를 깜빡했다. 정렬과 입력값 받기는 자주 상기할 것

※ Greedy

거스름돈이 배수 관계이고, (화폐 갯수 제한이 없다면) 그리디 알고리즘으로 (더 쉽게) 해결 가능하다. 가지고 있는 동전 중 큰 단위가 항상 작은 단위의 배수일 때, 작은 단위의 동전을 종합해 다른 해가 나올 수 없기 때문이다. 따라서 가장 큰 동전단위 단위부터 시작하여 계산하면 필요한 동전 개수의 최솟값을 구할 수 있다.

 

동전의 종류가 N개일때, 시간 복잡도는 O(N^2)이다.

1. 그리디로 풀 때는 가장 큰 동전을 고르고, 이 동전을 사용한 만큼 기존 값을 조정한다. 
2. 이 과정은 각 단계마다, 그 단계에서 최선이라고 생각되는 경우를 실행하는 것이고, 실행이 반복되면서 얻은 결과가 general optimal solution이 될 때까지 반복한다.

  기존 풀이와 차이가 있다면 최적의 해를 구하는 실행을 general optimal solution을 마주칠 때까지 반복한다는 것이다. 따라서 최적해를 구하는 실행을 반복해  general optimal solution를 구할 수 있다면 그리디 알고리즘으로 풀 수 있는 문제라고 할 수 있다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

참고문헌

[백준] [파이썬/Python] 11047번: 동전0 풀이 / 그리디알고리즘 설명 / sort()/내림차순 정렬

[백준 11047 파이썬] 동전 0 (실버2, 그리디)