-
알고리즘 문제 풀이6
알고리즘 문제 풀이 6 최근에 푼 재미있는 문제들을 포스팅 해보겠습니다. BOJ 1530 금민수의 합 이 문제는 4와 7로만 이루어진 수를 금민수로 정의하고, $N$($\leq1,000,000,000$)이 주어지면 $N$을 금민수의 합으로 나타내는 방법을 찾는 문제입니다. 만일, 방법이 여러가지라면 수의 개수가 적은 방법을, 이러한 방법 또한 여러가지라면 사전순으로 최소인 방법을 찾아야 합니다. 우선 여러가지 관찰을 해봅시다. 첫번째로 주어진 수 $N$을 금민수들의 합으로 표현하는 것이 불가능한 경우가 있을까요? 네, 물론 있습니다. 작은 수에서 예를 들어보면 1, 2, 3, 5, 6, 9,...
-
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 $의 원소이다) 이때...