돌이 코딩하는 방

문제 링크 : https://www.acmicpc.net/problem/13546 문제 태그 더보기 Mo's algorithm 문제 소개 1보다 크거나 같고, K보다 작거나 같은 수로 이루어져 있는 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. l r: max{|x − y| : l ≤ x, y ≤ r and $A_x$ = $A_y$} 을 출력한다. 문제 풀이 일단 각 쿼리의 구간내에서 각 숫자별로 그 숫자들이 존재하는 위치들을 전부 알고 있어야 쿼리의 질문에 대한 답을 구할 수 있다. "구간 별로 숫자의 집합을 관리한다." 는 Mo's algorithm을 통해서 해줄 수 있다. deque 를 숫자 범위의 갯수만큼 만들어서 각 deque별로 ..

문제 링크 : 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

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

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