2024 - 11- 12 C++ 코딩테스트 10주완성 D+60

그리디 알고리즘

 

그리디 알고리즘은 문제를 해결할 때 각 단계에서 그 순간에 최선이라고 생각되는 선택을 하는 방식으로,

 

이 과정에서 얻은 선택들이 모여 전체 문제에 대한 최적의 해를 구하는 알고리즘이다.

 

즉, 그리디 알고리즘은 지역적 최적해(Local Optimal Solution)를 찾는 과정에서,

 

이를 모아 전역적 최적해(Global Optimal Solution)를 구하는 방식입니다.

 

다만, 모든 경우에 전역 최적해를 보장하지는 않습니다. 

 

예를 들어

 

"12400" 원을 지불하고 싶은데, 최소한의 지폐를 사용하여 지불하고 싶다.

현재 가진 지폐는 10000원짜리 5장, 1000원짜리 5장, 100원짜리 5장이 있다고 치면,

최소한의 지불해야되는 지폐개수는 몇장인가? 

 

라는 문제가 그리디 알고리즘 문제가 될 수 있다.

그리디의 조건

 

그리디 알고리즘을 실행하려면 다음과 같은 조건이 충족되어야 한다.

 

 

1. 최적부분 구조

최적 부분 구조(Optimal Substructure)는 문제를 작은 부분 문제로 나눌 수 있으며,

그 부분 문제들의 최적해가 모여서 전체 문제의 최적 해를 이룰 수 있는 구조를 말합니다.

 

아까 예시로 든 문제를 단계별로 나눠보면 다음과 같습니다.

 

1. 가장 큰 화폐 단위부터 선택하여 부분 문제로 나눕니다.
2. 선택된 화폐를 사용하고 남은 금액을 다음 단계의 문제로 넘깁니다.
3. 이를 남은 금액이 0원이 될 때까지 위 과정을 반복하여 전체문제에 대한 최적해를 찾습니다.

단계별 과정은 다음과 같습니다/.

 

총 금액 : 12400원

 

사용할 수 있는 화폐 : 10000원 5개, 5000원 5개, 1000원 5개, 100원 5개

 

• 단계 1

 

| 현재 금액 : 12400원 |

 

| 선택 화폐 : 10000원 |

 

| 남은 금액 : 2400원 |

 

• 단계 2

| 현재 금액 : 2400원 |

 

| 선택 화폐 : 1000원 |

 

| 남은 금액 : 1400원 |

 

• 단계 3

| 현재 금액 : 1400원 |

 

| 선택 화폐 : 1000원 |

 

| 남은 금액 : 400원 |

 

• 단계 4

| 현재 금액 : 400원 |

 

| 선택 화폐 : 100원 |

 

| 남은 금액 : 3원 |

• 단계 5

| 현재 금액 : 300원 |

 

| 선택 화폐 : 100원 |

 

| 남은 금액 : 200원 |

• 단계 6

| 현재 금액 : 200원 |

 

| 선택 화폐 : 100원 |

 

| 남은 금액 : 100원 |

• 단계 7

| 현재 금액 : 100원 |

 

| 선택 화폐 : 100원 |

 

| 남은 금액 : 0원 |

 

 

 

최종 사용 화폐 : 1000원 1개, 1000원 2개, 100원 4개 ( 총 7개 )

 

이 과정은 최적 부분 구조를 이용하여 각 단계에서 최적의 선택을 하고,

 

이를 결합하여 전체 문제의 최적해를 찾는 방법을 보여주었습니다.

 

2. 탐욕적속성이 증명이 되어야 합니다.

 

보통 귀류법으로 증명을 합니다.

증명하는 방법은 크게 3가지가 있다.

귀류,귀납,대우증명이 있는데, 여기서 귀류법은 간접증명방법중 하나이다.

간접증명이란 직접증명하기 어려운 것들에 대해 간접적으로 증명하는 것이다.

 

예를 들어서 루트2가 무리수임을 귀류법으로 증명해보자.

 

먼저 루트2의 거짓명제인 유리수로 가정하고 풀어보자

 

루트 2 = 2의 제곱근이므로 A / B 이다.

 

여기서 양쪽 항에다 제곱을 곱해주면 2 = A^2/B^2 가 된다.

 

양쪽 항에다 B^2 를 곱해주면 2 * B^2 = A^2 이다.

 

이때 2 * B^2 는 짝수이기때문에 A^2도 짝수가 되어야한다.

 

이때 A는 정수이기때문에 무조건 짝수가 될 수는 없다.

 

따라서 루트2가 유리수라는 명제는 거짓이다.

 

 

현실적인 방법

 

원래 그리디 알고리즘을 정석적으로 하기에는 "~를 위해서 탐욕적으로 ~를 해야 한다." 라는 명제를 앞의 설명처럼 증명해

 

하고 해당 명제가 맞는 것임을 확인하고 그 명제로 문제를 풀어야한다.

 

하지만 이러한 것을 코딩테스트에서 하기에는 불가능하다.

 

어떤 명제를 생각한 다음 -> 어떠한 상태값( idx, here 등..)에서 가장 최적의 로직은 무엇일까 생각하고

 

-> 코드로 구현 -> 해당 명제가 틀렸다면 -> 빠르게 변경해서 다시 푸는 것입니다.

 

이제 문제를 풀면서 실습을 해보자!

 

 

큰돌은 욕심많은 도서관 사서야!

 

큰

돌은 도서관의 사서입니다.

 

그의 도서관에는 학생들이 자유롭게 사용할 수 있는 N개의 좌석이 있습니다.

 

학생들은 좌석에 앉아서 공부를 하기 위해 특정한 시간에 도착하여 특정한 시간에 떠납니다.

 

큰돌은 학생들이 가능한 한 많은 좌석을 사용할 수 있도록 최대한 많은 학생들에게 좌석을 배정하려고 합니다.

 

각 학생의 도착 시간과 떠나는 시간이 주어질 때, 가능한 한 많은 학생들이 좌석을 사용할 수 있도록 배정할 때의 최대 학생 수를 구하세요.

 

입력

첫 줄에 학생의 수 N이 주어집니다. (1 ≤ N ≤ 100,000)

다음 N개의 줄에는 각 학생의 도착 시간과 떠나는 시간이 주어집니다.

도착 시간과 떠나는 시간은 정수로 주어지며, 도착 시간은 떠나는 시간보다 항상 작습니다.

 

출력

 

최대 몇 명의 학생들이 도서관 좌석을 사용할 수 있는지 출력하세요.

 

실습코드

 

#include <bits/stdc++.h>

using namespace std;

int n,from,to,ret;

int main()
{
    cin >> n;

    vector<pair<int,int>> v;

    for(int i = 0; i < n; i++)
    {
        cin >> from >> to;
        v.push_back({to,from});
    }

    sort(v.begin(),v.end());
    from = v[0].second;
    to = v[0].first;

    for(int i = 1; i < n; i++) 
    {
        if(v[i].second < to) continue;
        from = v[i].second; to = v[i].first; ret++;
    }

    cout << ret;
}

 

골동품 수집가 큰돌은 욕심쟁이야!!!

 

골동품 수집가인 큰돌은 세계 여러 곳을 여행하며 희귀한 골동품을 수집해 왔습니다.

 

이번에 큰돌은 거대한 골동품 박람회에 참석하기로 했습니다.

 

박람회에서는 다양한 골동품들이 전시되어 있으며, 각각의 골동품은 무게 M[i] 와 가치 V[i] 를 가지고 있습니다.

 

큰돌은 자신이 수집한 골동품들을 보관할 수 있는 고급 가방 K개를 가지고 있습니다.

 

각 가방은 최대 C[i] 무게까지 골동품을 담을 수 있으며, 가방 하나에는 최대 한 개의 골동품만 넣을 수 있습니다.

 

큰돌은 가능한 한 최대한 가치 있는 골동품들을 가방에 넣어 가져가고 싶습니다.

 

큰돌이 수집할 수 있는 골동품의 가치의 합이 최대값을 구하는 프로그램을 작성하세요.

 

입력

 

첫째 줄에 골동품의 수 N과 가방의 수 K가 주어집니다.( 1 <= N,K <= 300,000 )

다음 N개의 줄에는 각 골동품의 정보(M[i], V[i]) 가 주어집니다. ( 0 <= M[i] , V[i] <= 1,000,000 )

다음 K개의 줄에는 가방에 담을 수 있는 최대 무게 C[i] 가 주어집니다. ( 1 <= C[i] <= 100,000,000 )

 

출력

 

큰돌이 수집할 수 있는 골동품 가치의 합의 최대값을 출력합니다.

 

실습코드

 

#include<bits/stdc++.h>
using namespace std; 
typedef long long ll;
ll n, k, ret, temp1, temp;
int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
	
	cin >> n >> k; 
	vector<pair<ll,ll>> v(n);
	vector<ll> vv(k); 
	for(int i = 0; i < n; i++){
		cin >> v[i].first >> v[i].second; 
	}
	for(int i = 0; i < k; i++) cin >> vv[i]; 
	sort(v.begin(), v.end());
	sort(vv.begin(), vv.end());
	priority_queue<ll> pq; 
	
	int j = 0; 
	for(int i = 0; i < k; i++){
		while(j < n && v[j].first <= vv[i]) pq.push(v[j++].second);
		if(pq.size()){
			ret += pq.top(); pq.pop();
		}
	} 
	cout << ret << "\n"; 
	return 0;
}

 

먼저 이문제에 대해서는 가방의 무게와 골동품의 무게를 비교하는 것이 핵심이다.

 

그리드 다양한 명제로 추론을 하자면,

 

1. 골동품을 오름차순으로 정렬하는 방법

2. 골동품을 내림차순으로 정렬하는 방법

3. 가방의 무게를 기준으로 최대의 무게를 가지고 최대의 가치를 가지는 물건을 하나씩 넣는 방법

 

등이 있다.

 

1번 명제로 봤을 때,

 

예를 들어 (10,500),(11,400),(2,200) 등이 있다고하고 가방이 11,10 이 있다고 하자.

이때 가치가 11인 가방에 (0,500) 이 담길 것이고, 10인 가방에 (2,200)이 담길 것이다.

하지만 최대 가치의 수는 11인 가방에 (11,400)이 담기고, 10인 가방에 (0,500)이 담기는 것이다.

따라서 이 명제는 틀렸다.

 

 

빠르게 태세변환을 하여 다른 로직으로 가보자!

 

2번 명제로 봤을 때,

 

위에 예시를 똑같이 계산해보자 (2,200),(11,400),(10,500) 이고 가방은 10,11 일것이다.

이때 가치가 10인 가방에 (2,200)이 담길 것이고, 11인 가방에 (11,400)이 담길 것이다.

하지만 최대 가치의 수는 11인 가방에 (11,400)이 담기고, 10인 가방에 (0,500)이 담기는 것이다.

따라서 이 명제도 틀렸다.

 

우디르급 태세변환해서 다른 명제로 후딱 가보자!

3번 명제로 봤을 때,

 

위의 예시를 똑같이 계산해보자.

가치가 10인 가방의 무게이하인 골동품들만 비교하여 가치가 최대인 골동품을 담는다.

고로 무게가 10인 가방에는 (2,200) 과 (10,500)을 비교하면 가치값이 (10,500)이 더 크기 때문에

(10,500)이 담긴다.

11인 가방에는 (2,200),(11,400) 과 비교하면 가치값이 더 큰 (11,400)이 담기게 된다.

최대 가치의 수는 11인 가방에 (11,400)이 담기고, 10인 가방에 (0,500)이 담기는 것이다.

따라서 이 명제는 참이 된다.

 

 

자 이제 3번 로직을 이용해서 짠 코드의 실행순서를 살펴보자!

 

1. 골동품의 개수와 가방의 개수를 입력받는다.

2. 골동품의 개수만큼 반복문을 돌린다.
 ㄴ 2-1. 각 골동품의 가치와 무게를 입력받는다.

3. 가방의 개수만큼 반복문을 돌린다.
  ㄴ3-1. 각 가방의 무게를 입력받는다.

4. 골동품을 오름차순으로 정렬해준다.

5. 가방을 오름차순으로 정렬해준다.

6. 가방의 개수만큼 반복문을 돌린다.
  ㄴ6-1. 내부변수 j를 이용하여
              만약  j가 가방의 개수 n 보다 작고, j번째 골동품의 무게가 가방의 무게보다 작을 시 
              우선순위 queue에 j번째 골동품의 가치를 push해준뒤 j++를 해준다.
 ㄴ 6-2. 만약 pq의 사이즈가 있으면
             우선순위 queue는 push할떄마다 자동으로 오름차순으로 정렬해주므로
             ret 에 pq의 top을 더해주고, pq.pop 을 진행해준다.

7. ret을 출력시켜준다.             

 

처음에 6번로직 자체가 이해되질 않았는데,

 

pq가 오름차순으로 자동정렬을 하여주어, 가치가 최대한 스택을 하나씩 빼서 가치를 저장후 pop시켜주고,

 

또 계속 push를 하여도 문제없는 이유는,

 

가방을 오름차순으로 정렬하였기 떄문에 다음 순서인 골동품으로 넘어가도 그전에 push 시켰던 골동품들도

 

비교대상에 다 포함가능한것이라 이런 로직으로 짠것이다!

 

알고리즘을 정말 대단한것같다.. 분명 예시문제인데,, 어렵다..