- [ 장르 ] Heap 또는 Priority_queue
- [ 문제 ]
11279번: 최대 힙
첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이�
www.acmicpc.net
- Code 1 ( 힙 을 구현한 ver. )
#include <iostream>
#include <vector>
using namespace std;
vector<int> arr;
int n = 0;
void downHeap(int idx)
{
int greater, tmp;
if (idx * 2 <= arr.size()-1)
{
greater = idx * 2;
if (idx * 2 + 1 <= arr.size()-1)
if (arr[greater] < arr[idx * 2 + 1])
greater = idx * 2 + 1;
if (arr[greater] > arr[idx])
{
tmp = arr[idx];
arr[idx] = arr[greater];
arr[greater] = tmp;
downHeap(greater);
}
}
}
void upHeap(int idx)
{
int max;
if (idx / 2 >= 1)
{
if (arr[idx] > arr[idx / 2])
{
max = arr[idx];
arr[idx] = arr[idx / 2];
arr[idx / 2] = max;
upHeap(idx / 2);
}
}
}
void InsertItem(int data)
{
arr.push_back(data);
upHeap(arr.size()-1);
//n = n + 1;
}
int removeMax()
{
if (arr.size() >= 2)
{
int rootValue = arr[1];
arr[1] = arr.back();
arr.pop_back();
downHeap(1);
//n = n - 1;
return rootValue;
}
}
int main()
{
cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false); // ★ C++의 입출력속도개선의 매우중요
int opcnt,X;
arr.push_back(0);
cin >> opcnt;
for (int i = 0; i < opcnt; i++)
{
cin >> X;
if (X == 0)
{
if (arr.size() == 1)
cout << 0 << '\n'; // ★ 개행도 endl이 아닌 '\n'을 쓸 것
else
cout << removeMax() << '\n';
}
else
InsertItem(X);
}
return 0;
}- Code 2 ( Priority_queue를 활용한 ver. ( 정확히는 힙은 아닌 것 같다. )
#include <iostream>
#include <queue>
using namespace std;
int main()
{
cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
priority_queue<int> q; // 우선순위 큐 ( FIFO,First In First Out )
int opcnt,X;
cin >> opcnt;
for (int i = 0; i < opcnt; i++)
{
cin >> X;
if (X == 0)
{
if (q.empty())
cout << 0 << '\n';
else
{
cout << q.top() << '\n'; // 우선순위 큐의 front 요소출력
q.pop(); // front요소 pop
}
}
else
q.push(X); // 우선순위 큐는 push하면서 자동으로 front에서부터 내림차순정렬
}
return 0;
} " 알고리즘 문제를 풀 때는 딱 어떤 자료구조를 이용해야하는지 정해진 건 없다.
그 문제에서 요구하는 것이 아니어도 좀 더 효율적이라면 그걸 쓰자. "
[ CheckPoint ]
- 문제는 간단하다고 생각했으나 풀면서, 생각보다 몰랐던 부분, 생각해야 할 부분이 많았던 문제였다.
- 먼저, 최근에 나는 Heap에 대한 이론을 깨우쳐서 이 문제를 처음에는 힙을 만드는 과정의 삽입,삭제를 일일히 구현해서 메인에서 사용했다.
- 근데 생각해보니, 이 문제만 봤을 떈, 결국 삽입시에는 상관없고, 삭제하면서 출력시에 최대 값만 출력하면 되는 문제였다보니, 꼭 힙을 써야할까 ?
생각이 들었다. 결론은 그러지 않아도 된다 !- C++로 알고리즘 풀면서 이번에 queue container에 priority_queue를 쓰면
매우 유용한 부분이 또 있다는 것을 알았다.- 이는, queue와 기본적으로 FIFO형태라 보면 되는데, 특이점은 요소를 삽입시, default옵션이 자동으로 내림차순으로 PQ안에 요소들이 정렬된다는 것!
문제에선 삭제시, 배열 내에 최대값을 삭제하면서 출력하는 것이 었으니
queue.top( )을 통해서 큐에 front에 요소를 top( )하고, 후에 pop( )을하면 간단했다.- 그리고, 무엇보다 이번에 가장 중요한 포인트는, 입출력과 관련된 시간이었다. 로직은 분명히 맞다. 맞는데. 이상하게 계속 시간초과가 뜬다. 이래저래 수를 써봤는데 변화가 없었다. 그러던 차에 구글링을 했더니 중요한 사항을 발견했다.
- 글의 내용에서, C++기준으로 정리를 하자면, 입출력을 할때, 조금이라도 더 빠른 실행시간이 필요하다면, C++의 입출력인 cin,cout에 대해서
cin.tie(NULL) , cout.tie(NULL) , ios_base::sync_with_stdio(false) 를 메인 문두에 선언- C++에서 개행 시에도 endl보다 '\n'을 사용하는 것이 속도적인 면에도 좋다.
그 외 백준알고리즘문제를 풀면서 참고해야 BOJ(Baekjoon) 참고사항 링크를 아래에 걸어둔다.
https://www.acmicpc.net/blog/view/55
728x90
반응형
'Algorithm Practice > [ Baekjoon ]' 카테고리의 다른 글
| [Baekjoon][#10866] 덱(Deque) (0) | 2020.09.24 |
|---|---|
| [Baekjoon][#11729] 하노이 탑 이동순서 (0) | 2020.09.23 |
| [Baekjoon][#18258] 큐 2 (0) | 2020.09.22 |
| [Baekjoon][#1991] 트리순회 (0) | 2020.09.21 |
| [Baekjoon][10828번] 스택 (0) | 2020.09.18 |
