돌이 코딩하는 방

이번에 포스팅할 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..

지난번 3월 23일 이후로 어떤 것들을 하였고, 어떤 성과를 거두었는지 정리하는 포스팅이다. 일기형식의 글이고 굳이 보실 필요는 없다고 생각한다. 일단 약 두달정도 되는 기간에서 semi-game cup을 빼고 얘기할 수가 없을 것이다. 약 1달 정도 되는 기간을 전부 투자했고, 정말 좋은 경험을 했고, 많은 것들을 얻었지만 그와 반대로 백준 문제나, 코포 등은 신경을 쓸 수가 없었다. 그래도 성공적으로 잘 마무리 되어서 정말 좋았다. BOJ 기록 평균적으로 하루에 한문제 정도 풀었다. 사실 엄청 많은 양은 아니지만, 푼 문제의 난이도나 1달동안 semi-game cup에만 시간을 쏟은것을 생각하면 그렇게... 적다. 사실 그냥 문제량을 좀 더 늘릴 필요는 있다고 생각한다. 요즘은 koi를 돌고 있다. ..

'Tree에서는 Centriod를 잡고 생각하면 편하고 그래프에서는 SCC를 잡고 생각하면 편하다.' 라는 말이 있다. 사실 수준급의 그래프 문제를 많이 풀어본 것이 아니라서 별로 공감은 안되지만, SCC가 정말 좋은 테크닉이라는 것은 인정하고, 저러한 말이 나올 정도로 굉장히 유용하게 쓰일 수 있다. 이번 포스팅은 그러한 SCC에 대해서 설명하려고 한다. SCC scc란 무엇일까? scc는 strongly connected component로 약자를 풀어내면 해석이 되는 다른 줄임말과 다르게 바로 알 수가 없다. 보통 방향그래프에서의 scc를 말하며, scc는 아래의 두가지 조건을 만족하는 서브 그래프이다. 1. 한 scc안에 속한 임의의 어떤 한 노드 A와 다른 한 임의의 노드 B에 대해서 A에서 B..

세그먼트 트리를 이용하여 구할 수 있는 다양한 값들을 소개하려고 한다. 그 중 이번 포스팅은 사람들에게는 Inversion counting이나 LIS등으로 더 친숙한 2-elements 문제나, 특정 문제에서 사용되어진 3-elements 문제에 대해서 말해보려고 한다. 2-elements는 하나의 객체가 2가지 요소 (두개의 값, 하나의 값과 입력순서 등) 를 가지고 있으며 그 두가지 요소가 모두 작은 객체의 갯수 (LIS) , 둘 다 작은 객체의 존재 여부, 둘의 우선 순서가 뒤바뀐 쌍의 수(inversion counting)등을 구하는 문제이다. 3-elements는 하나의 객체가 3가지 요소를 가지고 있으며 세가지 요소가 모두 작은 객체의 존재여부 등을 다루는 문제이다 (굉장한 학생) 2-Elem..

Segment Tree의 활용성은 무궁무진하다. 정말 중요한 자료구조(알고리즘)이며, 대회에도 다양한 형태로 정말 많이 출제가 되어진다. 우리는 거의 모두 Segment Tree를 처음 배우는 과정에서 배열의 값이 바뀌어도 구간합을 빠르게 구할 수 있는 자료구조로서 Segment Tree를 배우지만, 이를 어떻게 추가적으로 활용하느냐, 노드에 어떤 다양한 값을 담느냐에 따라서 정말 다양한 연산을 처리할 수 있다. Segment Tree는 어떨 때 사용할까? 우리가 풀이에 세그먼트 트리를 고려해 볼 수 있는 상황은 간단하게 생각하면 두가지 정도 있다. 첫번째로 쿼리 형식으로 문제가 주어졌을 때이고, 두번째로 시간복잡도를 log로 만들고 싶을 때이다. log가 나오게 된다면 어떤 문제이던지 간에 한번쯤은 생..