돌이 코딩하는 방

생각보다 시간이 많이 빠듯했다. 할 것도 많았고, 오랜만에 하다보니까 하나하나 생각하는데 시간도 꽤나 오래 걸렸다. 사실 애초에 이 셋에 일주일동안 쓴 시간이 다 합쳐봤자 얼마 안되었다는게 가장 문제였다. 18솔을 했다. 하지만 여왕벌은 거르더라도 실골 문제들을 풀자고 만들어 놓은 연습셋이 아니기 때문에 아쉬운 부분이 많다. 그래도 일단 쭉 정리를 해보려 한다 A - 사냥꾼 KOI 2013 고등부 1번 그냥 딱히 생각하는 것도 오래 안걸리고 구현도 딱히 안빡셌다. 무난한 문제 풀이 https://stonejjun.tistory.com/98 B - 막대기 KOI 2013 고등부 2번 문제를 잘 못봤다. 관찰 위주의 문제였고, 솔직히 오래 걸릴 문제도 아니었지만, 문제 조건을 잘못 봐서 오래 고생한것이 컸다..

이번에 포스팅할 Segment Tree의 활용법은 구간 내에서 최대 부분합을 찾는 방법이다. 흔히 "금광 세그"라고 불리는 방식이며, 금광이라는 문제에 이 기법이 사용되어졌다. 어떠한 문제에서 두가지 쿼리가 주어졌다고 하자. 1번 쿼리로 수열에서 a번째 숫자를 b로 바꾸는 쿼리가 들어온다. 2번 쿼리로 l,r이 주어졌을때 수열의 [l,r]내에서 연속된 부분합의 최댓값을 구하는 것이다. 이러한 문제를 Segment Tree를 활용해서 해결할 것이다. 어떤 노드에 그냥 최대 부분합만 담고 있다고 생각해보자. 아래 두 개의 노드를 합칠때 그냥 둘 중 최댓값을 고르게 되면 왼쪽 절반 안에 속해있는 부분합과 오른쪽 절반안에 속해있는 부분합 밖에 알 수 없다. 두 구간을 걸친 부분들의 합은 고려해 줄 수 없는 것이..

문제 링크 : https://www.acmicpc.net/problem/2415 문제 소개 좌표평면에 점들이 주어지면 주어진 점들로 만들 수 있는 가장 큰 직사각형의 크기를 출력하는 문제이다. 문제 풀이 굉장히 아이디어성 문제이고, 다양한 풀이가 나올 수 있는 문제이다. 일단 이 문제를 풀기 위해서 직사각형의 성질들을 생각해보자. - 두 쌍의 대변의 길이가 각각 같다. - 두 쌍의 대각의 크기가 각각 같다. - 두 대각선이 서로 다른 대각선을 이등분 한다. - 두 대각선의 길이가 같다. 한 직사각형에서 변이나 길이는 두 쌍이지만, 대각선은 두 개이다. 따라서 대각선에 집중을 해보자. 두 대각선의 길이가 같고, 서로 이등분하면 직사각형이다. 즉, $N^2$개의 선을 만들 수 있고, 그 중 길이가 같고 서로..

문제 링크 : https://www.acmicpc.net/problem/13209 문제 태그 더보기 Parametric Search 문제 소개 트리가 있다. 이중 k개의 간선을 끊어서 k+1개의 트리로 만든다. 이때 각 트리에 포함된 노드의 가중치의 합들 중 최댓값의 최솟값을 구하시오. 문제 풀이 트리의 간선을 '최대한 잘' 끊어야 한다. 트리별로 노드의 가중치의 합이 최대한 비슷하도록, 어느한쪽이 치우치지 않도록 끊어야 한다. 어떻게 해야 최대한 잘 끊을 수 있을까? 이를 생각하는 문제는 굉장히 어렵다. 너무 다양한 경우의 수가 나오게 된다. 따라서 좀 다른 방식을 생각해보자. 트리에서 어떻게 잘 잘라서 "가능한 최솟값"을 물어보는 문제이다. x가 된다면 당연히 x이상은 모두 다 가능하고, x가 불가능..

문제 링크 : https://www.acmicpc.net/problem/13548 문제 태그 더보기 Mo's algorithm 문제 소개 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j: Ai, Ai+1, ..., Aj에 가장 많이 등장하는 수가 몇 번 등장했는지 출력한다. 문제 풀이 일단 문제를 읽어보자. 구간 내에서 가장 많이 나타나는 수 -> 각각의 수들이 몇번씩 나왔는지 관리하려고 하면 된다. 또한 이 질문이 쿼리로 주어진다. 이러한 형식의 문제를 많이 풀어봤으면 바로 Mo's algorithm을 써야 한다는 생각을 할 수 있다. Mo's algorithm 으로 구간을 더하거나 빼주면서 각 숫자별로 몇 개씩 있는지 관리한다고 생..

문제 링크 : https://www.acmicpc.net/problem/13547 문제 태그 더보기 Mo's algorithm 문제 소개 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j: Ai, Ai+1, ..., Aj에 존재하는 서로 다른 수의 개수를 출력한다. 문제 풀이 수의 갯수를 출력하기 위해서는 수들의 집합을 관리 해야한다. 쿼리로써 구간을 많이 주는데 그 쿼리마다 수들의 집합을 관리해야한다 -> 바로 Mo's algorithm을 떠올릴 수 있다. 풀이도 꽤나 간단하게 보인다. Mo's algorithm을 이용하여 구간을 정렬하고 구간내에서의 각 숫자의 갯수를 세주면 된다. 구간을 추가할 때는 추가되는 구간의 숫자의 갯수에 1..

BOJ 2512 고등부 1번 예산 문제 링크 : https://www.acmicpc.net/problem/2512 문제 태그 파라매트릭 서치, 이분 탐색 문제 풀이 설정 할 수 있는 (가능한) 가장 큰 값을 묻는 문제이다. 이 부분을 보자마자 바로 파라메트릭 서치를 한 번 떠올려야 한다. 내가 어떤 값을 제사하여 그 값이 가능한가? 로 묻는 문제로 바꾸면 훨씬 더 쉽게 해결할 수 있을지에 대해 생각하면 파라메트릭을 쓸지에 대한 여부가 결정되고, 따라서 이 문제는 쓰는 것이 좋다. 더이상 말이 크게 필요없다. 지난번 글에서도 썻듯이 파라메트릭 서치 기본 문제이다. 코드 더보기 #include #include typedef long long ll; using namespace std; ll n, a[1000..

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

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