그리디 알고리즘

그리디 알고리즘이란?

사전적 의미로 Greedy는 탐욕적이라는 뜻을 가지고 있다. 이름에서 알 수 있듯이 탐욕적으로 풀어나가는 알고리즘이다. 탐욕적으로 풀어 나간다라는 말은 문제를 접근할때 순간 가장 좋은 것을 먼저 선택하고, 이 선택이 나중에 미칠 영향에 대해서는 고려하지 않는 것이다.

특징

사전에 외우고 있지 않아도 풀 수 있는 가능성이 높다.
정렬 알고리즘을 써야하는 경우가 많다.
최적의 해를 찾을 수 없을 가능성이 높다.

정당성 확인

그리디 알고리즘으로 해법을 찾았을 때는 정당한지 검토가 필요하다.
예를들어, 거스름돈 같은 문제에서 800원을 500, 400, 100원을 이용하여 푼다고 가정해보자. 그리디 알고리즘을 이용하면 500, 100, 100, 100원으로 4개가 정답이지만 최적의 해는 400, 400원으로 2개이다. 따라서 최소한의 아이디어를 떠올리고 정당한지 검토할 수 있어야 답을 도출할 수 있다.

문제 파악

문제 유형이 파악이 안될 경우 그리디 알고리즘 -> 다이나믹 프로그래밍 -> 그래프… 순으로 생각하면서 문제에 접근하는 것도 하나의 방법이다.

예제

큰 수의 법칙

문제

여기서 큰 수의 법칙이란 다양한 수로 이뤄진 배열이 있을 때 주어진 수들을 M번 더해 가장 큰 수를 만드는 법칙
단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과할 수는 없음

입력 조건

첫째 줄에 N(2<=N<=1000), M(1<=M<=10000), K(1<=K<=10000)의 자연수가 주어지며 각 자연수는 공백으로 구분

둘째줄에 N개의 자연수가 주어짐. 각 자연수는 공백으로 구분. 단, 각각의 자연수는 1이상 10000이하의 수로 주어짐

입력으로 주어지는 K는 항상 M보다 작거나 같다.

출력 조건

첫째 줄에 큰 수의 법칙에 따라 더해진 답을 출력

해결 방법

가장 큰 수와 두번째로 큰 수를 찾고 가장 큰 수를 K번 더하고 두번째로 큰 수를 1번 더하는 방법을 반복하면 된다.

import sys
N, M, K = map(int, sys.stdin.readline().split())
num_list = list(map(int,sys.stdin.readline().split()))
num_list.sort(reverse=True)
first = num_list[0]
second = num_list[1]
ans = 0
count = 0
while True:
    for _ in range(K):
        if M == 0:
            break
        ans += first
        M -= 1
    if M == 0:
        break
    ans += second
    M -= 1
print(ans)

M의 크기가 100억 이상처럼 커질 경우 시간초과 문제가 있으므로 최적화 진행

우선 반복되는 수열에 대해서 파악 (6 + 6 + 6 + 5)
반복되는 수열의 길이는 (K + 1)
M을 (K + 1) 로 나눈 몫이 반복되는 수열의 횟수 M / K+1 = 2
다시 여기에 K를 곱해주면 가장 큰 수가 등장하는 횟수 (M / K+1) * K = 6
만약 M이 (K + 1) 로 나누어떨어지지 않는 경우 (M % K+1) = 0
가장 큰 수가 더해지는 횟수(4번 + 5번의 합)
```
int(M / (K + 1)) * K + M % (K + 1) 
```

최종 코드

import sys
N, M, K = map(int, sys.stdin.readline().split())
num_list = list(map(int,sys.stdin.readline().split()))
num_list.sort(reverse=True)
first = num_list[0]
second = num_list[1]
count = int(M / (K + 1)) * K
count += M % (K + 1)

result = 0
result += (count) * first
result += (M-count) * seconde
print(result)

숫자 카드 게임

문제

여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임
단, 게임의 룰을 지키며 뽑아야함

숫자가 쓰인 카드들이 N X M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하고, M은 열의 개수를 의미
먼저 뽑고자 하는 카드가 포함된 행을 선택
선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑음
처음에 카드를 골라낼 행을 선택할 때, 이후 해당 행에서 가장 숫자가 낮은 카드를 뽑아야 하는 것을 고려해 가장 높은 숫자를 뽑을 수 있도록 해야함

입력 조건

첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어짐
(1 <= N, M <= 100)
둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어짐 각 숫자는 1이상 10000이하의 자연수

출력 조건

첫째 줄에 게임의 룰에 맞게 선택한 카드에 적힌 숫자를 출력

해결 방법

각 행에서 가장 작은 수를 뽑고 그 수에서 가장 큰 수를 출력하면 된다.

import sys

N, M = map(int, sys.stdin.readline().split())
ans = 0
for _ in range(N):
    num = list(map(int, sys.stdin.readline().split()))
    min_num = min(num)
    ans = max(min_num,ans)
print(ans)

1이 될 때까지

문제

어떠한 수 N이 1이 될 때 까지 다음의 두 과정 중 하나를 반복적으로 선택해 수행하려 함
단, 두번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있음

N에서 1을 뺀다.
N을 K로 나눈다. N이 1이 될 때 까지 1번 혹은 2번의 과정을 수행해야하는 최소 횟수를 구하는 프로그램을 작성

입력 조건

첫째 줄에 N(2<= N <= 100000)과 K(2 <= K <= 100000)가 공백으로 구분되며 각각 자연수로 주어짐
이때, 입력으로 주어지는 N은 항상 K보다 크거나 같음

출력 조건

첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력

해결 방법

1을 빼는거 보다 나누는게 수를 줄일 수 있는 가장 최선의 방법이므로 K로 나누어 떨어지면 나누고 아니면 1을 빼면서 수행한다.

import sys

N, K = map(int, sys.stdin.readline().split())
ans = 0
while N > 1:
    if N % K  == 0:
        N = N // K
        ans += 1
    else:
        N -= 1
        ans +=1

print(ans)

서강덕

그리디 알고리즘