-
장애물을 포함하지 않는 가장 큰 직사각형 찾기
장애물을 포함하지 않는 가장 큰 직사각형 찾기 Motivation 계산기하에서 장애물을 포함하지 않는 가장 큰 도형을 찾는 것은 핵심적인 문제 중 하나이다. 다양한 거리계, 그리고 도형의 모양에 따라서 서로 다른 알고리즘들이 존재한다. 예를 들어서, 다음과 같은 문제들을 생각할 수 있다. A) $n$ 개의 점들이 있을 때, 이 점을 포함하지 않으며 넓이가 가장 큰 원은 무엇인가? B) $n$ 개의 점들이 있을 때, 이 점을 포함하지 않으며 넓이가 가장 큰 직사각형은 무엇인가? C) $n$ 개의 점들이 있을 때,...
-
Prüfer sequence
소개 안녕하세요. 이번 글에서는 labeled tree를 unique한 수열로 나타내는 Prüfer sequence에 대해 소개해드리려고 합니다. 사실 문제 풀이에 많이 활용되는 개념은 아니지만, 이해하기 쉬우면서도 이를 적용해 풀 수 있는 몇 가지 재밌는(?) 문제가 있어 정리해 보았습니다. Prüfer Sequence Prüfer sequence는 $n$개의 정점을 가진 labeled tree를 다음의 알고리즘에 따라 길이 $n-2$의 수열로 나타낸 것입니다. 트리를 수열로 encode한다는 의미에서 encoding 알고리즘이라고 합니다. function Tree_to_Prüfer(T=(V,E)) a <- an empty array while |V| > 2: u <- leaf node with...
-
알아두면 편리한 비트 연산 몇 가지
Bitwise Operation Problem Solving을 하다 보면, 혹은 최적화 등의 작업을 하다 보면 bit 단위의 연산을 하게 될 때가 있습니다. 일반적으로 논리/정수 자료형에서 많이 사용되기 때문에 본 포스팅의 설명은 해당 두 자료형에 한하며 이를 묶어 ‘정수’라고 표현하겠습니다. 간단한 비트 연산은 언어에서 제공하는 연산자를 통해 두 개의 정수를 and, or, xor 하거나 하나의 정수를 shift, not 등으로 변형할 수 있습니다. 이 포스팅에서는 앞에서 나온 기본 단위 연산자에 관한 내용은 따로 다루지 않고, 좀 더 나아가 하라면 하겠는데...
-
Problem Solving과 생성함수
간혹 조합론 문제를 해결하다가 점화식이 안 나와서 좌절하고 있을 때, 이 문제는 생성함수를 이용하면 기계적으로 만들어낼 수 있다는 충격적인 코멘트를 받아 언젠가 공부해야지 마음먹고 있습니다. 아쉽게도 정규 교육과정에 포함되어있지 않아서인지 problem solving와 관련된 자료가 드물었습니다. 때문에 이 포스트를 작성하시로 하였습니다. 이 포스트는 생성함수는 무엇이고, problem solving에 적용할 수 있는 방법을 다룹니다. 생성함수란? 일반적으로, 어떤 수열 ${a_i} = (a_0, a_1, a_2, \cdots)$에 대하여, \[f(x) = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n + \cdots...
-
Segment Tree Beats
안녕하세요. rdd6584로 활동하고 있는 권일우입니다. 이 글에서는 요즘 유행하는 segment tree beats(이하 세그비츠)에 대해서 소개하겠습니다. 이를 위해서는, segment tree with lazy propagation에 대한 지식이 선행되어야 하지만 여기서는 소개하지 않겠습니다. Segment Tree Beats segment tree beats의 beats는 일본 애니메이션 “angel beats”에서 따온 것으로 특별한 의미를 가지고 있지 않습니다. 그러면 세그비츠가 뭘까요? 세그비츠는 lazy propagation의 활용형으로 중단조건과 갱신조건을 적절히 조절하여 까다로운 구간 쿼리를 해결하는 방법 중 하나입니다. 아래와 같은 문제가 있습니다. 길이 $N$의 배열 $A$, 아래와 같은...