Approach Top-down 방식으로 DP를 짜면 중복되는 계산을 줄이면서 계산을 할 수 있을 것이라는 느낌이 든다. 추가적으로 N이 매우 큰 상황이므로, 기존의 DP처럼 메모리를 미리 확보하고 저장하는 방식을 채택할 수 없고 Map 자료 구조를 활용해서 기존의 연산을 수행했는지 여부를 확인해주면 된다. 1. 기존에 연산을 수행한 값 : 메모이제이션을 사용. 즉 Map에서 value값을 그대로 읽어주면 된다. 2. 기존에 연산을 수행하지 않은 값 : Top-down을 활용하여 구해준 뒤, Map에 저장해주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; t..

Approach key와 value가 등장하는 상황이므로 Map을 활용하면 된다는 것은 쉽게 추측할 수 있다. 이 문제에서 가장 독특한 지점은 가장 가까운 key값에 매핑한다는 것인데, 이 부분은 Map 안에 존재하는 lower_bound나 upper_bound method를 활용해서 구해주면 된다. 다만, 해당 method를 통해 구해준 iterator가 begin()이나 end()와 같은 경우만 예외처리를 잘 해주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int n, m, k; map s; int find_key(int t){ if(s.lower_b..

Approach 일단, 빈도 순으로 정렬하는 것이므로 Map 자료 구조를 활용해서 몇 번 출현했는지를 체크해주면 된다. 독특한 지점은 등장하는 횟수가 같다면 먼저 나온 것이 앞에 있어야 한다는 점이다. 이 부분은 먼저 나오는 번호를 따로 저장해두면 된다. 개인적으로는 문제에서 C를 준 이유가 있다고 판단하여서 vector를 활용해 정렬하였다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; bool compare(pair &a, pair &b){ if(a.first.first == b.first.first) return a.first.second < b.first.se..

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으로 만든다. 즉, ..