Approach 문제 상황을 재구성해보면 존재하는 맛 중에 경계값에 위치한 맛을 찾아주면 된다. 상황 자체는 https://viyoung.tistory.com/246 와 근본적으로 동일하다. [백준 19646번] [세그먼트 트리] Random Generator Approach "dp[i] : i번째 수까지 활용했을 때 존재하는 수"라고 잡아서 dp로 풀 수 있을 것처럼 보이지만 이 문제는 업데이트가 자주 나오고 있는 상황이므로, dp 값이 계속 바뀐다. 따라서 이 문제는 dp viyoung.tistory.com 위 문제의 경우는, 경계값을 찾가나가되 업데이트 과정에서 해당 숫자들을 모두 지워주는 형태이다. 반면 이 문제의 경우는 -1을 업데이트 처리해주면 된다. 근본적인 문제의 접근 방법 자체는 완전히 ..

Approach 이 문제의 예시로 제공된 수에서 위치를 가장 판단하기 쉬운 것은 8이다. 왜 8이 가장 마지막 자리에 있는지를 생각해보면 자기보다 작은 수가 한 개도 없고, 가장 큰 숫자이므로 가장 뒤에 오는 것이다. 마찬가지로 7의 경우를 판단해보면 뒤에서부터 남은 자리 중 2개를 건너뛰고 앉으면 된다. 즉, 이를 통해 구간합을 관리하고 있다는 느낌을 받으면 된다. 추가적으로 큰 수부터 작은 수로 자리를 채워나가면서 업데이트 해주면 된다. 다만, 해당 자리가 어딘지를 판단해주기 위해서는 이분탐색으로 파악해주면 된다. 느낌이 https://viyoung.tistory.com/246 와 정말로 비슷하다. 이분탐색을 통해 쿼리의 인덱스를 찾는 느낌이 매우 유사하다. [백준 19646번] [세그먼트 트리] R..

Approach 문제를 풀기 위해서 가장 중요한 것은 출제자의 의도를 읽는 것이다. 어느 범주에서 출제 했는지를 검토해보면, 이 문제는 주어진 쿼리의 최대값을 구하는 문제와 정확하게 동지이다. 추가적으로 범위라고 표현하기는 했지만, 궁극적으로 제시하고 싶은 정보는 쿼리의 길이이다. 슬라이딩 윈도우 기법을 활용해서 가능한 최저부터 최고까지 쭉 쓸고 가면 된다. 시간 복잡도는 $O(NlgN)$정도이므로, 뭐 충분하다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int seg[4000000]; int update(int node_index, int node_left, ..

Approach 다른 기준으로 쿼리를 관리하고 있으므로, Segment tree를 2개 각각 관리해주면 된다. 홀수의 구간합을 seg_odd, 짝수의 구간합을 seg_even에서 관리해주면 된다. 다만, update하는 과정에서 이전의 status가 변경될 수 있기때문에 하위 노드의 값이 바뀜에 따라 해당 index를 포함하고 있는 쿼리를 전부 업데이트 해주어야 한다. 느낌 자체는 구간 곱 쿼리의 처리 방법과 비슷하게 해주면 된다. https://viyoung.tistory.com/248 [백준 11505번] [세그먼트 트리] 구간 곱 구하기 Approach 구간 합 문제랑 비슷하면서도 조금 다르다. 구간 합을 구하는 경우는 update하는 과정에서 하위 노드들의 값을 재참조할 필요가 없이, parame..

Approach 구간 합 문제랑 비슷하면서도 조금 다르다. 구간 합을 구하는 경우는 update하는 과정에서 하위 노드들의 값을 재참조할 필요가 없이, parameter로 주입한 value값을 토대로 갱신만 해주면 된다. 구간 곱의 경우는 0의 존재때문에 다시 갱신해주는 것이 편하다. 잘 생각해보면 update를 할 때, 변한 index를 포함하지 않는 부분은 기존 seg값을 재활용하고 포함하는 경우만 갱신해주면 된다. 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]; ll update(int node..

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..