Algorithm/BOJ

[BOJ] - 내 생각에 A번인 단순 dfs문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy) 극좌표압축 + 스위핑 + 완전탐색 + maximum subarray

https://www.acmicpc.net/problem/18251 18251번: 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy) 욱제는 🎄포화이진트리🎄를 종이에 그렸다. 노드에 정수 가중치도 채워 넣었다. 욱제는 적당한 직사각형 영역을 잡아서, 영역 내에 있는 노드들의 가중치 합을 최대로 하고 싶다. 직사각형은 www.acmicpc.net 문제자체가 참 난감하다. 처음 든 생각은, 금광세그처럼 좌표를 압축한 다음에, 완전 탐색을 하는 것이였다. 그리고 잘 생각해보면, 2차원 스위핑을 1차원으로 치환할 수 있는데, dfs를 통해 각 노드에 시퀀스와 깊이를 저장해주면 이가 충분히 가능하다. import sys input = sys.stdin.readline '''..

[BOJ] - 제곱근 분할법 (Square Root Decomposition) + mo's 알고리즘

문제 크기가 N인 정수 배열 A가 있고, 여기서 다음과 같은 연산을 최대 M번 수행해야 하는 문제가 있다고 해 봅시다. 1. 구간 l, r (l a[i]: ans = a[i] 소스 1의 시간복잡도는 O(N)입니다. 2번 연산의 시간복잡도 A[i] = v는 O(1)입니다. 최대 쿼리가 M번 수행해야 하니 연산 하나의 시간 복잡도는 O(N)이 됩니다. 총 시간복잡도는 O(NM)입니다. 제곱근 분할법 제곱근 분할법을 사용하려면 크기가 N개인 배열을 크기가 sqrt(N)인 그룹으로 나누고, 각 그룹의 최솟값을 별도로 저장해야 합니다. 그룹의 크기가 sqrt(N)이니, 그룹의 개수도 sqrt(N)개입니다. N이 제곱수가 아닌 경우에는 그룹의 크기로 sqrt(N) a[i]: d[i//r] = a[i] 여기서 2번 ..