[알고리즘] 그리디와 라인스위핑

이희수·2024년 3월 14일

그리디 라인스위핑 알고리즘

알고리즘

목록 보기

3/25

그리디

각 단계마다 지역적 최적해가 궁극적으로 전역최적해가 되는 것.

그리디로 문제를 풀려면 2가지를 충족해야한다.

최적부분구조를 가지고 있어야 한다. 지금 state에서 최선을 다해 선택하는 해가 결국에는 전역적인 최적해로 이어져야 한다.
탐욕적속성이 증명이 되어야 한다.

하지만 코딩테스트에서 증명?? 할 시간이 없다.

무식하게 풀기 >>> DP >>> 그리디 순서로 생각해보자.

보통 그리디는 정렬, 우선순위 큐를 사용하는 2가지의 한정된 방법들이 주로 나오니 코드들을 외워놓자.

백준 1931 회의실 배정

1931 회의실 배정

끝 시간 순서대로 정렬을 하고 교차하는 지점들을 처리

#include<bits/stdc++.h>
using namespace std;
int n,from,to,ret=1;
vector<pair<int,int>> v;
int main(){
	cin>>n;
	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;
	return 0;
}

백준 1202 보석도둑

1202 보석도둑

무게를 적게 담을 수 있는 가방을 기준으로 넣을 수 있는 보석을 다 넣는 경우가 최댓값

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k,m,v,c,ret;
vector<pair<ll,ll>> gem;
vector<ll> bag;
int main(){
	cin>>n>>k;
	for(int i=0; i<n; i++){
		cin>>m>>v;
		gem.push_back({m,v});
	}
	sort(gem.begin(),gem.end());
	for(int i=0; i<k; i++){
		cin>>c;
		bag.push_back(c);
	}
	sort(bag.begin(),bag.end());
	priority_queue<ll> pq; 
	int j=0;
	for(int i=0; i<k; i++){
		while(j<n&&bag[i]>=gem[j].first) pq.push(gem[j++].second);
		if(pq.size()){
			ret+=pq.top(); pq.pop();
		}
	}
	cout<<ret<<'\n';
	return 0;
}

라인스위핑

하나의 라인을 한번에 빗자루 쓸 듯이 탐색하는 것만으로 점과의 집합, 선과의 집합 등 탐색을 끝내는 것을 라인스위핑 이라고 한다.

백준 2170 선 긋기

2170 선 긋기

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
P v[1000004];
int n, from,to,ret,l,r;
int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL); 
	cin>>n;
	for(int i=0; i<n; i++){
		cin>>from>>to;
		v[i]=P(from,to);
	}
	sort(v,v+n);
	l = v[0].first;
	r = v[0].second;
	for(int i=1; i<n; i++){
		if(r < v[i].first){
			ret += abs(r-l);
			l = v[i].first;
			r = v[i].second;
		}
		else if(v[i].first<= r && v[i].second >= r){
			r = v[i].second;
		}
	}
	ret += abs(r-l);
	cout<<ret<<'\n';
}

정렬 후 끝 지점이 다음 선의 왼쪽과 오른쪽 사이인 경우 (겹치는 경우) 오른쪽을 현재 선의 오른쪽으로 재정의함
끝 지점이 다음 선의 왼쪽보다 작을 경우 길이를 더함

투포인터

두개의 포인터를 가지고 탐색하는 알고리즘

이렇게 시작지점과 끝점 2개로 이루어진 투포인터를 활용해서 문제를 풀 수도 있고

이렇게 처음 시작점에서 같이 시작할 수도 있다.
어떤 '쌍' 을 가지고 푸는 문제에서 활용 가능하다.

백준 3273 두수의 합

3273 두수의 합

#include<bits/stdc++.h>
using namespace std;
int n,x,ret;
int a[1000005];
int main(){
	cin>>n;
	for(int i=0; i<n; i++){
		cin>>a[i];
	}
	cin>>x;
	sort(a,a+n);
	int l=0, r=n-1;
	while(l<r){
		if(a[l]+a[r]==x) r--, ret++;
		else if(a[l]+a[r]>x) r--;
		else if(a[l]+a[r]<x) l++;
	}
	cout<<ret<<'\n';
}