Greedy Algorithm

1. Greedy 알고리즘이란?
   그리디 알고리즘은 단순하고도 강력한 문제 해결 방법이다.
   어떠한 문제를 단순 무식, 탐욕적인 방법으로 문제를 해결하는 알고리즘.
   탐욕적이란 말은 현재 상황에서 지금 당장 좋은 것만을 고르는 방법을 의미한다.
   여기서 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

   코딩테스트에서의 그리디 알고리즘 문제 유형은 사전에 암기를 하고 있지 않아도 풀
   수 있는 문제들이 대다수이다.(예외로 다익스트라 알고리즘은 암기가 필요하다.)
   보통의 그리디 알고리즘 문제에서 요구되는 능력은 창의성 이다.
   즉, 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있으면 해결이 가능한 문제들
   이다.

   그리디 알고리즘은 간편하지만 치명적이다. 탐욕적으로 문제를 해결할 수 있다는 보장이 있다면 효과적이고 직관적이지만 대부분의 경우에는 최적의 해를 찾지 못한다.
   따라서 그리디 알고리즘으로 해법을 찾았을 경우 그 해법의 정당성을 검토해야한다.

   tip❗
   코딩테스트 시 문제의 유형이 바로 보이지 않을 경우에 그리디 알고리즘을 먼저 의심해보고 고민해보기
   그리디 알고리즘은 그 자체로 나오는 경우보다 정렬 알고리즘과 함께 출제되는 경향이 있다.
   따라서 정렬, 다익스트라 알고리즘은 기본적으로 숙지할 것!
   주로 카카오 기업 코딩테스트에서 종종 출제된다.

2. Greedy Algorithm 예제
   2-1

   거스름돈 예제
   500,100,50,10의 단위로 무한개의 동전이 존재할 때, N원 가격의 물건을 M개의
   동전으로 구매하려 할때 M의 최솟값은? 단, N은 항상 10의 배수이다.

solution
가장 기초적인 그리디 알고리즘 문제이다.
금액을 가장 큰 금액의 동전으로 먼저 나누어서 계산한다.라는 아이디어를 통해 문제를 해결 할 수 있다.

coin = [500,100,50,10]

n = int(input())

total = 0
for i in range(4):
    total += int(n/coin[i])
    n = int(n%coin[i])
print(total)

2-2

큰 수의 법칙
n 개의 숫자로 이루어진 배열이 있다. 이 배열안의 숫자들을 중복을 허용하여 m번 더했을 때
나올 수 있는 가장 큰 수를 구해라. 이때 배열의 특정한 인덱스에 해당하는 숫자는 연속으로
k번을 초과하여 더해질 수 없다.

solution
이 문제는 배열에서 가장 큰 수와 그 다음으로 큰 수 2개만 골라낼 수 있으면 쉽게 풀 수 있는 문제이다. 배열을 오름차순으로 정렬 한 뒤 가장 큰 수(a)와 그 다음으로 큰 수(b)를 골라낸다. 인덱스가 다르므로 두 수의 크기가 같아도 상관없다. 특정 인덱스의 수는 k번을 초과하여 더할 수 없으므로 전체 더하는 횟수 m에서 (k+1)을 나눈 몫만큼 b를 더하고 그 몫의 3배 만큼 a를 더하면 된다. 그 뒤 m에서 (k+1)을 나눈 나머지만큼 a를 더해주면 답이 나온다.

n,m,k = map(int,input().split())
answer =0
num=list(map(int,input().split()))
num.sort()

a = num[n-1]
b = num[n-2]

cnt = int(m/(k+1))

answer += a * cnt*3
answer += b*cnt
answer += a * int(m%(k+1))

print(answer)

2-3

숫자 카드 게임
숫자가 적힌 카드가 NxM 형태로 놓여져 있다.
먼저 봅고자 하는 카드의 행을 선택한다.
선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑는다.
위의 룰에 맞게 카드를 뽑았을 때 가장 큰 수를 뽑는 경우가 정답이다.

solution
문제는 간단하다. 각 행 별로 가장 작은 수를 뽑아서 리스트에 담은 후 그 중 가장 큰 수를 출력하면 된다.

n,m = map(int,input().split())

graph=[]
for _ in range(m):
    graph.append(list(map(int,input().split())))

answer =[]
for i in graph:
    answer.append(min(i))
print(max(answer))

2-4

1이 될 때까지
어떠한 수 n이 1이 될 때까지 다음의 두 과정 중 하나를 선택하여 반복할 수 있다.
1.n에서 1을 뺀다.
2.n을 k로 나눈다.
단, 두번째 연산은 n이 k로 나누어떨어질 때만 사용 가능하다.
이 때 n을 1로 만드는 최소 연산 횟수를 구해라
(2 <= n <= 100000, 2 <= k <= 100000)

solution
이 문제 또한 간단하게 해결 가능한 문제이다. k가 2 이상이므로 최소 연산 횟수는 최대한 많이 나눌수록 작아진다.

n,k = map(int,input().split())

cnt = 0
while True:
    if n == 1:
        break
    
    
    if n%k == 0 and n>=k:
        n = int(n/k)
        cnt += 1
    else:
        n -= 1
        cnt += 1
    
    
print(cnt)

출처
이것이 취업을 위한 코딩 테스트다 with 파이썬
저자 나동빈

이 글은 위 서적을 바탕으로 학습하기 위해 작성되었습니다.