이코테 2021 - 그리디 (탐욕법)

- 현재 상황에서 지금 당장 좋은 것만 고르는 방법 (= 탐욕법)

- 단순히 가장 좋아보이는 것만 반복적으로 고르는 것이 맞는가?

> 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다.

 

대표문제 1

N= 1,260일때 500*2 + 100*2 + 50*1 + 10*1

큰 단위의 화폐부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유는?

> 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른해가 나올 수 없기 때문이다

n = 1260
count = 0

# 큰 단위의 화폐부터 차례대로 확인하기
array = [500, 100, 50, 10]

for coin in array:
	count += n//coin # 해당화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n%= coin

print(count)

> 이 알고리즘의 시간 복잡도는 거슬러줘야하는 금액과는 무관하며, 동전의 총 종류에만 영향을 받는다.

 

 

대표문제 2

if 문을 사용하는 것 보다 로그시간복잡도로 빨리 실행됨 (실행시간 감소)

 

 

풀어보기

s = input()
s = '*'.join(s)

for i in range(1,len(s),2):
	if int(s[i-1]) <= 1 or int(s[i+1]) <= 1:
    	s[i] = '+'

# 계산하기
result = eval(s)
print(result)

> 오답! 연산자 상관없이 앞에서부터 계산한 결과가 나와야 함!!

정답

 

 

 

 

아래 영상을 참고하였습니다