그리디

그간 코딩 테스트를 좀 주먹구구식으로 풀었다. 

그러다보니 특정 알고리즘 문제를 풀어도, 내가 얼마만큼 왔고 어느정도 더 해야하는지 감이 잘 안잡혔다. 

이를 위해 1독을 목표로 한 책을 선정했다. 바로 나동빈씨의 "이것이 취업을 위한 코딩 테스트다" 라는 책이다. 

 

그 중 첫 쳅터인 그리디이다. 

 

그리디

1) 어떠한 문제가 있을 때 단순 무식하게, 현재 상황에서 지금 당장 좋은 것만 고르는 방법

2) 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 

 

그리디는 다익스트라와 같이 암기 기반 알고리즘과 다르게 출제 폭이 럽어 단순 암기가 불가능하다. 

즉 다양한 문제를 접해봐야한다. 

 

그리디 알고리즘은 기준에 따라 좋은 것을 선택하므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다. 

$\rightarrow$ 이 경우, 정렬 알고리즘과 짝을 이뤄 출제되기도 한다. 

 

예를 들어 거스름돈 문제가 있다고 하자. 

계산 가능한 동전이 500원, 100원, 50원, 10원이 있다고 할 때, N 원을 계산하기 위한 동전의 최소 개수를 구한다고 해보자. 

 

여기서 힌트는 최소 개수이고, 생각을 해보면 가장 효과적인 금액부터 순차적으로 처리해도 구하고자한 최선 결과에 영향을 끼치지 않는다. 

다만, 이와 같이 최적의 해를 그리디를 통해 찾을 수 없는 경우는 너무 다양하고, 이 경우 그리디를 사용할 수 없다. 

$\rightarrow$ 즉, 그리디 해법이 정당한지 늘 검토해야한다. 

예를 들어 800원을 계산할 때 주어진 동전 단위가 500원, 400원, 100원이라면 그리디 알고리즘은 500, 100 * 3 개를 선택하는 반면 최선의 결과는 400 + 400 이다. 

다음과 같은 거스름 돈 문제에서는 동전의 단위가 서로 배수형태가 아니면 그리디로 해결 불가능하다. 이 경우에는 다이나믹 프로그래밍으로 해결을 해야한다. 

 

책에 제공 된 3문제를 풀어보자. 

 

1) 큰 수의 법칙 

다양한 수로 이루어진 배열이 있을 때, 주어진 수들을 M 번 더하여 가장 큰 수를 만드는 법칙

배열이 특정한 인덱스에 해당하는 수가 연속해서 K 번을 초과해서 더해질 수 없다. 

ex) 

M: 8, K: 3

[2, 4, 5, 4, 6] 

특정한 인덱스가 3번까지만 더해질 수 있으므로 

6 + 6 + 6 + 5 + 6 + 6 + 6 + 5 = 46

 

단, 서로 다른 인덱스인 경우 다른 것으로 간주한다. 

[3, 4, 3, 4, 3]

4+4+4+4+4+4+4+4 = 28

 

import sys
input = sys.stdin.readline

a, M, K = map(int, input().split())
lst = sorted(list(map(int, input().split())))

#간단하게 생각하면 같은 값이 있다고 해도 염려말고 항상 범용적으로 
#가장 큰거 3번, 그다음 큰거 1번 이런식으로 하면 된다. 

ans = (M // (K + 1)) * (lst[-1]* 3 + lst[-2]) + (M%(K+1)) * lst[-1]

 

주의할 점 

# input = sys.stdin.readline()

# input 은 한번 호출하면 끝난다. 

# input = sys.stdin.readline 이 의도대로 동작 

 

 

2) 숫자 카드 게임

N X M (N: 행 M: 열)  카드가 있다. 특정 행에서 고른 가장 작은 수가, 각 행 별 가장 작은 수중에서는 가장 큰 수가 되도록하는 수를 찾아라. 

 

import sys
input = sys.stdin.readline

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

ans = 0 
for i in range(n):
    ans = max(ans, min(list(map(int ,input().split()))))

print(ans)

 

3) 1 이 될 때까지

N이 1이 될 때 까지 다음의 두 과정 중 하나를 반복적으로 수행. 단 두번 째 연산은 N 이 K 로 나눠질 때만 선택 가능 

1. N 에서 1을 뺸다. 

2. N을 K로 나눈다. 

 

최소횟수는? 

import sys 
input = sys.stdin.readline

N, K = map(int , input().split())

ans = 0

while( N!= 1 ):
    ans += 1
    if N % K == 0:
        N = N/K
    else:
        N -= 1 

print(ans)

다만 위 방법은 만약 K 가 엄청나게 큰 수일 경우, 계산상의 약간의 손해가 있을 수 있다. 

하지만 비교 과정 자체가 더 손해일 것으로 보인다.