[백준 11047번] 그리디 알고리즘 / Greedy Algorithm

 

 

" The present is more important than the future. "

 

 

📍그리디 알고리즘(Greedy Algorithm)

: 지금 이 순간의 최적인 답을 선택하는 알고리즘 설계 기법이다.

 즉, 미래보다 현재의 이익을 추구한다고 생각하면 이해가 쉽다.

 

 

그런데 현재의 이익만 추구하는 것이므로 최적의 정답이 아닐 수 있다.

 

 

📍그럼 왜 그리디 알고리즘을 사용할까?

: 이 순간의 최선의 선택을 하므로 성능이 빠르다!

 그렇기 때문에 최적의 정답에 가까운 근사적인 답을 내릴 수 있다.

 

 

 

[ 백준알고리즘 11047번 - 동전0 ]

 

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

11047번: 동전 0

 

(오답)

문제: 시간 초과

틀린 이유: 이미 비교한 동전 가치들은 다시 확인할 필요가 없다. 그런데 나는 모든 동전 가치와 비교하려고 했다.

n,k=map(int, input().split())
ans=0
money=k
vals=[]
for i in range(n):
    vals.append(int(input()))

while money!=0:
    for i in range(n-1,-1,-1):
        if vals[i]<money:
            ans+=money//vals[i]
            money-=(money//vals[i])*vals[i]
            break
        else:
            continue

print(ans)

 

(정답)

n,k=map(int, input().split())
ans=0
vals=[]
for i in range(n):
    vals.append(int(input()))

vals.sort(reverse=True)

for i in vals:
    if k==0:
        break
    ans+=k//i
    k%=i

print(ans)

 

(정답2)

n,k=map(int, input().split())
ans=0
vals=[]
for i in range(n):
    vals.append(int(input()))

while k>0:
    v=vals.pop()  
    ans+=k//v
    k%=v

print(ans)

 

 

<공부>

 

◾ 리스트의 순서를 역으로 읽고 싶은 경우 list.sort(reverse=True) 를 사용하면 편리하다.

 

◾ 자신보다 큰 수로 나눴을 때 몫은 0이 된다.

    ex. print(400//100)=4

    ex. print(400//500)=0

 

◾ pop(i): i번째 리스트 요소를 꺼내면서 동시에 삭제시킨다.

test=['가방','나비','다람쥐']

print(test.pop(0))  #가방
print(test)  #['나비', '다람쥐']

 

 

◾ pop(): (인덱스를 지정하지 않으면) 리스트의 마지막 항목을 꺼내면서 동시에 삭제시킨다.

test=['가방','나비','다람쥐']

for i in range(3):
	print(test.pop())

#다람쥐
#나비
#가방