(이코테) 이것이 취업을 위한 코딩 테스트다 with 파이썬

[이것이 취업을 위한 코딩테스트다 with 파이썬] - 저자 : 나동빈 

강의 기록

 

그리디 알고리즘 

 

• 그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구함
• 그리디 해법은 그 정당성 분석이 중요함
• 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토 
• 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많음
• 하지만 코딩 테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제됨

 

 

문제상황

1) 루트 노드부터 시작하여 거쳐 가는 노드 값이 합을 최대로 만들고 싶습니다.

    Q. 최적의 해는 무엇인가요?

2) 루트 노드부터 시작하여 거쳐 가는 노드 값이 합을 최대로 만들고 싶습니다. 

    Q. 단순히 매 상황에서 가장 큰 값만 고른다면 어떻게 될까요?

 

문제

당신은 음식점의 계산을 도와주는 점원입니다. 카운터에는 거스름돈으로 사옹할 500원, 100원, 50원, 10원짜리 동전히 무한히 존재한다고 가정합니다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수입니다.

 

해결 아이디어

- 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거슬러주면 됨

- N원을 거슬러 줘야 할 때, 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 줌

  > 이후에 100원, 50원, 10원짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 주면 됨

 

n = 1260
count = 0

array = [500, 100, 50, 10]

for coin in array:
    count += n // coin
    n %= coin
    
print(count)

 화폐의 종류가 K 라고 할 때, 해당 알고리즘의 시간복잡도 : O(K)

 

 

....작성중