블로그 이사 중입니다 >> gumgood.github.io

가로변, 세로변을 분리시켜서 생각하면 편하다. 세로 변의 길이의 합를 구하는 함수가 있으면 직사각형들을 y=x 축에 대칭시켜 같은 함수로 가로 변의 길이의 합도 구할 수 있다. 세로 변의 길이의 합를 구하는 함수를 생각해 보자. Plane sweeping 방법과 비슷하게 진행하는데 직사각형을 추가하거나 삭제하면서 생기는 변의 길이를 센다. 직사각형을 추가했는데 segtree의 query가 늘어났다면 해당 길이에 해당하는 직사각형이 생겨 새로운 변이 생긴 것이고 직사각형을 삭제했는데 segtree의 query가 줄어들었다면 그 길이에 해당하는 직사각형이 끝나 새로운 변이 또 생길 것이다. 주의해야할 점은 직사각형이 삭제됨과 동시에 추가하는 경우 (즉, 같은 크기의 직사각형이 같은 변을 맞대고 있는 경우) ..

작성일 기준 BOJ에서 채점 가능한 문제만 풀어보았습니다. 1번. BOJ 5819 열대 식물원 공식 풀이는 \(O(QN)\)입니다. 이 안에 절대 안될거라 생각했는데 시간 제한을 너무 보수적으로 생각했나봅니다. 아무튼 제 풀이는 \(O(N+M\log M + Q)\)이긴 하지만 대회 문제는 쉬운 풀이가 좋은 풀이라 생각하기 때문에 관심 있으신 분만 읽으셔도 됩니다. 각 연못을 node로 하고 각 산책로에 대해 아름다운 정도를 가중치로 갖는 edge로 directed graph를 구성합니다. 철수가 한 연못에서 다음 연못으로 이동 중인 상태를 '어떤 node \(u\)에서 edge를 거쳐 다음 node \(v\)로 가는 상태'로 볼 수 있습니다. 즉, 철수의 현재 연못과 상태(어느 연못에서 왔는지)는 하나의..

https://www.acmicpc.net/category/detail/1935 A. BOJ 16282 Black Chain 첫 번째 접근법은 'n개의 고리가 연결된 체인에서 m개의 고리를 풀 때 1g부터 ng까지 모든 무게를 생성할 수 있는지' 여부를 판단하는 함수 f를 만들어 풀어야 할 고리의 최소값을 binary search로 찾는 것이었습니다. f를 만들어낸 방법은 다음과 같습니다. m개의 고리를 풀면 1g 고리가 m개가 생성되므로 일단 이것만으로 1g부터 mg까지 모두 생성이 가능합니다. 남은 (n-m)g의 체인은 m+1개 이하의 체인들로 나눌 수 있습니다. 여기서 나눈 체인들은 앞에서 푼 고리 사이에 들어간다고 생각하시면 됩니다. 1g ~ mg의 무게를 만들 수 있을 때, (m+1)g의 체인이..

COCI(Croatian Open Competition in Informatics) 2009/2010 contest #2 https://www.acmicpc.net/category/detail/84 1. BOJ 2914 저작권 앨범의 수록곡의 개수 A와 수록곡 당 멜로디의 개수의 평균값 I이 주어질 때, 적어도 몇 개의 멜로디가 있는지를 묻는다. 이 문제에서는 평균값을 구할 때 올림을 사용하므로 실제 평균 avg.는 I-1 < avg.

원문 : https://stackoverflow.com/questions/1506078 permutation of n elements가 있을 때, integer로 mapping하는 방법에 대해 설명한다. n!의 permutation이 있을 수 있고, 이를 n!가지의 정수에 1:1 mapping하는 것이 목적이다. n개의 원소로 이루어진 permutation을 설명할 때, 첫 번째 원소가 있을 수 있는 위치는 n가지가 있다. 따라서 이 원소의 위치를 0~n-1 사이의 수로 나타낼 수 있다. 그 다음 원소가 있을 수 있는 위치는 남은 n-1가지이다. 그래서 이 원소의 위치를 0~n-2 사이의 수로 나타낼 수 있다. 이를 위치를 나타내는 n개의 수를 얻을 때까지 계속 반복한다. n=5인 경우를 예로 들어, '..

COCI(Croatian Open Competition in Informatics) 2009/2010 contest #1 https://www.acmicpc.net/category/detail/83 1. BOJ 2920 음계 음계가 "1 2 3 4 5 6 7 8"이면 ascending, "8 7 6 5 4 3 2 1"이면 descending을 출력하고, 나머지는 mixed를 출력한다. stl vector의 비교연산자로 간결하게 구현한다. #include using namespace std; vector as = {1,2,3,4,5,6,7,8}; vector ds = {8,7,6,5,4,3,2,1}; vector in(8); int main(){ for(int i=0;i

Today I want to introduce you some very very useful data structures. Trees Trees are one of the most useful data structures. A tree is a connected-acyclic graph. Ther are too many types of trees, like : rooted trees, weighted trees, directed trees, tries, etc. Partial sum There are two types of problems solvable by partial sum. 1. Problems which you are asked to answer some queries about the sum..

원문 : https://codeforces.com/blog/entry/18051 Segment tree with single elment modifications Segment tree는 한 배열에서 몇 번의 변경이나 연속된 부분에 대한 query들을 처리할 때 사용한다. 첫번째 예로 다음 두 명령어를 생각해두자. 1. 배열에 있는 한 원소를 수정한다. 2. 어떤 범위에 대한 원소들의 합을 찾는다. Perfect binary tree 다음은 segment tree를 도식화한 것이다. 표기법은 node_index: corresponding segment [left border included, right excluded)이다, 트리의 leaf에 해당하는 맨 밑에 행은 우리의 배열에 해당한다. Perfect..