10주 C++ 코딩 테스트 완료 | 알고리즘 IT 고용 데이터 구조 문제 해결 – 인프라 | 강의
네이버, 카카오, 삼성 코딩테스트 합격!
10주 C++ 코딩 테스트 강의 완료!
, 강의 소개 | 하부 구조
www.inflearn.com
https://blog.naver.com/jhc9639/222319124359
(알고리즘 강의) 5주차. 두 개의 포인터를 휩쓰는 탐욕스러운 선
안녕하세요. 큰 바위입니다.
이 주차장에 있는 탐욕스러운 싹쓸이 투포인터를 보자. 이 3가지…
blog.naver.com
위 강좌를 듣고 작성한 글입니다.
적은
현재 상태 인덱스에서 당신이 최고라고 생각하는 해가 답이다BE
각 단계의 국부적 최적해는 결국 전역 최적해가 된다.
- 최적의 하부 구조를 가져야 합니다.
- 탐욕 속성이 입증되어야 합니다.
위의 두 속성을 검증하기 어려우므로 시간 또는 공간 복잡도가 너무 커서 경우의 수를 셀 수 없을 때 Greedy를 시도해야 합니다.
학습 취소 -> DP -> 탐욕 순서대로 생각해 봅시다.
- 순서가 지정된 대기열과 우선 순위가 지정된 대기열을 사용하는 두 가지 제한적인 방법이 주로 있습니다.
*연도가 틀려도 처음부터 다시 시작하는 것이 중요합니다.
1931. 회의실 지정
| 2초 | 128MB | 160866 | 50860 | 35722 | 29.751% |
문제
회의실이거 있는데 써보고싶다 N 세션에 대한 회의실 사용 테이블을 만들려고 합니다.
각 회의에 대해 시작 시간과 종료 시간이 주어집니다.
각 회의가 겹치지 않고 회의실을 사용할 수 있는 최대 회의 수찾아보자 하지만 회의가 시작되면 중간에 멈출 수 없고 다음 회의는 회의가 끝나는 것과 동시에 시작될 수 있다.
회의 시작 시간과 종료 시간은 같을 수 있습니다.
이 경우 시작하자마자 끝나는 것을 상상할 수 있습니다.
기입
첫 번째 줄에 세션 수 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호: 회의실 배정
(1,4), (5,7), (8,11), (12,14)를 사용할 수 있습니다.
www.acmicpc.net
먼저 그림을 그린다
흐름
암호
#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 초 | 256MB | 48839 | 11301 | 7925 | 21.841% |
문제
세계적인 도둑 상덕은 보석상을 털기로 결심한다.
상덕이가 털던 보석가게에서 총 N개의 보석 있습니다.
모든 보석 가중치 수요일 및 가격 Vi상덕인이 있다 K 가방 가지고 있어 어떤 포켓에도 넣을 수 있습니다 최대 무게는 Ci입니다.
오전. 가방 안에 보석까지꽂을 수만 있습니다
상덕이는 훔칠 수 있다 보석의 최대 가격검색 프로그램 작성
기입
N과 K는 첫 번째 줄에 표시됩니다.
(1 ≤ N, K ≤ 300,000)
다음 N 행 각각 보석 정보 수 및 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: 보석 도둑
N과 K는 첫 번째 줄에 표시됩니다.
(1 ≤ N, K ≤ 300,000) 다음 N행에는 각 보석의 Mi, Vi 정보가 주어진다.
(0 ≤ Mi, Vi ≤ 1,000,000) 다음 K 행은 가방에 담을 수 있는 최대 무게 Ci를 나타냅니다.
(1 ≤ Ci
www.acmicpc.net
흐름
암호
#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;
}