[중급 알고리즘] 그리디 알고리즘

Greedy Algorithm

- 결정해야할 때 그 순간에 가장 좋다고 생각하는 것(기준이 필요)을 선택하면서 답을 찾아가는 알고리즘

- 그 때는 최적일지도 모르지만 최종적으로는 답이 최적이 아닐 수도 있다.

 

- 기준을 하나 선택해서 계속 적용하는 것

- 왜 그 기준을 선택하는 것이 정답인지를 증명해야 한다.

 

그리디 알고리즘의 흔한 예시인 거스름돈 문제는 사실 동전이 배수 관계이기 때문에 성립 가능하다.

 

💚1080 행렬

결국에는 0, 1밖에 없으므로 궁극적으로 연산을 아예 안 하는 것과 1회 한 것으로 나눌 수 있다.

3 X 3보다 큰 행렬을 바꾸는 연산을 할 때 가장자리가 연산횟수가 1회로 가장 적다.

그걸 기준으로 바꾸는 연산을 할지 말지 결정해야 한다.

행렬을 순회하면서 가장자리의 정보를 가지고 판단한다.

 

💚2138 전구와 스위치

위 문제와 동일하게 전구 on / off 둘로 나눌 수 있다.

 

💚1285 동전 뒤집기

무작위로 행과 열을 뒤집는다 생각하면 어렵다.

행과 열을 분리한 뒤, 행의 뒤집는 여부가 결정되어있으면 열의 경우 최대값을 만들 수 있는 조합이 제한되므로 최대값을 찾기 수월해진다.

그리고 그러한 행 조합을 모두 수행한 뒤 최대값을 찾으면 된다.

여기서는 비트마스크를 통해 행의 뒤집기 여부를 생성하였다.

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

char flip(char x) {
    if(x == 'H') return 'T';
    else return 'H';
}

int main() {
    int n;
    cin >> n;
    vector<string> a(n);
    for(int i = 0;i < n;i++) {
        cin >> a[i];
    }

    int ans = n * n;
    // 행 조합 생성
    // 행마다 어떻게 돌릴지 결정한 후에 열마다 결정(즉 결정읇 분리)
    for(int state = 0;state < (1 << n);state++) {
        int sum = 0;
        for(int j = 0;j < n;j++) {
            int cnt = 0;
            // 현재 열 j의 행 탐색
            for(int i = 0;i < n;i++) {
                char cur = a[i][j];
                if(state & (1 << i)){
                    cur = flip(cur);
                }
                if(cur == 'T') {
                    cnt++;
                }
            }
            // cnt = T의 개수, n - cnt = H의 개수
            // 해당 열에서의 가능한 최소값
            sum += min(cnt, n - cnt);
        }
        // 행 조합마다 T의 최소값 탐색
        if(ans > sum) ans = sum;
    }

    cout << ans << '\n';
    return 0;
}

💚1202 보석 도둑

 

오랜만에 확인한 Lower bound, Upper bound!! 잊지말고 잘 활용하자.

 

목표: 가격이 큰 보석을 최대한 많이 가져가는 것이 좋다. ➡️ 가격 기준 내림차순 정렬이 필요해 보인다.

무게와 가격 정보가 매칭되어야 한다. ➡️ pair를 쓰면 좋아보인다.

적게 넣을 수 있는 가방부터 챙겨서 넣는 게 이로워보인다.➡️ 최대 무게 기준 오름차순 정렬이 필요해 보인다.

 

총 2가지 방법이 있다.

1) 

- 가격이 높은 보석부터 차례대로 각 보석을 담을 수 있는 가방 중 C[i]가 가장 작은 가방에 넣는다.

- 이를 구현하기 위해 다음을 효율적으로 할 수 있는 자료구조가 필요해 보인다.

 

1. 어떤 수 x보다 큰 숫자 중에 가장 작은 수를 찾는다.(lower_bound)❤️

2. 수를 지운다.

 

BST(Binary Search Tree)를 이용하면 1번과 2번을 O(lgK)만에 할 수 있다.

MultiSet을 이용한다.(NlogK)

 

---

 

⭐️ Set이란?

연관 컨테이너, 노드 기반 이진 트리 구조

중복 허용 안함(unique)

Set은 Red-Black Tree로 구현한다. 이는 BST 중 Self-Balancing 특성을 갖는다.

균형을 유지하기 때문에 모든 작업의 시간 복잡도가 O(NlogN)을 유지한다.

 

⭐️ 내림차순 정렬 set 생성

set<int, greater<int>> s;

⭐️ Iterator

for(auto i = s.begin();i != s.end();i++) {
	cout << *i << endl;
}

⭐️ 멤버 함수

1) 크기 관련

- s.size()

- s.empty()

 

2) 탐색 관련

- s.lower_bound(k) : iterator 리턴

- s.upper_bound(k) : 정렬된 순서를 기준으로 k 다음 원소의 Iterator를 리턴

- s.find(k): k를 가리키는 iterator 리턴, k가 없으면 end()와 같은 iterator 리턴

 

3) 원소 삭제

- s.erase(it)

- s.erase(it1, it2)

- s.clear()

 

4) 원소 삽입

- s.insert(k)

🌎 추가 설명

insert 함수의 반환값으로 <iterator, bool>

- iterator: 삽입한 위치에 해당하는 iterator

- bool: 성공 여부

 

 

⭐️ Multiset이란?

Set과 거의 동일하지만, 중복된 key값을 허용하는 컨테이너이다.

#include <set>
multiset<int> mts;
multiset<int, greater<int>> mts;
multiset<int> mts(mts2);
multiset<int> mts2(mts1.begin(), mts1.end());

 

⭐️ 멤버 함수

거의 유사하지만 일부 다른 메서드가 있다.

- mts.lower_bound(k): 원소 k가 있는 구간의 처음을 가리키는 iterator 리턴

- mts.upper_bound(k): 원소 k가 있는 구간의 끝(그 다음 원소)을 가리키는 iterator 리턴

- mts.equal_range(k): 원소 k가 있는 구간을 나타내는 pair 객체 리턴. pair의 원소는 (lower_bound, upper_bound)

 

Set, Multiset 참고

https://choiiis.github.io/cpp-stl/basics-of-set-multiset-class/

[C++] set, multiset 클래스 정리

 

---

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
struct jewel {
    int m, v;
};

int main() {
    int n, k;
    cin >> n >> k;
    vector<jewel> a(n);
    for(int i = 0;i < n;i++) {
        cin >> a[i].m >> a[i].v;
    }

    multiset<int> s;
    for(int i = 0;i < k;i++) {
        int t;
        cin >> t;
        s.insert(t);
    }

    // 가격 오름차순 정렬
    sort(a.begin(), a.end(), [](jewel u, jewel v) {
        return u.v > v.v;
    });

    long long ans = 0;
    for(int i = 0;i < n;i++){
        // 보석의 무게를 감당할 수 있는 가방 중 최소
        auto it = s.lower_bound(a[i].m);
        if(it != s.end()) {
            // 가방 존재하면 보석 포함 후 해당 가방은 multiset에서 제거
            ans += a[i].v;
            s.erase(it);
        }
    }

    cout << ans << '\n';
    return 0;
}

 

2) 

보석과 가방을 하나로 합치고 무게를 기준으로 오름차순 정렬하자.

최대힙(max heap, c++에서는 priority_queue)을 이용해 구현을 할 수 있다.

struct jewel {
   int m,v,w;
}

m은 무게, v는 가격을 의미하고, w는 0이면 보석 1이면 가방임을 표시한다.

이건 (N + K) log N이라는 시간이 걸린다.

 

💚 2109 순회 강연 

위의 보석 도둑 문제와 상당히 유사하다.

보석의 무게 <= 가방의 무게

현재 날짜 <= 강연의 날짜

부등호의 방향만 다르다고 생각하면 된다.

 

강연날짜를 기준으로 내림차순으로 정렬한 후

해당 날짜가 가능한 강연 중 가장 보상이 높은 강연 선택

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

struct Lecture {
    // 강연료, 날짜
    int p, d;
};

int main() {
    int n;
    cin >> n;
    vector<Lecture> a(n);
    for(int i =0;i < n;i++) {
        cin >> a[i].p >> a[i].d;
    }

    // 날짜 내림차순
    // 비교적 경쟁률이 낮은 것부터 하기 위함
    sort(a.begin(), a.end(), [](Lecture a, Lecture b) {
        return a.d > b.d;
    });

    int k = 0;
    priority_queue<int> q;
    int ans = 0;
    for(int i = 10000;i >= 1;i--) {
        // 인덱스 처리 및 i 날짜에 해당되는 강연 탐색
        while(k < n && a[k].d == i) {
            q.push(a[k].p);
            k += 1;
        }
        if(!q.empty()) {
            ans += q.top();
            q.pop();
        }
    }

    cout << ans << '\n';
    return 0;
}

이전에는 가격 기준으로 정렬해놓은 후 해당 날짜 뒤에서부터 채워넣은 방식을 썼다.

#include <iostream>
#include <queue>


using namespace std;

priority_queue <pair<int, int>> q;
int scheduler[10001];

int main(void) {
	int money = 0;
	int n;
	int p,d;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> p >> d;
		q.push(make_pair(p, d));
	}
	
	while (!q.empty()) {
		p = q.top().first;
		d = q.top().second;

		q.pop();
		for (int i = d; i > 0; i--) {
			if (scheduler[i] != 1) {
				//cout << p << " " << i << endl;
				money += p;
				scheduler[i] = 1;
				break;
			}
		}
	}

	cout << money << '\n';

}

💚 12738 가장 긴 증가하는 부분 수열3

숫자가 지나치게 길기 때문에 DP는 불가능하다.(DP로 푸는 건 여기, 숫자가 커서 O(N^2)의 시간복잡도를 지닌 DP는 바로 시간초과가 뜬다.)

LIS

가능한 정답의 리스트를 만들어가면서 답을 구한다.

그런데 가장 길이가 긴 리스트를 탐색하다보면 길이가 짧은 것은 탐색할 필요가 없다는 사실을 깨우친다.

lower_bound를 사용해서 크거나 같은 것중에 가장 작은 수를 의미하므로 lower_bound의 수를 바꿔주고, 없으면 추가하는 것을 반복하면 된다! 대신 길이만! 구할 수 있다.

예를 들어 5, 6, 7, 1인 경우 탐색이 끝나면 결국 1,6,7이 되기 때문

 

수열까지 다 구하려면 추가적인 작업이 필요하다. 각각의 수를 추가할 때마다 그 앞에 어떤 수의 인덱스가 있었는지 기록해야 한다.

앞선 예에 적용해보면 5을 입력할 때는 -1을, 6을 입력할 때는 0을...이렇게!

그리고 마지막 숫자부터 역으로 추적하여 증가수열을 찾아낼 수 있다.

시간 복잡도는 O(NlogN)이다.

 

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

int main() {
    int n;
    cin >> n;
    vector<int> v;

    for(int i = 0;i < n;i++) {
        int num;
        cin >> num;
        auto it = lower_bound(v.begin(), v.end(), num);

        if(it == v.end()) {
            v.push_back(num);
        }
        else {
            *it = num;
        }
    }

    cout << v.size() << '\n';
}

 

그리디 연습, 도전에서 이어질 예정...