MZ 개발자

기본적으로 우선순위 큐는 삽입,삭제에 대해 O(logN)의 시간복잡도를 가진다. 또한 트리구조를 취하는 MaxHeap( 또는 MinHeap)으로 구현된다. 문제에서 Q의 종류중 D 1 은 가장 큰 값 삭제, D -1은 가장 작은 값 삭제를 수행하야 하지만 우선순위 큐 한개로는 불가능 하다. 따라서 MaxHeap, MinHeap으로 구현된 우선순위 큐 2개를 사용해야 한다. 여기 까지가 처음 생각한 방법이다. 하지만 문제는 두 큐가 동기화가 되지 않는다는 점이다. 한참을 고민하던도중 multiset이라는 자료구조를 이용하면 해결 가능하다는 것을 발견하였다. multiset이란 기본적인 set은 중복을 포함하지 않고 정렬되어있지만 multiset은 중복을 허용한 정렬된 자료구조이다. 또한 특정 값을 eras..

이 문제를 풀면서 아직 실력이 많이 부족하다는 것을 느꼈다. 처음 생각해낸 방법은 덱을 사용해서 문제마다 모든 조건을 처리해주는 정신 나간 짓을 하려고 하였다. 2번 3번 조건을 만족하기 위해 현재 내가 풀고있는 문제(now)가 있고 이 문제를 풀기 이전 풀어야할 문제(pre)를 설정하고 이상한 뻘짓을 많이 하였다... 문제를 보는 순간 어떤 알고리즘을 물어보는지 감이 오지 않아 어떻게든 내가 알고있는 알고리즘 내에서 최대한 풀어보려고 시도하였다. 또한 문제가 잘 이해되지 않았다. 처음에 답이 두개인가?? 생각도 하고 질문 답변을 확인한 결과 조금 이해가 되었다. 어느덧 3시간 고민 후... 각 N 마다 먼저 풀어야하는 문제를 우선순위 큐에 넣어 DFS 탐색까지 도달였다. 하지만 결과는 DFS로는 풀수 ..