그리디 알고리즘 개념정리와 문제

✏️ 그리디 알고리즘

간단하게 이야기하면 뒷 일은 생각안하고 당장에 눈 앞에 있는 것중에 가장 좋은 것만을 택하는 알고리즘이라고 볼 수 있다. 

그리디 알고리즘과 최적경로

시작점부터 시작해서 가장 큰수를 얻어야하는 문제가 있다. 여기서 노란색 화살표로 표현된 것이 그리디 알고리즘, 주황색 화살표로 표현한 것이 최적해이다. 처음에 10을 거쳐야 가장 큰 수인 500을 얻을 수 있지만 그리디 알고리즘은 당장에 가장 큰 수인 15를 먼저 선택했기떄문에 20을 출력하게 된다. 그리디(Greedy)알고리즘은 이처럼 최적해를 보장해주지 않는다.

 

 

✏️ 그리디 알고리즘의 사용조건

첫째.

그리디 알고리즘은 최적해를 보장해주지 않는다고 했다. 즉, 그리디 알고리즘을 이용했을때 최적해가 나오는 문제에 그리디알고리즘을 이용할 수 있다. 이를 만족시킬 조건들이 주어질 것이다.

 

둘째.

현재의 선택이 이후의 선택에 영향을 주어서는 안된다.

 

✏️ 그리디 알고리즘을 이용하는 문제

https://www.acmicpc.net/problem/11047

11047번: 동전 0

백준11047번

 

대표적으로 백준 11047 '동전 0' 문제가 있다.

주어진 조건(1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)을 보면 큰 동전이 모두 작은 동전의 배수가 됨을 알 수 있다. 따라서 그리디 알고리즘을 적용할 수 있을 것이다.

 

아이디어는 다음과 같다. 동전가치를 내림차순으로 재정렬하고 K와 동전가치리스트의 원소를 순차적으로 비교하여 K보다 작은 원소의 값을 K에서 빼서 K에 저장한다. 이런 연산을 외부변수에 저장해 연산횟수를 출력할 것이다.

N, K=list(map(int,input().split()))
coin=[]
for _ in range(N):
  coin.append(int(input()))
coin=sorted(coin, reverse=True)

cnt=0
while(K>0):
  for value in coin:
    if value<=K:
      K=K-value
      cnt+=1
      break
    else:
      del coin[0]
      break

print(cnt)

시간초과

무지성으로 짰더니 시간초과다. 반복문을 두개나 썼더니 시작복잡도가 너무 컸던 모양이다. 

값을 하나씩 빼서 연산을 하나씩 카운트할 필요없이 나눠서 몫을 카운트하면 반복문을 위에처럼 할 필요가 없다.

N, K=list(map(int,input().split()))
coin=[]
for _ in range(N):
  coin.append(int(input()))
coin=sorted(coin, reverse=True)

cnt=0
for i in range(N):
  cnt+=K//coin[i]
  K=K%coin[i]

print(cnt)