baekjoon 1700:멀티탭 스케줄링
1700번 멀티탭 스케줄링
접근
//가장 나중에 쓸 전자기기를 뽑는게 왜 최적의 해를 보장할까? //belady’s min algorithm //논문 보셈
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//1700
#include <iostream>
#include <vector>
#include <map>
#include <limits.h>
using namespace std;
int findNear(vector<int>& v, int x, int y); //x부터 y를 조사
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, k; cin >> n >> k;
vector<int> v(k);
map<int, int> m;
int size = 0;
int changeCount = 0;
for(int i = 0; i < k; i++){
cin >> v[i];
}
for(int i = 0; i < k; i++){
if(m.find(v[i])!=m.end()){
continue;
}
if(size < n){
m[v[i]] = 1;
size++;
}
else{
int farthest = 0;
int farthestNum = 0;
for(auto j = m.begin(); j != m.end(); j++){
// cout << j->first;
int temp = findNear(v, i+1, j->first);
// cout << temp << " ";
if(temp > farthest){
farthest = temp;
farthestNum = j->first;
}
}
// cout << farthestNum <<"지우기\n";
m.erase(farthestNum);
m[v[i]] = 1;
changeCount++;
}
}
cout << changeCount;
return 0;
}
int findNear(vector<int>& v, int x, int y){
for(int i = x; i < v.size(); i++){
if(v[i] == y){
return i;
}
}
return 200;
}
배운 점
greedy의 어려운 점은 그 아이디어를 떠올리는 게 어려운 것 같다.
greedy에 대해 찾아보면 greedy choice property(탐욕적 선택 속성)과 최적 부분 구조(optimal substructure)에 대해 언급하는 사람이 상당히 많다.
하지만 블로그마다 좀 이해하기 어렵거나, 잘못된 방법으로 서술해둔 사람이 많은 것 같다.
optimal substructure은 어떤 problem을 풀 때 subproblem을 정의해서 각 subproblem에서 optimal solution을 구하고 그 solution들을 합쳐서 전체 problem을 풀 수 있을 때 optimal substructure라고 한다.
greedy choice property는 locally greedy choice를 했을 때 global optimal solution이 획득가능하다는 것이다.
사실 이런 두 조건을 생각하면서 greedy 문제를 푸는 것은 의미가 없다.
greedy알고리즘의 전개방식을 생각해보면 되는데, 각 단계에서 한가지 기준을 세워두고 그 동일한 기준을 적용시켜 매 단계에서 선택을 해서 solution을 얻어낸다.
위와 같은 방식으로 global optimal solution이 획득 될 것 같으면 greedy, 매번 기준이 없고 다 해봐야한다면 dp인 것이다.
greedy알고리즘 증명 방식도 비슷하다. 매 단계 greedy한 선택을 해도 optimal이 유지된다는 것을 증명하면 greedy알고리즘 증명된 것이다.