Algorithm

[알고리즘, 틀림] 백준 1700 멀티탭 스케쥴링 // 그리디, 페이지 교체 알고리즘

https://www.acmicpc.net/problem/1700* 풀이1 vector, 배열에 삽입, 삭제 불편 -> unorder_set사용 (find O(1)임)find후 없으면 s.end를 리턴함최초로 찾은후 break 해야하는 이유#include using namespace std;typedef long long ll;ll n,k,ret;unordered_set s;int arr[104];int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>k; for(int i=0;i>arr[i]; } for(int i=0;i#include using namespace std;int main() { // 입출력 최적화 i..

[알고리즘] 백준 1202 보석도둑 // 그리디, pq

https://www.acmicpc.net/problem/1202* 추론과정문제는 보석 도둑 문제인데, 각 보석은 무게와 가격을 가지고 있고, 가방에는 각각 최대 무게가 있어서 각 가방에 최대 한 개의 보석을 넣을 수 있다. 우리의 목표는 훔칠 수 있는 보석들의 최대 가격 합을 구하는 거다. 일단, 가장 먼저 생각나는 접근은 그리디 알고리즘일 것 같다. 왜냐하면 최적의 선택을 단계적으로 해나가야 하기 때문이다. 그리디로 풀기 위해서는 어떤 기준으로 선택을 해야 할지 결정해야 한다. 보석을 가격이 높은 순서대로 정렬하고, 각 보석을 담을 수 있는 가장 작은 가방에 넣는 방법이 있지 않을까? 예를 들어, 가장 비싼 보석부터 차례대로 해당 보석의 무게를 수용할 수 있는 가장 작은 가방에 배정하는 거다. 이렇게..

[알고리즘] 백준 1931 회의실 배정 // 그리디, 라인스위핑, 정렬

https://www.acmicpc.net/problem/1931* 풀이start로 정렬? -> 반례 -> 우디르end? -> 되네#include using namespace std;typedef long long ll;int n,ret;vector> v; // int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin>>n; for (int i=0;i>a>>b; v.push_back({b,a}); } sort(v.begin(),v.end()); int endTime=v[0].first; ret++; for(int i=1;i

[알고리즘] 백준 14469 // 그리디, 라인스위핑은 막대기를 그려라

https://www.acmicpc.net/problem/14469* 풀이1pq로 비비려다가 망함 * 풀이2시간문제는 수직선으로 표현하라.#include using namespace std;typedef long long ll;int n,ret;vector> v; // int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin>>n; for (int i=0;i>a>>b; v.push_back({a,b}); } sort(v.begin(),v.end()); int time=v[0].first+v[0].second; for (int i=1;i

[알고리즘] 백준 1787 컵라면 // 그리디 , pq

https://www.acmicpc.net/problem/1781 * 풀이최대값은 최대를 많게 하거나, 최소를 적게하거나!그리디는 정렬, pqday 순정렬 => 배치를 신경안써도됨최소힙 => 이전날짜가 비효율적인경우, 그걸 뺄수있음day: 1  2     2 컵 :   1 100 200day1은 선택안하는게 나았음! #include using namespace std;typedef long long ll;int n, ret; // n: 문제의 개수, ret: 최종 컵라면 개수vector> v; // 을 저장하는 벡터priority_queue, greater> pq; // 컵라면 개수를 저장하는 최소 힙int main() { ios_base::sync_with_stdio(0); cin.tie(0);..

[알고리즘] 백준 9935 문자열폭팔 // 폭팔은 스택, 끝문자만 비교하라

https://www.acmicpc.net/problem/9935*풀이1 1. 입력 받기: - 문자열 s (원본 문자열) - 문자열 t (폭발 문자열)2. 변수 초기화: - n = s의 길이 - len = t의 길이 - stk = 빈 스택 (문자 저장용)3. 원본 문자열 s 순회: for i = 0부터 n-1까지: - 현재 문자 s[i]를 스택에 push - 만약 스택의 top이 s[i]와 같고, 스택 크기가 len 이상이면: - tmp = 빈 문자열 (임시 저장용) - for j = 0부터 len-1까지: - tmp에 스택의 top을 추가 - 스택에서 pop - tmp를 뒤집음 ..

[알고리즘] 백준 2109 순회강연 // 그리디 , pq, 최대값은 최소를 적게 or 최대를 많게

https://www.acmicpc.net/problem/2109* 풀이1day기준 오름차해서 각각 day에서 비싼거 뽑으면 될듯?참고) pq에 줄 cmp는 struct로 줘야함struct cmp { bool operator()(const pair& p1, const pair& p2) { return p1.first  * 풀이2day기준 오름차, 내림차 -> 오름차 선택최대 = 최소를 적게 or 최대를 많게 -> 최소를 적게 선택pq.size에 day의미 부여greater(최소힙) => 돈 적은거 pop#include using namespace std;typedef long long ll;int n,ret;vector> v;priority_queue,greater> pq; //최소힙i..

[알고리즘] 백준 6549 히스토그램 // 스택 심화, 암기..

https://www.acmicpc.net/problem/6549 * 풀이스택문제는 오름차순, 내림차순, 같은경우를 나눠생각이중에서 계산해야 되는 걸 골라야함!이문제는 내림차 일때, 기존의 막대들이 확장불가 ( 확정) -> 계산을 드가면됨.이때, 패딩을 0으로 줘서 마지막도 강제 내림차로만들고 i = n+1 까지 돌려서, 마지막에 자동계산토록 함 특이한점은 pop을 한후에 전전 막대의 idx 차이를 너비로 사용 #include using namespace std;typedef long long ll;ll n, arr[100000+4];// int main(){ ios_base::sync_with_stdio(0); cin.tie(0); while(1) { cin>>n; if(n..