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

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

AlexNet First large scale convolutional nerual network이다. 특징은 1. ReLU를 처음 사용하였다. 2. Norm layers를 사용하였다. (지금은 대부분 쓰지 않는다.) 3. 드롭아웃 0.5로 설정 4. batch size 128 5. SGD momentum 0.9 6. Learning rate 1e-2 7. L2 weight decay 5e-4 8. 7개를 앙상블 처리하여 정확도 향상 추가적으로 잘 보면 상하로 2개로 나뉘어있는 것을 볼 수 있는데, 이는 네트워크가 2개의 Network로 분산되었기 때문이다. 즉, 맨 처음 CONV layer를 보면 필터가 96개인데 각 GPU마다 48개씩 절반으로 나누어 연산을 병렬적으로 처리하는 것이다. ZFNet 전..

writing