Approach 쿼리에 대한 업데이트가 자주 일어나고, 구간합을 구하는 상황이므로 세그먼트 트리를 활용해주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef long long ll; ll seg[4000000]; void update(int node_index, int node_left, int node_right, int index, ll value){ if(index < node_left || node_right < index) return; // Out of Bound seg[node_index] += value; if(node_left ==..

Approach "dp[i] : i번째 수까지 활용했을 때 존재하는 수"라고 잡아서 dp로 풀 수 있을 것처럼 보이지만 이 문제는 업데이트가 자주 나오고 있는 상황이므로, dp 값이 계속 바뀐다. 따라서 이 문제는 dp로 풀 수 없다. 업데이트가 자주되고 특정 숫자까지 사용하였을 때 개수가 중요하므로 구간합과 쿼리로 문제 상황을 이해할 수 있다. 해당하는 숫자까지 사용했을 때의 개수가 주어진 숫자보다 더 큰 것 중 가장 작은 것을 찾아야 하는 상황이다. 특정 임계점을 기준으로 해당 경향성이 갈리므로 이분탐색을 활용해주면 된다. 따라서 시간 복잡도는, 이분탐색에서 logN이고 세그먼트에서 탐색이 logN, 마지막으로 모든 숫자에 대해 해당 작업을 처리해야하므로 N을 곱해서 $O(N(lgN)^2)$이다. C..

Approach 가장 원초적으로 생각할 수 있는 풀이는 dfs로 계속 타고 내려가면서 계속 업데이트를 해주면 된다. 다만, 이 경우에는 시간복잡도가 $O(NM)$으로 시간이 초과하게 된다. 이때 등장하는 방법이 Euler tour technique이다. 해당 방법을 통해 트리를 Array로 필 수 있게 된다. 기존에 진행하던 DFS 과정을 잘 생각해보면, 일종의 재귀적으로 계속해서 해당 노드를 기준으로 밑으로 내려가게 된다. 즉, DFS에서 방문순서를 기준으로 index를 부여할 수 있게 된다. 이를 바탕으로 다음과 같은 식을 잡을 수 있다. dfs_in[i] : 노드 i를 포함한 i의 subtree를 방문하는 Euler trail의 시작 index dfs_out[i] : 노드 i를 포함한 i의 subt..

Approach 특정한 구간에 대한 정보를 묻고 있는 상황이므로 세그먼트 트리 자료구조를 활용할 수 있지 않을까라고 판단해주면 된다. 이때, 퀘스트가 총 21억개로 상당히 많은 것과 달리 처리한 퀘스트는 최대 2백만정도 밖에 존재하지 않는다. 따라서 처리한 퀘스트를 기준으로 좌표압축을 해주고, 특정 쿼리에 대한 해결한 퀘스트의 개수를 구해주는 방식으로 이 문제를 해결할 수 있다. 단, 이런 방식으로 처리하려면 입력값으로 들어오는 좌표들을 미리 한번에 받아두어야하므로 미리 정보를 다 저장해둔다. 처음에 접근한 방식은 해결한 퀘스트 번호만을 가지고 좌표 압축을 진행하였다. 다만 이 방식의 문제점은, request에서 퀘스트 번호가 주어졌을 때 무엇을 포함하고 포함하지 않을 것인지에 대한 기준이 모호하다. 만..

Approach 이 문제에 대해서 잘 고찰해보면, 어떤 기업이 선택되는 것은 이전 기업에 얼마만큼의 투자했는지에 의해서 결정된다. 따라서 이러한 측면에서 관계식을 통해 표현할 수 있으므로 DP라고 인식해야 한다. Let $dp[i][j]$ : the amount of maximum profit when we investing exactly $j$ until considering $i$'th element $dp[i][j] = \underset{k \in R, \forall k \in [0,j]}{max}(dp[i - 1][j - k] + b[i][k])$ 즉, i번째 기업까지를 고려해서 투자할 때, i - 1번째 까지의 투자 데이터를 가지고 있으면 된다. 그렇게 되면 투자 금액이 동일할 때, 최대의 이익..

Dynamic programming이란? 복잡한 문제를 여러 간단한 문제로 쪼개서 푸는 것 기본적으로 고등학교 때 학습하였던, 점화식을 활용하여 푸는 방법론이라고 이해해도 무방한다. 구현 방법 구현 방법은 크게 2가지가 있다. 반복분 장점 빠르고 메모리 측면에서 이득을 본다. DP 최적화 작용이 쉽다. (덱 DP, 세그 DP) 단점 테이블을 채우는 순서를 고려해야 한다. 순서가 복잡한 경우 사용하기 어렵다. (트리 DP, 비트 DP) 재귀 (Memoization을 사용) 장점 DP를 채우는 순서를 고려하지 않아도 되나, memoization을 사용하여 동일 반복 계산을 피한다. 순서가 복잡한 경우에도 처리하기 쉬움 (트리 DP, 비트 DP) 단점 반복문에 비해 느리고 메모리가 많이 든다. DP 최적화 작..

접근 방법 일단, 어차피 카드 묶음이 1개씩 지워지는 상황이므로 무조건 큰 숫자가 나중에 묶이는 것이 유리하다. 그렇지 않으면 반복해서 묶이게 되어 숫자가 더 커지기 때문이다. 따라서, 숫자가 작은 것을 먼저 선택하기 위한 자료 구조가 필요하므로 우선순위 큐 자료구조를 활용해주면 된다. 코드 #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int main(void){ fastio; int n; cin >> n; priority_queue pq; for(int i = 0; i > temp; pq.push(temp); } int res..

접근 방법 우선순위 큐에 N만큼의 크기를 유지시키면서 pq의 최솟값을 갱신시켜주면 결과적으로 전체 세트의 N번째 최댓값을 쉽게 구할 수 있다. Priority queue 사용 느낌에 대해서 다시 한번 정리하는 용도로 정리해주면 된다. 코드 #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int main(void){ fastio; int n; cin >> n; priority_queue pq; for(int i = 0; i > temp; if(pq.size() < n) pq.push(..