thisisuser's study

최근 PS 재활치료를 하면서 기본기가 많이 부족하다는 것을 느꼈다.당장 플레5 하나 잡고 풀어보려니까 뇌가 많이 아팠다. 이 문제같은 경우 PS할 때 한번은 짚고 넘어가면 좋을 것 같아서 복습 겸 정리를 해본다.2957번: 이진 탐색 트리 (acmicpc.net) solved.ac: Platinum V (2024.09.10)문제는 이거 구현해서 C값 출력하라는 것이다.딱 봐도 그대로 구현하라는 문제는 절대 아니다. 편향 트리 반드시 주긴 할 거다. 먼저 저 카운터 값은 노드의 깊이를 의미한다는 것을 알 수 있다.임의의 노드에 대해 자식이 존재한다면 왼쪽 자식은 반드시 노드보다 작고, 오른쪽 자식은 반드시 노드보다 크다.일단 대충 트리가 있고, X가 삽입되는 상황이라고 가정해 보자. 어떤 노드 P에 대해 ..

Heavy-Light Decomposition이란 트리를 여러 개의 선형 구조로 분해하여 접근할 수 있게 해주는 기법입니다.먼저 트리 위에서 다음과 같은 쿼리가 주어지는 문제를 생각해 봅시다.정점 i의 가중치를 v로 변경한다.두 정점 간의 경로 상의 정점의 가중치 합을 구한다.당연히? $N \le 100000$ 정도입니다.배열 위에서였다면 바로 신나게 세그먼트 트리를 짰겠지만, 트리 위이다 보니 바로 적용하기는 어렵습니다. 배열에서는 되고, 트리에서는 안 되는 이유는 무엇일까요?당연한 소리지만, 트리는 배열과 달리 비선형구조이기 때문입니다. 그렇다면 이렇게, 트리를 여러 개의 선형 구조로 쪼갠다면 어떨까요?이 경우에는 부분 부분에 대해서는 세그먼트 트리로 관리해줄 수 있겠다는 생각이 듭니다.문제는 이걸 ..

일단 시간복잡도는 제껴두고, 이 문제를 풀어봅시다.13323번: BOJ 수열 1 (acmicpc.net)  만약 $N \le 10000$ 정도라면, 약간의 관찰을 통한 간단한 $O(N^{2})$ DP를 통해 해결할 수 있습니다.대충 '$DP(x, k) = x$번째 값을 $k$로 만들었을때 최소 연산 어쩌구' 꼴로 구성해주고,$DP(x, k) = \min (1 \le i \le k - 1) DP(x-1, i) + |a[x] - k| $ 이라 정의하여 간단히 해결할 수 있습니다. 하지만 만약 $N$이 무지막지하게 커져서, 한 $10^{6}$ 쯤 된다고 해봅시다.그러면 당연히 시간 내에 풀 수 없을 것입니다. 물론 그 전에 메모리가 터지겠지만요. 문제를 해결하기 위해서는 DP(x, k)를 k에 따른 함수로 해..