돌이 코딩하는 방

문제 링크 : https://www.acmicpc.net/problem/13554 문제 태그 (관련 지식) 더보기 Mo's algorithm, Segment tree 문제 소개 길이가 N인 두 수열 A1, A2, ..., AN과 B1, B2, ..., BN가 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j k: i ≤ p, q ≤ j이면서 Ap × Bq ≤ k 인 (p, q) 쌍의 개수를 출력한다. 문제 풀이 일단 오프라인 쿼리고 시간제한이 6초이다. 사실 어떻게 접근을 해야할지 모르겠다. 이 문제를 볼 때 쯤이면 다른 수열과 쿼리 문제를 꽤나 풀어봤을 것이고, 그러면 수쿼를 풀 수 있는 도구중 Mo's Algorithm이 생각이 날 수 밖에 없다. 하지만 문제가 있다. Mo's a..

sqrt, 루트계의 스페셜리스트 알고리즘인 Mo's algorithm을 소개하려고 한다. 어떤 문제를 해결할 때 기본적으로 루트풀이는 친숙하지 않아서 떠올리기 힘들다. 하지만 그 와중에 Mo's algorithm은 굉장히 신박한 아이디어로 만든 시간복잡도이기 때문에 이 알고리즘은 정말 '알고 있어야' 사용이 가능하고 문제를 풀 수 있을 것이다. Mo's algorithm 이란? Mo's algorithm은 업데이트가 없이 오프라인으로 구간 쿼리가 많이 주어질 때, 그 구간쿼리들을 효율적으로 처리하는 알고리즘이다. 기본적으로 오프라인 쿼리여야 되고, 처리하는 쿼리들의 순서를 잘 조정함으로서 더 효율적으로 처리를 할 수 있게 됩니다. Mo's algorithm의 작동 방식 1. 어떤 쿼리 (구간) 에 대한 ..

문제 링크 https://www.acmicpc.net/problem/14435 문제 소개 놀이기구가 주어지고, 각 놀이기구에 같이 탈 두명이 각각 주어진다. 그 둘이 놀이기구를 타기 위해서는 둘의 키의 합이 제한을 넘어야 한다. 각 날마다 한 명의 키가 1씩 크며 전날에 제한을 만족한 놀이기구가 그 전날 제한을 만족한 놀이기구 수 보다 많다면 키가 1이 더 큰다. 이때 각 날 별로 몇 개의 놀이기구에 대하여 아이들이 제한을 만족하는지 출력하여야 한다. 문제 풀이 굉장히 재밌는 아이디어의 문제였고, 이 문제를 혼자 생각하지 못하였다. 거의 모든 부분을 이해한 업솔빙 느낌의 문제였다. 그래서 만약 처음부터 생각했다면 어떤 느낌으로 접근해야 맞을지를 생각하여 작성하였다. 일단 $O(QK)$의 풀이를 생각해보자..

문제 링크 https://www.acmicpc.net/problem/2243 문제 소개 두가지 행동을 하는 문제이다. 1. x 맛의 사탕의 갯수를 k개 변화시킨다. 2. k번째로 맛있는 사탕의 맛 수치를 출력한다. (1이 가장 맛있고 1000000이 최악) 문제 풀이 1번 쿼리는 굉장히 자주 나오는 쿼리이고 하나도 까다롭지 않게 작용한다. 중요한 것은 2번쿼리로 그니까 1부터 순서대로 늘어놓았을 때 k번째 숫자를 구하고 싶은 것이다. 구간 합 구하기의 가장 간단한 세그를 생각해보면 우리가 얻은 수 있는 값은 구간 의 합이다. 이 문제는 세그에는 추가적인 옵션을 가하지 않고, 이 값을 이용하여 문제를 해결할 수 있다. 이분 탐색이다. 1~i 구간의 합을 구할 수 있다. 그 값이 k이하인지 초과인지에 따라서..

문제 링크 : https://www.acmicpc.net/problem/17411 문제 소개 수열이 주어졌을 때 가장 긴 증가하는 부분 수열의 길이 와 그 갯수를 출력하시오. 문제 풀이 가장 긴 증가하는 부분 수열 즉 LIS를 $O(NlgN)$에 구하는 방법은 여러가지가 있다. 간단한 코딩으로는 lower_bound를 사용할 수 있으며, 이분탐색도 가능하며, 세그먼트 트리도 가능하다. 이 글에서는 세그먼트 트리를 활용한 방법을 설명하고 이를 이용하여 이 문제를 해결하는 방법을 설명하려고 한다. $O(NlgN)$ LIS by segment tree DP로 LIS 를 찾을 때 i번째 수를 마지막으로 하는 LIS값이 Li고, 수열의 값이 Ai라면 우리는 어떤 i에 대해서 1~i-1중 Ai보다 작은 값중 가장 ..

관련 알고리즘과 함께 푼 수열과 쿼리 문제들을 쭉 포스팅 하려고 한다. 문제 링크 : https://www.acmicpc.net/problem/17408 문제 소개 1 i v: Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ $10^9$) 2 l r: l ≤ i b.ff) { return tree[nod]=a; } else return tree[nod]=b; } pll sol(ll l ,ll r, ll s,ll e,ll nod) { if(er) return {0,0}; if(l

문제 링크 : https://www.acmicpc.net/problem/2463 문제 소개 그래프가 주어진다. 이 문제에서 Cost(u,v)는 가장 적은 비용의 간선부터 차례대로 끊어나갈 때, 점 u와 점 v가 처음으로 다른 컴포넌트가 될 때 까지 끊은 간선의 가중치의 총합이다. 이때 주어진 그래프에서 임의의 i

백준 게시판에도 올렸지만 혹시 못보신분들을 위해서 두 버전으로 다시 올려봅니다!!

그냥 주저리 주저리 쓴 글입니다... 가독성이 안 좋을 수 있지만 나름 재밌을 수도 있습니다. 전체 후기 한 달 동안 다른거 줄여가면서 정말 열심히 달려왔다. 지금 이 그림을 머릿속에 그려놓긴 했지만, 이 그림이 현실로 다가올지는 상상도 하지 못했다. 오늘이 생일이라서 더 뜻깊은 것도 있는것 같다. 시작은 그저 아이디어는 조금 있는데 백준 스택 권한이 없어서...도 있었고, 게임문제를 미친듯이 풀어대는 나의 모습을 보고 주위에서 장난식으로 한 번 만들어보라고 했던 이유도 있었다. 무엇보다 사람들의 어그로도 끌고 싶었고, 뜻 깊은 경험이 될 것 같았다. 사실 의지만 가지고 하기에는 좀 많이 벅찬 여정이었다. 최근 대회퀄이 너무 좋았기 때문에, 계속해서 뇌절 아이디어만던져대고 시간은 다가오고, 급박했었다. ..

이 문제는 굉장히 어렵고 이 글에는 강력한 스포(풀이의 전체)가 있다. 2주가 넘는 시간동안 이 문제에 정말 많은 시간을 쏟아서 만들었다. 문제에 대해서 많은 고민을 해본 후에 이 풀이를 봐주셨으면 좋겠다. 더보기 일단 가장 먼저 발견해야하는 것은 게임판에 "유리도"라는 개념을 부착하는 것이다. 이 게임판이 A,B 둘 중 누구에게, 얼만큼의 유리함을 가져다 주는 지에 대한 값으로 정식 명칭은 아니지만 "유리도" 라고 부르려고 한다. 솔직히 아무것도 모르는 상태에서 "유리도"를 생각하는 것은 정말 말도 안되는 일이고, 따라서 판 뒤집음, 구간 게임판 사용등으로 한 게임판을 수치화 시켜야 된다는 일말의 힌트를 남겨놓긴 하였다. 이 게임의 가장 큰 특징은 내가 턴을 넘기면 무조건 이득이다. 절대로 턴을 넘겨서..