-
problem solving 1
문제풀이를 하면서 재미있었던 문제를 소개하고자 간단하게 문제 설명과 풀이를 작성해보았습니다. Min Max Convert (SEERC 2018) $N (N \leq 100,000)$개의 숫자를 가진 배열 $A, B$가 주어질 때, 2가지 쿼리를 이용하여 $A$ 배열을 $B$ 배열로 만들 수 있으면 해당 쿼리를 출력하고 불가능하면 -1을 출력하는 문제입니다. 그리고 가능한 경우에는 쿼리를 $2*N$ 번 이하로 사용해서 만들어야 합니다. 첫번째 쿼리는 $[a, b]$ 구간의 숫자들을 모두 해당 구간의 최대값으로 변경하는 쿼리고, 두번째 쿼리는 $[a, b]$ 구간의 숫자들을 모두 해당 구간의 최소값으로...
-
알고리즘을 이용한 Problem Solving
Lagrange the Chef (Nanjing 2018) 당신은 요리사입니다! 당신이 만들 수 있는 요리는 $10^6$개가 있으며, 손님에게 만들 수 있는 요리 중 $N$개를 코스요리처럼 순서대로 주려 합니다. (고를 수 있는 요리는 중복 가능합니다.) 당신의 식당에 한 손님이 찾아 왔습니다. 이 손님은 매우 특이하여 $X, Y$요리가 연속적으로 나오는 것을 싫어합니다. 즉 $X$다음에 바로 $Y$요리가 나오거나, $Y$다음에 바로 $X$음식이 나오면 불평을 하며 식당을 떠나갑니다. 당신은 식당에 불만이 들어오는 것을 싫어합니다. 따라서, 요리를 하는 순서를 적당히 바꾸어 주려 합니다. 하지만...
-
Persistent Segment Tree
안녕하세요, 이번 글에서는 Persistent Segment Tree 에 대해 알아보도록 하겠습니다. Segment Tree Persistent Segment Tree를 이해하기 위해서는 Segment Tree에 대한 이해가 선행되어야 합니다. 이미 대다수의 독자분들이 Segment Tree에 대해 알고 있겠지만 다시 한 번 짚고 넘어가겠습니다. Segment Tree는 배열을 여러 구간으로 나누어 관리하는 구조로, $N$개의 원소가 있을 때 구현에 따라 2배에서 4배 정도의 추가 공간이 필요하지만 원소의 변경, 특정 범위 내의 원소의 연산을 $lgN$에 수행할 수 있습니다. 구체적으로 배열 1 2 3 4 3 2...
-
Counting the number of topologies on a finite set
Topology 수학에서, topological space란 다음 조건을 만족하는 집합 $X$와 $X$의 subset들의 collection $\tau$에 대해 ordered pair $ (X, \tau) $ 를 말한다. $ \phi, X \in \tau $ Any arbitrary union of members of $ \tau$ still belongs to $ \tau$. ($ \tau$의 원소들의 합집합은 $ \tau $의 원소이다) The intersection of any finite number of members of $ \tau$ still belongs to $ \tau$. ($ \tau$의 원소 유한개의 교집합은 $ \tau $의 원소이다) 이때...
-
PS Training 2
안녕하세요, 이번 달에도 Problem Solving 관련 글을 쓰게 되었습니다. 최근에는 참가한 대회가 없지만, 연습 과정에서 만난 문제들 중 괜찮은 문제들을 추려 모아 보았습니다. 이번에도 문제의 풀이와 소스 코드, 링크 등을 정리합니다. Circling Round Treasures Codeforces Round #221 (Div. 1)의 C번 문제입니다. $N * M$ 격자 그리드 안에 다음과 같은 것들이 놓여 있습니다. 폭탄 빈 칸 보물 장애물 주인공은 주어진 어떤 시작점에서 출발해, 상하좌우 중 빈 칸으로 이동할 수 있습니다. 이동하는 데는 1원이 듭니다. 이동을 마치고...