이것이 코딩테스트다 3일차 - 그리디

1. 그리디란?

현재 상황에서 지금 당장 좋은 것만 고르는 방법
따라서 최적의 해가 나오지 않을 때가 많다

사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형
(정렬, 최단경로 등은 이미 알고리즘 사용법을 정확히 알아야 한다.)

최단경로 문제는 플로이드워셜 or 다익스트라를 이미 알고 있어야 한다
(다익스트라 알고리즘은 그리디 알고리즘으로 분류되긴 한다)
다만, 그리디 알고리즘 자체가 문제 출제의 폭이 매우 넓어서 단순 암기만으로는 안 된다
많은 유형을 풀어봐야 한다! 훈련! 창의력, 문제를 풀기위한 최소한의 아이디어를 떠올리는 능력을 요구한다.

1.1 문제가 이렇게 나오면 그리디를 고려하자

• 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀수 있을 때
• 알게모르게 가장 큰 순서대로, 가장 작은 순서대로와 같은 기준을 알게 모르게 제시해준다. 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 자주 정렬 알고리즘과 짝을 이뤄 출제된다.

1.2 거스름돈 문제

문제

거스름돈 : 500원, 100원, 50원, 10원
N원을 거슬러줘야할 때 동전의 최소개수를 구하라

해설

내 생각 : N을 500원부터 나눠서 몫을 count++, 나머지를 나눠서 몫을 count++ N이 0이되면 return count

구현

n = 1260
count =0

#sort
coin_types=[500,100,50,10]

for coin in coin_types :
    count+= n // coin 
    n %= coin

print(count)

시간복잡도 : 코인의 종류가 n개라고 할 때 O(n) / 금액의 크기와 무관

1.3 그리디 알고리즘의 정당성

가장 큰 화폐단위부터 돈을 거슬러주는 것 같이 탐욕적으로 그 순간만 만족하면 될 때
BUT 거스름돈 문제에서는 화폐의 단위가 작은 단위의 배수형태이므로 그리디가 가능한 것. 아니라면,, 제일 큰 화폐단위부터 다 방문해봐야 함..? 너무하네 (동적프로그래밍으로 가능..)
그리디는 쉽게 떠오를 수는 있지만 그게 정당한지 재차 고민해봐야 한다

1.4 실전문제

1.4.1 큰 수의 법칙

문제 : 주어진 수들을 M번 더하여 가장 큰수를 만드는 법칙. 단, 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과해서 더해질 수 없다. 단, 서로 다른 인덱스에 해당하는 수가 같은 경우에는 서로 다른 것으로 간주한다.

해결 : 그리디
내생각
1. 내림차순 정렬
2. if list[0]!=list[1] 이면 (list[0]+list[1])*(N//(K+1))+ list[0]*(N%(K+1))
또는 list[0]을 3번 더하고list[1]을 한번씩더하는 것을 반복한다
3. if list[0]==list[1] 이면 return list[0]*M
또는 list[0]을 3번 더하고list[1]을 한번씩더하는 것을 반복한다
4. 근데 다 정렬할 필요는 없지 않나. 정렬 오래걸림..이지만 파이썬 정렬은 O(NlogN) 이라 괜츈… 암튼 Max와 SubMax를 뽑아서 list로 만들면 된다. Max를 뽑.. (GOOD!)
5. 그리디 알고리즘으로 풀 경우일 때는..

우와 뭐 대충 맞춤!! 신난다!!

일단 구현은 나중에.. 알고리즘을 떠올리는 것 부터 할게요… 안녕~