그리디(Greedy) 알고리즘

최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

[참고 : 위키피디아 - 탐욕 알고리즘]

 

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

 

모든 문제는 아래의 책을 참고하였다.

book.naver.com/bookdb/book_detail.nhn?bid=16439154

이것이 취업을 위한 코딩 테스트다 with 파이썬

 

거스름돈 문제

문제

 

거스름돈 500원, 100원, 50원, 10원짜리 동전이 무수히 존재한다고 가정

 

손님에게 N원을 거슬러줘야할 때 줘야할 동전의 최소 개수 계산

 

해결방법

 

문제를 풀기 전에 한 번 생각을 해보고 풀자

 

만약 손님에게 3000원을 거슬러 준다고 해보자.

 

그렇다면 줘야할 동전의 최소 개수는 500원 짜리 6개다. (100원짜리는 30개, 50원짜리는 60개, 10원짜리는 300개)

 

이 점에서, 하나를 유추할 수 있다.

 

바로, 큰 잔돈부터 줘 버리면 동전 개수가 최소가 된다는 사실이다.

 

이를 c++ 코드로 작성해보자.

 

/*
2021-04-05 예제 3-1 거스름돈 문제 cpp 계산
이것이 취업을 위한 코딩 테스트다 with 파이썬 참고
*/

#include <iostream>

int main(void)
{
    int change = 5620; // 거스름돈 5620원
    int arr[5] = { 500, 100, 50, 10 }; // 거스름돈 단위 (500원, 100원, 50원, 10원) 배열 정의
    int count = 0; // 횟수 count

    for (int i = 0; i < 4; i++) // 동전의 종류가 총 4종류이니 반복을 4번한다.
    {
        count += change / arr[i]; // 몫을 계산하면 몇개의 동전을 써야하는지 알 수 있다.
        change = change % arr[i]; // 잔돈에서 동전의값을 나눈 나머지는 다음 잔돈에 대한 금액을 알 수 있다. (5620원 % 500원(x11개) => 120원) 

    }
    printf("%d\n", count);

    /*
    1. 거스름돈 : 5620원
    2. 잔돈 500원 11개 거스름돈 지불 5500원 (count + 11)
    3. 거스름돈 : 120원
    4. 잔돈 100원 1개 거스름돈 지불 100원 (count + 1)
    5. 거스름돈 : 20원
    6. 잔돈 50원 0개 거스름돈 지불 0원 (count + 0)
    7. 거스름돈 : 20원
    8. 잔돈 10원 2개 거스름돈 지불 20원 (count + 2)

    최소 횟수는 14번
    */
}

 

그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토

 

위 문제를 해결할 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 조합해 다른 해가 나올 수 없기 때문

 

예시, 위와 동일하게 5,620원을 거슬러 줘야 하는데 화폐 단위가 1,500원, 1,124원, 1,000원, 100원, 10원이라고 하면 그리디 알고리즘에 의해 7개의 동전(1,500 x 3개, 1,000원 x 1개, 100원 x 1개, 10원 x 2개)을 거슬러줘야 한다.

 

그러나 1,124원짜리 화폐단위를 이용하면 5개의 동전(1,124원 x 5개)으로도 거슬러 줄 수 있어 이것이 사실상 최적의 해다.

 

(따라서 위 문제의 화폐 단위가 배수가 아닌 무작위로 주어졌을 때는 그리디 알고리즘으로 해결할 수 없다.)

 

대부분의 그리디 알고리즘 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.

 

 

 

큰 수의 법칙(Vector 및 sort 사용)

/*
2021-01-20 예제 3-2 큰 수의 법칙 문제 cpp 계산 
이것이 취업을 위한 코딩 테스트다 with 파이썬 참고
*/

/*
Vector를 이용한 풀이
*/

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void)
{
    vector<int> v;
    int n, m, k, d; // n : 총 개수, m : 총 연산, k : 최대 연속 사용, d : 받을 숫자자
    int max, smax;
    int result = 0;

    scanf("%d%d%d", &n, &m, &k);

    for (int i = 0; i < n; i++)
    {
        scanf("%d", &d);
        v.push_back(d);
    }

    sort(v.begin(), v.end());

    max = v[n - 1];
    smax = v[n - 2];

    result = max * k * (m / k) + smax * (m % k);

    cout << result << endl;
}

vector와 sort를 이용해서 풀었다.

 

풀이 방법...

 

처음에는 순서대로 덧셈을 하는 방법을 구현하려다가 너무 비효율적인 것 같아 종이에 다른 예시도 적어 보았습니다.

 

책 예시

 

1.

n = 5,

m = 8,

k = 3,

d = 2, 4, 5, 6, 8

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

 

2.

n = 5,

m = 7, 

k = 2, 

d = 3, 4, 3, 4, 3

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

 

추가 예시 생각

n = 5,

m = 9,

k = 4,

d = 1, 2, 3, 4, 5

=> 5 + 5 + 5 + 5 + 4 + 5 + 5 + 5 + 5

 

위 예시들을 한꺼번에 놓고 보니 뭔가 패턴이 보였다.

 

순서대로 계산하는 건 의미가 없고

 

최대 숫자와 그 다음 큰 숫자가 몇번 더해지는 것만 알면 된다는 것이다.

 

즉 첫 번째 예시의 경우,

 

6 × 3 × 2(번) + 5 × 2 × 2(번) 된다는 것을 알 수 있다.

 

추가 예시의 경우

 

5 × 4 × 2(번) + 4 × 1 × 1(번) 된다는 것을 알 수 있다.

 

만약 여기서 추가 예시의 m을 10으로 한다면

n = 5, m = 10, k = 4, d = 1, 2, 3, 4, 5

=> 5 + 5 + 5 + 5 + 4 + 5 + 5 + 5 + 5 + 4

가 될 것이다.

 

그렇다면 5 × 4 × 2(번) + 4 × 1 × 2(번) 된다는 것을 알 수 있다.

 

이러면 위 문제에 대한 수식을 아래와 같이 정의 할 수 있다.

 

최대값 × k × (m%k의 몫) + 두번째 최대값 × 1 × (m%k의 나머지)

 

위 수식을 코드로 정의한 것이 

 

max * k * (m / k) + smax * (m % k);

이 부분이며 정상적으로 값이 출력되는 것을 알 수 있다.

큰 수의 법칙(STL 사용 안함)

추후 정리 예정...

 

숫자 카드 게임 (STL 사용 안함)

STL을 사용하면 구현할 수 있으나 STL 사용안하고 구현하는 건 나중에 따로 정리

 

1이 될 때 까지

/*
2021-01-21 예제 3-4 1이 될 때까지 cpp 구현
참고: 이것이 취업을 위한 코딩 테스트다 with 파이썬 
*/

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
using namespace std;

int main(void)
{
    int n, k; // n 25, k 5
    int count = 0;

    scanf("%d %d", &n, &k);

    while (true)
    {
        if (n == 0)
            break;

        else if (n % k == 0)
        {
            count++;
            n /= k;
            if (n == 1) // 마지막 몫이 1이 나오면 1을 빼준다.
            {
                n--;
            }
        }
        else if (n % k != 0)
        {
            n--;
            count++;
        }
    }
    cout << count << endl;
}

 

다시 짜보자

 

곱하기 혹은 더하기

/*
2021-04-11 예제 곱하기 혹은 더하기 문제 cpp 계산
이것이 취업을 위한 코딩 테스트다 with 파이썬 참고
*/

#include <iostream>
#define _CRT_SECURE_NO_WARNINGS

using namespace std;

int main(void)
{
	string str;
	cin >> str; // cin은 공백이 왔을 때 종료되는 걸로 인식, 한 줄로 받으려면 getline 사용

	// 첫 번째 문자를 숫자로 변경한 값을 대입
	/*
	문자형태의 숫자를 입력 받았을 때 0에 해당하는 아스키코드 값을 빼주면 된다.
	문자 1의 ASCII = 49
	문자 0의 ASCII = 48
	*/
	long long result = str[0] - '0';

	// 0번째 index는 봤으니 첫 번째부터..
	for (int i = 1; i < str.size(); i++)
	{
		// 두 수 중에서 하나라도 '0' 혹은 '1'인 경우, 더하기 수행

		int num = str[i] - '0';

		if (num <= 1 || result <= 1) 
			result += num;
		else 
			result *= num;
	}
	cout << result << endl;
}

 

 

모험가 길드

/*
2021-04-11 예제 모험가 길드 문제 cpp 계산
이것이 취업을 위한 코딩 테스트다 with 파이썬 참고
*/

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void)
{
	int n;
	cin >> n; // 사람 수

	vector<int> arr;

	for (int i = 0; i < n; i++)
	{
		int fear; // 공포도 
		cin >> fear;
		arr.push_back(fear); // 공포도 입력
	}

	sort(arr.begin(), arr.end()); // 오름차순 정렬, begin과 end는 iterator

	int group = 0; // 총 그룹 수
	int cnt = 0; // 현재 포함된 모험가 수

	for (int i = 0; i < arr.size(); i++) // 정렬된 공포도 확인
	{
		cnt += 1; // 현재 그룹에 해당 모험가 포함
		if (cnt >= arr[i]){ // 현재 그룹에 포함된 모함가의 수가 현재 공포도 이상이라면, 그룹 결성
			group += 1; // 총 그룹의 수 증가
			cnt = 0; // 초기화
		}
	}
	cout << group << endl;
}

 

모든 문제 출처 및 내용 참고

www.youtube.com/watch?v=2zjoKjt97vQ