5주차: 그리디, 라인스위핑, 투포인터

https://www.inflearn.com/course/10%EC%A3%BC%EC%99%84%EC%84%B1-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%81%B0%EB%8F%8C/dashboard

10주완성 C++ 코딩테스트 | 알고리즘 IT취업 자료구조 문제풀이 - 인프런 | 강의

 

https://blog.naver.com/jhc9639/222319124359

[알고리즘 강의] 5주차. 그리디 라인스위핑 투포인터

위 수업을 듣고 정리한 글입니다.

 

 

그리디

지금의 상태,인덱스에서 최선이라고 생각하는 해가 답이 되는 것

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

 

• 최적 부분 구조를 가지고 있어야한다.
• 탐욕적 속성이 증명이 되어야한다.

위 2가지 속성을 확인하기 어렵기때문에, 경우의 수를 따지기에는 너무나 큰 시간복잡도, 공간복잡도가 있으면 그리디를 시도해야한다.

 

무식하게 풀기 -> DP -> 그리디 순으로 생각하자.

 

• 정렬(sort), 우선순위 큐(priority_queue)를 사용하는 2가지 한정적인 방법이 주로 나온다.

* 자신의 해가 틀리더라도 다시 시작해보는 것이 중요하다.

 

1931번 . 회의실 배정

시간 제한           메모리 제한          제출          정답          맞힌 사람          정답 비율

 

2 초

128 MB

160866

50860

35722

29.751%

문제

 

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

 

입력

 

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

예제 입력 1 복사

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

예제 출력 1 복사

4

힌트

(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

 

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

먼저 그림을 그려보기

 

흐름

코드

#include <bits/stdc++.h>
using namespace std;

int from, to, n, ret=1;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> n;
    vector<pair<int,int>> v;
    for(int i=0;i<n;i++){
        cin >> from >> to;
        v.push_back({to,from});
    }
    //2. 끝점 기준으로 정렬하기
    sort(v.begin(), v.end());
    //3. 가능한 회의 최대 개수 구하기
    from=v[0].second;
    to=v[0].first;
    for(int i=1;i<n;i++){
        if(to>v[i].second) continue; //회의 겹치면 continue
        from=v[i].second; to=v[i].first; ret++;
    }
    //4. 정답 출력
    cout<<ret<<"\n";

    return 0;
}

 

1202번. 보석 도둑

보석 도둑 

다국어

한국어   

시간 제한          메모리 제한         제출         정답         맞힌 사람         정답 비율

 

1 초

256 MB

48839

11301

7925

21.841%

문제

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

 

출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

예제 입력 1 복사

2 1
5 10
100 100
11

예제 출력 1 복사

10

예제 입력 2 복사

3 2
1 65
5 23
2 99
10
2

예제 출력 2 복사

164

힌트

두 번째 예제의 경우 첫 번째 보석을 두 번째 가방에, 세 번째 보석을 첫 번째 가방에 넣으면 된다.

 

https://www.acmicpc.net/problem/1202

1202번: 보석 도둑

 

흐름

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k,ret,temp1,temp2;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> n >> k;
    vector<pair<ll,ll>> v(n); //크기가 n인 벡터 선언 : 보석-무게,가격 저장
    vector<ll> vv(k); //크기가 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]; //가방무게
    //2. 보석: 무게 순, 무게가 같으면 가격 순으로 정렬하기, 가방:무게순 , 오름차순
    sort(v.begin(), v.end());
    sort(vv.begin(), vv.end());
    //3. 가방마다 들어갈 수 있는 보석을 다 집어넣고 그 중 가격이 가장 높은것만 pop
    priority_queue<int> 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(); 
        }
    }
    //4. 정답 출력
    cout << ret <<"\n";

    return 0;
}

 

유의할 점

• 2개를 모두 고려해야할 경우(이 문제에서는 무게와 가격) - 제한사항부터 정렬하여(무게) 우선순위 큐에 집어넣고, 가격이 가장 높은(그 다음 고려사항)을 pop한다.
• 우선순위 큐에 집어넣기 전 sort(정렬)해놓으면 원소 push시에 끝까지 조건을 확인하지않고 중간에 멈출 수 있다.(크기순이므로) 

 

우선순위 큐

우선순위에 따라 원소가 정렬된 큐

원소가 push(삽입)될 경우 우선순위에 맞춰 큐가 정렬되고 pop은 정렬된 큐의 top(가장 크거나 가장 작은 원소)에서 이루어진다.

Heap으로 구현되었으므로 push 후 원소 정렬 과정은 O(logN)만에 이루어진다.

* 기본적으로 내림차순(크기 큰것부터 앞에 위치)

 

출처: https://travelbeeee.tistory.com/126

[C++] STL Priority_Queue Library 기본 명령어 정리

 

 

14729번: 칠무해

칠무해

 

시간 제한          메모리 제한          제출          정답          맞힌 사람          정답 비율

 

10 초

256 MB

4119

1770

1189

42.283%

문제

조(Joe)는 중앙대학교 교수이고, 논리회로 설계 과목을 담당하고 있다. 그는 수업을 하면서 7명의 학생을 제외한 나머지 학생들에게 좋은 학점을 주겠다고 약속을 하였다.

Joe 교수님을 돕기 위해서 학생들의 최종 성적이 주어질 때, 그의 연구실인 You See Lab으로 데려갈 성적이 좋지 못한 7명의 학생, 칠무해의 성적을 뽑아보자.

입력

첫째 줄에 학생의 수 N(8 ≤ N ≤ 10,000,000)이 주어진다.

둘째 줄부터 N개의 줄에는 학생들의 성적이 무작위로 주어진다. 성적은 최소 0점부터 최대 100점까지 0.001 점 단위로 부여된다.

출력

하위 7명의 성적을 점수가 낮은 순으로 각 줄마다 출력한다. 하위 7명의 성적의 커트 라인에 동점자가 있을 경우에도 7명만 출력을 하면 된다.

예제 입력 1 복사

8
20.000
70.000
50.000
30.000
70.000
30.000
60.000
70.000

예제 출력 1 복사

20.000
30.000
30.000
50.000
60.000
70.000
70.000

 

https://www.acmicpc.net/problem/14729

14729번: 칠무해

 

틀린 코드

#include <bits/stdc++.h>
using namespace std;

int n; double a;
priority_queue<double, vector<double>, greater<double>> pq;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력하기
    cin >> n;
    while(n--){
        cin>> a;
        pq.push(a);
    }

    //2. 하위 7명 출력
    //소수점 출력
    cout<<fixed; cout.precision(3);
    for(int i=0;i<6;i++){
        cout << (double)pq.top() <<"\n";
        pq.pop();
    }

    return 0;
}

 

오류: 자리수가 다른 입력이 들어올때 제대로 처리 못함

https://www.acmicpc.net/board/view/33869

글 읽기 - 데이터를 추가해 주세요.

 

유의할 점

• 숫자 개수가 천만이라면 수가 너무 크기때문에, 벡터에 집어넣는 방식(모든 수를 저장하는 것보다는)보다는 우선순위 큐를 사용하여 일정부분만 저장하는 방식으로 해야한다. (정렬하는데에도 시간이 많이걸리고, 메모리도 많이 잡아먹기때문에)
• 소수점 출력하는 방법

cout << fixed; cout.precision(3); //소수점 3자리까지 출력

 

선생님 코드

#include <bits/stdc++.h>
using namespace std;

int n;
double temp;
priority_queue<double> pq;
vector<double> v;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기, 제일 작은 7개 빼고 다 버리기
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> temp;
        if(pq.size()==7){
            pq.push(temp); 
            pq.pop(); //7개 중 제일 큰거 pop
        } else pq.push(temp);
    }
    //2. 벡터에 저장하기
    while(pq.size()){
        v.push_back(pq.top());
        pq.pop();
    }
    //3. 역순으로 하여 출력하기
    reverse(v.begin(), v.end());
    //소수점 출력
    cout << fixed; cout.precision(3);
    for(double d:v) cout << d << "\n";

    return 0;  
}

 

• 우선순위 큐는 기본적으로 내림차순이므로 pq.pop()시에 가장 큰 수가 삭제된다.
• 큐의 원소들을 오름차순으로 정렬하기위해서는 벡터에 원소들을 저장한 후 reverse 시킨다.

 

라인스위핑

하나의 라인을 한번에 빗자루 쓸듯이 탐색하는 방법

한쪽 시작점을 기준으로 반대편 종료지점까지 스캔하며 마주치는 요소들에 대해 기준을 적용한다.

" 정렬된 요소들"을 "한번만 순회"하여 정답이 나오게 구현

출처: https://blogshine.tistory.com/120

[알고리즘] Sweeping Algorithm : 라인 스위핑 알고리즘

 

2170번: 선 긋기

선 긋기

 

시간 제한          메모리 제한          제출          정답          맞힌 사람          정답 비율

 

1 초

192 MB

15092

5405

3975

35.992%

문제

매우 큰 도화지에 자를 대고 선을 그으려고 한다. 선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다. 선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다고 하자.

이와 같은 식으로 선을 그었을 때, 그려진 선(들)의 총 길이를 구하는 프로그램을 작성하시오. 선이 여러 번 그려진 곳은 한 번씩만 계산한다.

입력

첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다.

출력

첫째 줄에 그은 선의 총 길이를 출력한다.

예제 입력 1 복사

4
1 3
2 5
3 5
6 7

예제 출력 1 복사

5

 

https://www.acmicpc.net/problem/2170

2170번: 선 긋기

 

위치가 -10억~10억이므로 단순히 cnt 배열로 풀 수 없다. (숫자 범위가 백만을 넘어감)=> 라인 스위핑 이용하기

int는 21억까지이므로 int 사용가능

 

자세한 설명은: https://blogshine.tistory.com/120

[알고리즘] Sweeping Algorithm : 라인 스위핑 알고리즘

 

선생님 코드

#include <bits/stdc++.h>
using namespace std;
int n,from,to,l,r,ret;
pair<int,int> L[1000004];
int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> from >> to;
        L[i] = {from,to}; //시작위치-끝위치 저장
    }
    //2. 선 길이 구하기
    sort(L, L+n); //오름차순으로 정렬
    l=L[0].first; r=L[0].second; //left, right 저장
    for(int i=1;i<n;i++){
        if(r < L[i].first){ //선끼리 떨어져있으면 선길이만큼 추가
            ret += (r-l);
            l=L[i].first;
            r=L[i].second;
        }
        else if(r>=L[i].first && r<=L[i].second) r=L[i].second; //선끼리 겹치면 끝점 늘리기(끝점 더 긴걸로 늘리기)
    }
    ret += (r-l);
    //3. 정답 출력
    cout << ret;
}

 

• 선이 겹치지 않을때와 겹칠때로 나눌 수 있다.
• 선이 겹치지 않을때는 선분 길이만큼 더해주고, 선이 겹칠때는 끝점을 늘려준다.
• 한번 수행시 정답이 나오므로 라인 스위핑이다.
• 꼭 정렬한 후 라인스위핑하기. (정렬되지않으면 시작점과 끝점 비교가 의도대로 되지 않는다.)

 

투포인터

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

1번 사진처럼 보통 하지만 1번처럼 안될때 2번처럼 하기

 

한쌍인 두개의 수를 다루는 문제에서 잘 사용된다.

 

3273번: 두 수의 합

두 수의 합 

다국어

한국어   

시간 제한            메모리 제한            제출            정답            맞힌 사람            정답 비율 

1 초

128 MB

32508

11557

8739

35.140%

문제

n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)

출력

문제의 조건을 만족하는 쌍의 개수를 출력한다.

예제 입력 1 복사

9
5 12 7 10 9 1 2 3 11
13

예제 출력 1 복사

3

 

 

https://www.acmicpc.net/problem/3273

3273번: 두 수의 합

 

내 풀이

#include <bits/stdc++.h>
using namespace std;
int n, x, sum, ret, a[100004];
int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> n;
    vector<int> v;
    for(int i=0;i<n;i++){
        cin>>a[i];
    } 
    cin >> x;
    //2. 오름차순으로 정렬하기
    sort(a, a+n);
    //3. 조건을 만족하는 쌍의 개수 출력하기
    int i=0,j=n-1;
    while((i<n) && (j>=0)){
        if(i>=j) break; //모두 조사하였으면 종료
        sum = a[i]+a[j];
        if(sum<x) i++; //구한 합이 더 작으면 작은 숫자 키우기
        else if(sum>x) j--; //구한 합이 더 크면 큰 숫자 작게하기
        else { //합이 되는 쌍을 찾으면 ret++, 다음 케이스로 넘어가기
            ret++; i++;j--;
        }
    }
    
    //4. 정답 출력
    cout << ret;


}

 

• 투 포인터를 이용할때는 큰 값과 작은값이 같아지거나 대소관계가 바뀔때  break 해주어야한다.

선생님 코드와 거의 로직이 같아서 생략한다.