그리디 Greedy
현재 상황에서 가장 좋아보이는 것만을 선택하는 알고리즘
Greedy를 단어 그대로 번역하면 탐욕법이다. 이름에서 알 수 있듯이 문제를 풀 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다.
그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향은 고려하지 않는다.
예제 1) 거스름돈
Q. 500원, 100원, 50원, 10원짜리 동전으로 손님에게 1260원을 거슬러 줘야 할 때 거슬러 줘야 할 동전의 최소 개수
A. 가장 큰 화폐 단위부터 돈을 거슬러준다.
1. 남은 돈 : 1260원 -> 500원짜리로 2개까지 거슬러 줄 수 있음 (1260 - 1000 = 260원)
2. 남은 돈 : 260원 -> 100원짜리로 2개까지 거슬러 줄 수 있음 (260 - 200 = 60원)
3. 남은 돈 : 60원 -> 50원짜리로 1개까지 거슬러 줄 수 있음 (60 - 50 = 10원)
4. 남은 돈 : 10원 -> 10원짜리로 1개까지 거슬러 줄 수 있음 (10 - 10 = 0원) 끝!
==> 총 거슬러 줘야 할 동전의 최소 개수는 6개
예시 코드
def solution(money):
coin = [500, 100, 50, 10]
N = money
cnt = 0
remain = N
for i in coin :
cnt += remain // i
remain = remain % i
print(cnt)그리디 알고리즘의 정당성
그리디 알고리즘을 모든 알고리즘 문제에 적용할 수 있는 것은 아니다. 대부분의 문제에서 그리디 알고리즘은 최적의 해를 찾기 어렵다. 어떤 문제에 그리디 알고리즘을 사용할 때에는 그것이 정당한지 검토할 수 있어야 답을 도출할 수 있다. 위에 예시로 든 거스름돈 문제에서는 큰 단위가 항상 작은 단위의 배수 형태이므로 그리디 알고리즘을 사용하면 최적의 해를 사용할 수 있었지만 화폐의 단위가 서로 배수 형태가 아닌 무작위인 경우에는 그리디 알고리즘을 사용하면 최적의 해를 구할 수 없다.
실전 문제
1. 큰 수의 법칙
다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙
단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과해 더할 수는 없다.
입력 조건
- 첫째 줄에 N(2 <= N <= 1,000), M(2 <= M <= 10,000), K(1 <= K <= 10,000)의 자연수가 주어지며,각 자연수는 공백으로 구분한다.
- 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10,000이하의 수로 주어진다.
- 입력으로 주어지는 K는 항상 M보다 작거나 같다.
출력 조건
- 첫째 줄에 동빈이의 큰 수의 법칙에 따라 더해진 답을 출력한다.
풀이
- 입력받은 N개의 자연수를 정렬한다.
- 가장 큰 수를 K번 더한다.
- 두번째로 큰 수를 한번 더한다.
- 2번과 3번 과정을 더하는 횟수가 M번 될때까지 반복한다.
예시 코드
# N : 배열의 크기
# M : 숫자가 더해지는 횟수
# K : 한 숫자가 연속해서 더해질 수 있는 최대 횟수
N, M, K = map(int, input().split())
result = 0
num = list(map(int, input().split()))
num.sort(reverse=True)
for i in range(M):
for j in range(K):
if M == 0 : break
result += num[0]
M -= 1
if M == 0 : break
result += num[1]
M -= 1
print(result)2. 숫자 카드 게임
숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다.
1. 숫자가 쓰인 카드들이 N X M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다.
2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.
3. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.
4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다.
문제
카드들이 N X M 형태로 놓여 있을 때, 게임의 룰에 맞게 카드를 뽑는 프로그램을 만드시오.
입력조건
첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. (1 <= N,M <= 100)
둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1 이상 10,000 이하의 자연수이다.
출력조건
첫째 줄에 게임의 룰에 맞게 선택한 카드에 적힌 숫자를 출력한다
입력예시
3 3
3 1 2
4 1 4
2 2 2
출력예시
2
풀이
- N만큼 반복해서 list로 입력을 받고 그 리스트의 첫번째 값을 key값으로, 가장 작은 값을 value값으로 갖는 dictionary를 만들었다.
- dictionary를 value 기준으로 하여 내림차순 정렬한 뒤 가장 첫번째 key값을 출력하였다.
예시 코드
N, M = map(int,input().split())
dic = {}
for i in range(N):
lst = list(map(int, input().split()))
dic[lst[0]] = min(lst)
dic = sorted(dic.items(), reverse=True)
print(dic[-1][0])
3. 1이 될 때까지
어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은
N이 K로 나누어떨어질 때만 선택할 수 있다.
1. N에서 1을 뺀다.
2. N을 K로 나눈다.
문제
N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오.
입력 조건
- 첫째 줄에 N(2 <= N <= 100,000)과 K(2 <= K <= 100,000)가 공백으로 구분되며 각각 자연수로 주어진다.
- 이때 입력으로 주어지는 N은 항상 K보다 크거나 같다.
출력 조건
- 첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다.
입력 예시
25 5
출력 예시
2
풀이
- 문제에서 알 수 있듯이 N이 K로 나누어 떨어질 때만 N/K를 해주고
- 그렇지 않을 경우에는 N에서 1을 빼주었다.
Python 예시 코드
N, K = map(int,input().split())
result = 0
while(N != 1):
if( N>=K and N % K == 0):
N = N/K
result += 1
else :
N -= 1
result += 1
print(result)cpp 예시 코드
#include <iostream>
using namespace std;
int main(){
int N, K;
int result = 0;
cin >> N >> K;
while (N != 1){
if(N%K == 0){
result ++;
N = N/K;
}
else{
result ++;
N --;
}
}
cout << result << endl;
}