Approach 문자열을 그냥 바로 대소 비교하면 된다는 것만 캐치하면 쉽게 풀 수 있다. 문자열에서 따로 숫자를 파싱하고 하면 상당히 복잡하게 생각할 수 있으나 제시된 시각의 틀이 동일하기 때문에 바로 문자열 비교를 통해 요구한 시간안에 출석을 했는지 여부를 판단해주면 된다. 문제에서 가장 중요한 부분이 개강 총회가 끝나고 스트리밍이 끝날때까지 채팅을 남긴 대상 중, 개강 총회가 시작하기 전에 등어온 사람만 출석이 된다는 것이다. 전자 조건은 문자열 비교를 통해 쉽게 해결할 수 있으나, 해당 사람이 시작하기 전에 출석한 Set에 속한 사람을 판단하는 것을 Set 자료 구조를 활용해주면 쉽게 해결할 수 있다. 문제 자체는 되게 쉽다. (문자열 처리만 잘 한다면) Code #include #define f..

Approach 1번 조건 때문에 기존에 대기열에 존재하는지 여부가 굉장히 중요하다는 것을 알 수 있다. 왜냐하면 대기열 Set에 존재하는 상황에서 이후의 query가 들어오게 되면 나중의 순서로 재배정되기 떄문이다. 이 지점에서 기존의 대기열을 set으로 관리하여 존재하는지 여부를 관리하면 된다는 생각을 할 수 있다. 다만, 문제의 요구사항 중 하나는 대기열의 성공순서를 고려해야하는 상황이므로 어느 타이밍에 대기열에 등장했는지를 파악하는 것이 중요하다. 즉, 어느 타이밍에 대기열에 들어왔는지를 반영하기 위해서 Set보다는 Map 자료구조가 적합하다는 것을 알 수 있다. 그러나, key가 학번이므로 Map이 내림차순으로 정렬된다는 것을 활용항 수 없다. 따라서 Map을 2개 만듦으로서 이 문제를 해결해주..

Approach 이 문제를 보고 파블로프의 개처럼 최댓값과 최솟값을 다루는 문제이므로 우선순위 큐를 생각할 수 있으나 잘 생각해보면 비효율적이라는 것을 쉽게 알 수 있다. 우선순위 큐를 활용한 접근 방법의 가장 큰 문제점은 최대힙과 최소힙이 서로 동기화가 안된다는 것이다. 즉 최대힙을 통해 지운 데이터가 최소합에 반영되기가 힘들다. 이 문제점을 해결하기 위해서 Map이나 Set 등의 자료구조등을 활용해서 지운 데이터인지를 계속해서 비교하는 방법등을 활용할 수 있으나 비효율적이다. 잘 생각해보면 Multiset은 order가 이미 힙트리 상에 저장되어있다. 즉, 이를 활용해주면 하나의 자료구조로 두 개의 값을 동시에 다룰 수 있는 장점이 있다. Codes Priority_queue를 활용한 방법 #incl..

Approach 전체에서 몇 퍼센트 해당하는지를 파악하는 것이므로, 쿼리에 대한 모든 정보를 받고 처리해야 한다. 이 부분에서 오프라인 쿼리 문제임을 인식해주면 된다. 추가적으로 Map container를 활용해주면 해당 set안에 몇 개 들어있는 상황인지를 쉽게 파악할 수 있다. + 어디까지 들어올지 모르는 상황이므로 while(getline(cin, t))를 사용하는 점을 유의깊게 보도록 하자. + cin.precision의 경우 정수부와 소수부의 자리수 개수의 합을 지정해주는 것이다. 소수점 이후의 자리부분을 설정하려면 cout

Approach 이 문제를 물론 네트워크 플로우를 활용해서 풀 수는 있는데, 그리디를 활용한 방법으로 접근해보자. 문제를 정확히 이해해보면, reordering 성질을 만족하는 것을 쉽게 파악할 수 있다. 예를 들어 다음과 같은 행렬이 있다고 하자. $$\begin{pmatrix} 1 &1 & 0 & 1 \\ 1 &0 &1 &1 \\ 1 &1 &1 &1 \\ 1&1 &1 &1 \end{pmatrix}$$ 행과 열의 합을 유지한 상태로 1로 표시된 2개의 element의 위치를 변경할 수 있다. 예를 들어, 첫번째 row vector의 2번째 element대신 3번째 element를 1로 만든 뒤 두번째 row vector의 2번째 element를 1로 만들고 3번째 element를 0으로 만든다. 즉, ..

Approach 자기보다 아래에 있는 트리에 물이 채워지면 현재 자신이 위치한 트리의 높이만큼의 물이 채워지는 방식이다. 따라서, 해당 위치에 얼마나 물이 채워져있는지는 자기 자신을 루트 노트로 가지는 subtree안에 속한 구간할을 구하면 된다. 따라서 트리의 구간합을 구하는 방식이므로 오일러 투어 테크닉(ETT)를 생각해주면 된다. 따라서 노드 i안에 있는 물의 양은 다음과 같다. $$query[dfs\_in[i], dfs\_out[i]] * depth[i]$$ 이해가 안된다면 다음 블로그 글을 참고하도록 하자. https://thekeykim.github.io/posts/BOJ_18227/ [백준] 18227 - 성대나라의 물탱크 C++ 문제링크 18227 - 성대나라의 물탱크 문제 성대나라에는 각..

Approach 각 세그먼트의 노드에서 가장 최댓값, 그 다음 최댓값을 가지고 있으면 해당 쿼리에서의 최댓값과 그 다음 최댓값을 쉽게 도출할 수 있다. 다만, 2개의 value를 핸들링해야하는 상황이므로 pair도 뭐 가능하긴한데 class를 활용해주었다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; class max_store{ public: int max_1; int max_2; max_store(){ max_1 = -1; max_2 = -1; } max_store(int a){ max_1 = a; max_2 = -1; } max_store(int a, int ..

Approach Subtree에 대한 정보를 가지고 이야기를 하고 있으므로, 오일러 투어 테크닉(ETT)를 활용하면 서브트리에 대한 정보를 쿼리 정보로 바꿔서 처리할 수 있다. 또한 추가적으로 쿼리에 대한 특정 수보다 작거나 크고 k번째 수의 경우는 머지 소트 트리를 활용해서 쉽게 풀 수 있다. 즉, 오일러 투어 테크닉(ETT)와 Mergesort Tree를 활용하면 쉽게 풀 수 있다. 느낌 자체는 https://viyoung.tistory.com/245 [백준 14287번] [세그먼트 트리 / 오일러 투어 테크닉] 회사 문화 3 Approach 가장 원초적으로 생각할 수 있는 풀이는 dfs로 계속 타고 내려가면서 계속 업데이트를 해주면 된다. 다만, 이 경우에는 시간복잡도가 $O(NM)$으로 시간이 초..