seojin0305 PS 블로그

segment tree가 뭔가요? segment tree(이하 segtree)는 주어진 배열에서 특정 원소 수정 구간 단위 연산의 결과(ex: 구간 합, 구간 최댓값) 를 $O(logN)$에 수행하게 해주는 알고리즘입니다. 기본 원리 작동하는 기본 원리는 이분 탐색과 비슷한 듯 다릅니다. 위의 그림에서와 같이, 현재 구간에 대해 반으로 나누며 필요한 경우 새로운 구간에 대해 재귀적으로 반복하는 것입니다. 각 범위별로 구간 단위 연산의 결과를 저장해놓는다 하면, 배열의 크기가 $N$일 때 $4N$ 이하의 크기의 배열에 저장할 수 있습니다. 저장 원리는 현재 범위를 저장할 번호가 $k$라 할 때, 앞쪽 절반 배열은 $2k$, 뒤쪽 절반 배열은 $2k+1$에 저장하는 것입니다. 예시로 배열의 크기가 8이라 하..

알고리즘 greedy, dp 시간복잡도 $O(N)$ 풀이 $ad, b->c)$보다 항상 비용이 작음이 증명된다. 따라서 절대 소가 밀릴 일이 없는 지점에서 시계 방향으로 돌 때 가장 가까운 0으로부터 순차적으로 밀어주면 된다. dp를 통해 가장 많이 밀린 지점을 구할 수 있으며, $O(N)$으로 끝에 있는 0부터 채워주면 된다. 코드 #include using namespace std; #define ll long long int N, a[100005], dp[100005]; ll ans; ll add(ll b, ll n) { ll r = 0; for (ll i = 0; i >N; for (int i =..

알고리즘 dp, two_pointer 시간복잡도 $O(NlogN)$ 풀이 현재 점 왼쪽의 모든 점을 연쇄적으로 터뜨릴 수 있는 최솟값을 $dpl[i]$, 마찬가지로 오른쪽의 경우 $dpr[j]$로 구한다. 임의의 두 점에 대하여 두 점 사이 거리의 절반, 앞에서 구한 $dpl, dpr$ 값들 중 최댓값이 전체 최솟값 후보일 것이다. 이를 $O(N^2)$로 구하면 시간초과가 나기에 맨 끝에서부터 two pointer로 관리해주면 된다. (dp값이 작은 것을 밀도록) 코드 #include using namespace std; int N, a[50005], dpl[50005], dpr[50005]; int ans = 2e9; int main() { cin>>N; for (int i = 1; i >a[i]; a..

알고리즘 random 시간복잡도 $O(TKN^2)$ 풀이 $i$번 정점과 $j$번 정점 사이의 인접 연결 정보를 저장한 행렬을 $A$, $i$번 정점과 $j$번 정점 사이 거리가 2인 연결 정보를 저장한 행렬을 $B$라 하면 $A^2 = B$인지 아닌지를 확인하면 된다. 그러나 일반적인 행렬 제곱 시 $O(N^3)$이므로 시간 제한에 걸리게 된다. $Freivalds' \space algorithm$이라는 신박한 알고리즘이 존재한다. $x \in \mathbb{R}^n$라 할 때, $A^2 x = Bx$인 경우 약 $\frac{1}{2}$의 확률로 $A^2=B$이다. 이 곱셈의 시간복잡도는 $O(N^2)$이다. random한 $x$에 대해 10번 확인 시 적중 확률은 99.9%이다. 코드 #include..

알고리즘 bitmasking, ed_hoc 시간복잡도 $O(NlogM)$ 풀이 00...01의 전이 상태를 순차적으로 확인해보면, 1세대 때 00...011 2세대 때 00...0101 4세대 때 00...010001 8세대 때 00...0100000001 ... 임을 확인할 수 있다. 즉, 현재의 상태 $a_i$에 대하여 $2^k$세대 이후의 상태는 $a_i ' = a_i + a_{(i + 2^k) \space mod \space N} \space (0 \leq i < N)$이다. 각 전이는 서로에 대해 독립적이므로 $M$을 2의 거듭제곱으로 분해하여 진행하면 된다. 코드 #include using namespace std; int N, M, a[1000005], b[1000005]; int main(..