📚 그리디 알고리즘
그리디 알고리즘(탐욕법, Greedy Algorithm)이란 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 말한다.
- 그리디 알고리즘은 현재 조건을 선택했다면 다른 조건은 검증하지 않는다.
- 최적해는 보장하지 않는다 그렇기 때문에 정당성 분석을 해줘야한다.
- 코딩테스트에서는 정렬 알고리즘과 짝을 이뤄 출제된다.
시작 지점부터 가장 큰 수를 구하는 문제가 있다고 가정하면
최적의 해는 3-21 이라는걸 알고있지만 그리디를 이용할시 7-12로 이어지는 경로를 가장 큰 수라고 판단을 하게 된다
이처럼 그리디는 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 말한다
📚 예제
📕 거스름돈
당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.
이 문제는 그리디 알고리즘을 이용해 풀 수 있는 대표적인 문제로 간단한 아이디어만 떠올리면 해결할 수 있다. 그것은 바로 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이다.
돈을 거슬러 주는 방법은 여러가지가 있다 예를 들어 10원만 이용해 거슬러 주거나 100원 혹은 다른 조합으로 거슬러 주는방법이 있는데 문제에서 원하는건 최소 개수 이므로 가장 큰 단위의 화폐 부터 거슬러 주는것이다.
#include <iostream>
using namespace std;
int n = 1260;
int cnt;
int coinTypes[4] = {500, 100, 50, 10};
int main(void)
{
for (int i = 0; i < 4; i++){
cnt += n / coinTypes[i];
n %= coinTypes[i];
}
cout << cnt << endl;
}배열에 거스름돈을 넣고 각 배열의 요소를 나눈뒤 몫을 cnt 저장 나머지를 n에 저장후 다음 배열 요소를 참조하는 식으로 만들었다.
📘 큰 수의 법칙
다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다.
배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어진다.
내가 생각한 아이디어는 배열중에서 가장 큰 수를 K번 더하고 그 다음 큰 수를 한번 더하는것을 반복하여 구하는 수가 가장 큰 수이기 때문에 (가장 큰 수 * K + 1) 을 한 묶음으로 생각하여 그 만큼 더해주는식으로 코드를 짰다.
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int N, M, K;
int first, second, a, b, res;
cin >> N >> M >> K;
int *arr = new int[N];
for (int i = 0; i < N; i++)
cin >> arr[i];
sort(arr, arr + N);
first = arr[N - 1];
second = arr[N - 2];
a = first * K;
b = (M / (K + 1));
if (M % (K + 1) == 0)
res = (a * b) + (second * b);
else
res = (a * b) + (second * b) + (first * (M % (K + 1)));
cout << res << endl;
delete arr;
return 0;
}📙 숫자 카드 게임
숫자 카드게임은 여러 개의 숫자 카드중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다
- 숫자가 쓰인 카드들이 N * M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다.
- 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.
- 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.
- 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야한다.
간단한 아이디어로 풀었다 각 행마다 가장 작은 수를 찾고 그 수 중에서 가장 큰 수를 찾는방법으로 풀었다. 처음에는 배열을 이용하여 풀까 하다가 필자는 배열을 끔직히 싫어하므로 그냥 입력 받을때마다 min, max값에다가 저장을 해주었다.
#include <iostream>
using namespace std;
int main()
{
int max = -2147483648;
int N, M, cnt;
cin >> N >> M;
for (int i = 0; i < N; i++)
{
int min = 2147483647;
for (int j = 0; j < M; j++)
{
cin >> cnt;
if (cnt < min)
min = cnt;
}
if (min > max)
max = min;
}
cout << max << endl;
return 0;
}📗 1이 될 때까지
어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두번 째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.
- N에서 1을 뺀다.
- N을 K로 나눈다.
N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오.
주어진 N에 대하여 최대한 많이 나누기를 수행하면 된다
#include <iostream>
using namespace std;
int N, K, count;
int main()
{
cin >> N >> K;
while(true)
{
if (N == 1)
break;
if (N % K == 0)
{
N /= K;
count++;
}
else
{
count += N % K;
N = (N / K) * K;
}
if (N < K)
{
while (N != 1)
{
N--;
count++;
}
}
}
cout << count << endl;
return 0;
}처음에는 단순히 K로 나눠질때는 나누고 그 외에 상황에서는 1을 빼는 식으로 코드를 짰는데 이런 경우 K로 나눠질때까지 반복문을 돌아야 하기 때문에 나눠지지 않는 경우 나머지 만큼 count를 증가시키는 방식으로 바꿨다 그리고 N < K가 되는 시점부터는 따로 예외처리를 해줬다.
➕ 11501 주식
홍준이는 요즘 주식에 빠져있다. 그는 미래를 내다보는 눈이 뛰어나, 날 별로 주가를 예상하고 언제나 그게 맞아떨어진다. 매일 그는 아래 세 가지 중 한 행동을 한다.
- 주식 하나를 산다.
- 원하는 만큼 가지고 있는 주식을 판다.
- 아무것도 안한다.
홍준이는 미래를 예상하는 뛰어난 안목을 가졌지만, 어떻게 해야 자신이 최대 이익을 얻을 수 있는지 모른다. 따라서 당신에게 날 별로 주식의 가격을 알려주었을 때, 최대 이익이 얼마나 되는지 계산을 해달라고 부탁했다.
예를 들어 날 수가 3일이고 날 별로 주가가 10, 7, 6일 때, 주가가 계속 감소하므로 최대 이익은 0이 된다. 그러나 만약 날 별로 주가가 3, 5, 9일 때는 처음 두 날에 주식을 하나씩 사고, 마지막날 다 팔아 버리면 이익이 10이 된다.
처음 생각한 아이디어는 주식을 사고 그 다음날 더 높은값이 나오면 이익 실현을 하는 방식으로 생각을 하였다 그래서 count를 하나씩 올려가며 주식개수를 늘려가다가 최대값을 만나면 모두 이익실현을 하는걸로 구성을 하였다 근데 이 코드에서 큰 문제점은 최대값을 만나고 그 다음날짜에 또 이익을 볼 수 있는 입력이 들어왔을때 계산을 못하게 되는것이 큰 문제점이였다
그래서 혼자서 고민하다가 도저히 답이 나오질 않아서 구글링을 하게된다
와... 뒤에서 계산하면 되는구나
거꾸로 계산하면 쉽게 풀리는데 참 간단한 아이디어인데 여기까지 생각이 닿지를 못하는게 아쉽다
수정전 코드
#include <iostream>
using namespace std;
int T, N;
int main()
{
int *arr;
cin >> T;
for (int i = 0; i < T; i++)
{
int cnt = 0, count = 1, profit = 0;
cin >> N;
arr = new int[N];
for (int j = 0; j < N; j++)
cin >> arr[j];
cnt = arr[0];
for (int j = 1; j < N; j++)
{
if (cnt <= arr[j])
{
profit += count * (arr[j] - cnt);
cnt = arr[j];
count++;
}
else
{
cnt = arr[j];
count = 1;
}
}
cout << profit << endl;
delete arr;
}
return 0;
}만들다가 말았다 원래는 여기서 배열을 정렬해줘서 최대값을 가지고 온뒤 그 값과 비교하면서 이익을 저장하려 하였다 하지만 이대로 완성하려면 문제가 너무나 많았다
수정 후 코드
#include <iostream>
using namespace std;
int T, N;
int main()
{
int *arr;
cin >> T;
for (int i = 0; i < T; i++)
{
int max = 0;
long long int profit = 0;
cin >> N;
arr = new int[N];
for (int j = 0; j < N; j++)
cin >> arr[j];
for (int j = N - 1; j >= 0; j--)
{
if (arr[j] > max)
max = arr[j];
profit += max - arr[j];
}
cout << profit << endl;
delete arr;
}
return 0;
}코드가 참 간단해졌다 뒤에서 계산하니까 이렇게 편하더라 그리고 이익값이 int 범위를 넘는다고 하여서 long long으로 선언해줬다
