chw0501

먼저 모든 lazy propagation 문제를 펜윅트리로 풀 수 있는 것은 아니다. 하지만 lazy propagation 문제 중 대표적인 유형 몇 개는 놀랍게도 펜윅으로 풀 수 있다. 여기서는 두 문제를 소개하려고 한다. 이 놀라운 방법은 다음 두 곳에서 설명하는 것으로 이해했다. www.acmicpc.net/blog/view/88 tony9402 님의 boj10999 풀이 먼저 대표적인 유형 www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘..

dp를 연습하기 위해 https://atcoder.jp/contests/dp/tasks 셋을 풀었다. 대부분의 문제가 유명하고, 문제 지문도 매우 직관적인 것으로 보아 꽤 정형화 된 문제들이라서 공부하기에 추천한다. 난이도 순은 아니라는데 맨 뒤의 문제가 체감상 더 어려웠다. 이번 글에서는 내가 스스로 못풀고 풀이(http://www.secmem.org/blog/2019/05/15/Education-Dp-Contest-Solution/)를 본 문제를 복습하는 의미로 정리하였다 T - Permutation $dp[i][j]$ : 맨 앞 i개의 숫자를 1~i 숫자로 채워넣을 때 마지막 수가 j가 되도록하는 가짓수 $sum[i][j]$ : 구간 합 배열로 $dp[i][1]$ ~ $dp[i][j]$ 의 합 $i..

https://www.acmicpc.net/problem/10742 해답을 보고 알았지만 재밌는 이분탐색 문제이다. 평균이 가능한 범위는 1부터 1000000까지 이다. 이분탐색으로 답이 p이상이 가능한지 확인하면서 범위를 좁히는 형식으로 해결할 수 있다. 답이 p이상이 가능한지 안한지 확인하는 방법은.. 먼저 각 요소에 p를 뺀 배열을 새롭게 만든다. 이때 만약, 길이가 $k$이상인 부분합이 $0$이상인 구간이 존재한다면 okay이다. 따라서 하나씩 $index$를 증가시키면서 미리 계산한 구간합배열 $psum$ 을 두고 $psum[index] \geq min_{i \leq index-k}(psum[i])$ 인 곳이 있는지 $min(psum[i])$를 update해주면서 확인하면 된다. using na..

boj 15977 이 문제의 해결 방법에 대한 아이디어 및 코드 출처(koosaga님), 설명은 2020/01/24 - [분류 전체보기] - dp와 분할정복으로 LIS 해결 에서 충분히 하였다. 본 문제를 다시 설명하면 $m=2$일 때는 첫 째 행에 대해 정렬시켰을 때 두 번째 행에 대한 lis를 구하는 문제이므로 간단하다. $m=3$일 때가 중요한데... 마찬가지로 같은 아이디어를 적용하면 첫 째 행에 대해 정렬시켰을 때 pair에 대한 lis를 구하는 문제로 바뀐다. 그리고 이 문제에 대한 핵심 아이디어 dp와 divide&conquer 풀이법은 이전글에서 설명하였다. 항이 하나 늘어나기는 했으나 핵심은 같다. 단, 원소의 범위가 $1$~$10^9$ 이므로 좌표 압축을 해야 한다. 따라서 코드로 설명..

LIS(Longest Increasing Subsequence)를 해결하는 방법은 다양하다. 특히 $O(nlogn)$ 으로 푸는 방법들에는 이분탐색과 세그먼트 등이 있다. 이번에는 시간복잡도는 $O(nlog^2n)$ 으로 약간 뒤쳐지지만 분할정복과 dp로 lis의 길이를 구할 수 있는 방법에 대해 써보려고 한다. 이 풀이는 KOI 2018 고등부 3번 조화로운 행렬 을 풀어보려고 하다가 ba*arkingdog님의 블로그를 보고 알게된 koosaga님의 댓글을 보고 알게 되었다. (복잡한 사연..) https://codeforces.com/blog/entry/43319 여기를 보면 이와 같이 풀이에 대한 아이디어가 적혀있는데 여기서 붉은 문단을 이해할 수 없어서 결국 koosaga님의 조화로운 행렬풀이를 ..

boj 10548 solved.ac 기준 platinum 5 문제이다. 하지만 이런 문제 유형을 처음 본 나로서는 정말 어려웠다.. COCI 공식 해답지를 보고 공부한 결과, 문제의 아이디어는 히스토그램의 최대 넓이를 구하는 문제를 스택을 사용한 스위핑 알고리즘으로 푸는 것과 비슷하다. (BOJ 1725) 히스토그램 문제를 분할 정복으로 해결하면 $O(NlogN)$ 이 걸리지만 스위핑 알고리즘으로는 $O(N)$ 으로 충분하다. 마찬가지로 이번 문제도 $O(NM)$ 의 시간복잡도로 해결가능하다. 본 문제를 해결하는 기본 방법은 직사각형의 오른쪽 아래점을 고정 시켰을 때 몇 가지의 직사각형이 나올 수 있는지 구해서 모두 더하는 것이다. $i$행에 대해서 위의 스위핑 알고리즘이 어떻게 적용되는지 알아보자. $..

boj 14459 아무리 생각해도 dp로 푸는 시간 복잡도 $O(N^2)$, 공간복잡도도 $N^2$ 인 풀이밖에 생각이 나지 않았다. 따라서 답지를 봤는데... 자바 언어로 되어 있어서 해석하기 힘들었다. 그리고 처음에 lattice point를 어떻게 잡는다는 것인지도 헷갈렸다. 꽤 오랜 시간을 쓰고 나서 이해했고 직관적인 꽤 간단한 풀이가 있음을 알 수 있었다. 먼저 목초지가 왼쪽과 오른쪽으로 나눠져 있다. 밑의 코드를 참고하면 쉽게 이해할 수 있을테지만 문자 정의부터 내리겠다. $a[i]$ : 왼쪽 목초지의 $i$번째 종류 $s[i]$ : 오른쪽 목초지에서 종류 $i$ 목초지의 위치 (단, $index$는 $0$부터 $n-1$이다.) 그리고 dp와 segment tree를 이용할 것이다. 구간 $[..

$ax+by=c$ 의 해를 찾는 방법 먼저 $c$가 $gcd(a,b)$의 배수가 되어야 한다. 만약 $gcd(a,b)$의 배수가 아니라면 좌변은 $gcd(a,b)$로 나누어 떨어지지만 우변은 안 나눠떨어지기 때문에 모순이다. 따라서 우리는 $$ax+by=gcd(a,b)$$ 의 해를 구할 것이다. 그리고 한가지 짚고 넘어가야 하는 점은 $ax+by$의 꼴은 항상 $gcd(a,b)$의 배수이다. $a=bq+r (단, b>r\geq0)$ 라 하자 주어진 식에 $a$값을 대체 하면 $(bq+r)x+by=gcd(bq+r,b)$ 이 되고 정리하면 $$b(qx+y)+rx = gcd(r,b)$$ 이 된다. 가운데 정렬한 두 식을 비교하자. 만약 아래식 $bx'+ry'=gcd(b,r)$의 해를 $(x',y')$를 구..