그리디

[골4] 1715 - 카드 정렬하기

#include #include #include #pragma region 입출력 속도향상 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion using namespace std; int main() { FAST_IO(); int n, ans = 0; cin >> n; priority_queue pq; if (n == 1) { cout tmp; pq.push(tmp); } while (!pq.empty()) { int sum = 0; sum += pq.top(); pq.pop(); if (!pq.empty()) { sum += pq.top(); pq.pop(); ..

탐욕 / 그리디 알고리즘 (Greedy Algorithm)

Greedy Algorithm 탐욕 알고리즘(그리디 알고리즘)은 특정 경우들 중 하나를 선택할 때, 그 순간에 가장 최적의 경우를 선택하는 알고리즘이다. 목적지까지 최단 경로로 가야 하는 상황을 예로 들어보자. 목적지를 향해 가던 중, 갈림길을 만났다. 그리디 알고리즘에서는, 다음과 같은 갈림길들 중 현재 상황에서만 최적인 경우를 선택한다. 따라서 위 그림에 그리디 알고리즘을 적용한다면, 직진을 하게 될 것이다. 하지만 만약 직진으로 간 다음 경유지에서 목적지까지의 거리가 100km이고, 다른 두 갈림길의 경유지에서 거리는 10km라면 어떻게 될까? 그리디 알고리즘을 통해 최적의 경우를 선택했지만, 결과적으로는 직진을 선택했기 때문에 목적지까지 최단경로로 갈 수 없게 된다. 이와 같이 그리디 알고리즘은 ..

[실1] 1931 - 회의실 배정

#include #include using namespace std; pairarr[100001]; int main() { int n,a,b,cnt=1; cin>>n; for (int i = 0; i > b >> a; arr[i] = {a, b}; } sort(arr, arr + n); int end=arr[0].first; for (int i = 1; i < n; i++) { if (end