CP Algorithm & Knowledge (30) 썸네일형 리스트형 단조 큐 (Monotone Queue) 개요 큐에 들어있는 어떠한 값들의 집합이 단조성을 보이면(monotonic) 그 큐는 단조 큐가 된다. 예를 들어 큐 안에 있는 수들을 수열로 봤을 때 단조증가한다면 단조 큐다. 용어는 단조 큐이지만 이를 활용하기 위해서 덱(deque)이 쓰인다. 단조 큐를 활용한 문제 풀기 백준 저지에서 11003번 문제를 보자. 수열을 순회하면서 특정 구간에 대해 최솟값을 찾을 것을 요구하고 있다. 어떤 구간에서 최솟값보다 큰 수들은 무시된다는 점에 주목해보자. 수열을 순회하면서 상대적으로 큰 수들을 적절히 배제하고 구간에 알맞은 최솟값을 남길 수 있다면 좋을 것이다. 여기서 단조 큐를 이용하면 $O(N)$으로 빠르게 답을 구할 수 있게 된다. 11003번 문제를 푸는 과정을 통해 단조 큐 사용법을 알아보자. 1. .. 지그재그 순열(Alternating Permutaion) 의 개수 구하기 소개 Zigzag Permutaion, Alternating Permutaion이라고 불리는 순열은 다음과 같은 대소 관계를 지니도록 수를 나열한 것이다. a부터 g까지의 수가 나열되어 있을 때 $a c e g$ $a > b d f < g$ 이 순열은 감소 - 증가 - 감소 - 증가... 하거나 증가 - 감소 - 증가 - 감소... 하는 패턴이 반복된다. 올라갔다 내려갔다 하는 모습이 마치 지그재그 모양을 연상시켜서 지그재그 순열이라고 부르는 것 같다. 자연수 n까지 지그재그 순열을 만드는 경우의 수 구하기 1부터 n까지 자연수를 나열한 수열이 지그재그 순열이 되는 경우의 수를 구하는 방법은 여러가지가 있지만 프로그래밍 대회 수준에서 신뢰할 수 있고 .. MST 최소 신장 트리 Sollin, Boruvka (솔린, 보르부카) 알고리즘 구현 이 게시글에서는 솔린, 해외에서는 보르부카라는 이름으로 더 알려져 있는 MST 생성 알고리즘을 구현해보겠다. 솔린 알고리즘의 간단한 설명 주어진 그래프에서 각 노드들을 트리라 생각한다. 그러면 그래프는 포레스트가 된다. 각 트리에서 다른 트리로 연결된 최소 비용 엣지를 택하여 그 엣지로 연결된 두 트리를 union하는 것을 포레스트가 하나의 트리가 될 때까지 반복하면 MST가 완성된다. 단계마다 모든 엣지들을 탐색하면서 포레스트에 들어있는 트리의 개수가 절반씩 줄어들다가(한 트리는 다른 트리와 무조건 짝지어지게 됨을 생각하면 이해할 수 있다.) 1개, 즉 MST가 되면 종료하므로 시간 복잡도는 $O(ElogV)$이다. 구현 - 백준 1197번 풀기 union하는 것에서 눈치챌 수 있듯이 솔린 알고리즘도 .. 페르마의 소정리를 활용한 알고리즘 문제 풀기 이 게시글에서는 페르마의 소정리를 간략하게 배우고 관련 알고리즘 문제를 푼다. 정수 a와 p가 있고 a가 p의 배수가 아니면서 p가 소수(Prime number)일 때 다음이 성립한다. $a^{p} \equiv a (\mod p)$ 여기서 $\equiv$ 는 합동을 의미하는 기호인데 $a^{p}$를 $p$로 나눈 나머지는 $a$를 $p$로 나눈 나머지와 같다는 뜻이다. 또한 여기서 양변에 a를 나누는 것으로 다음 두 식을 유도할 수 있다. $a^{p - 1} \equiv 1 \; (\mod \; p)$ $a^{p - 2} \equiv a^{-1} \; (\mod \; p)$ 페르마의 소정리에 대해 알았으니 이를 이용하는 문제를 하나 풀어보자. icpc.me/16134 16134번: 조합 (Combinat.. 기본적인 소수 판별 알고리즘 2가지 소수가 자기 자신과 1만을 약수로 가진다는 것은 널리 알려진 사실이다. 알고리즘 문제를 풀 때 어떤 수가 소수인지 아닌지 판별할 상황이 오는데 그 수가 너무 크지만 않다면 게시글에서 알려줄 두가지 방법을 이용하여 적절히 해결할 수 있다. 판별법 1. 완전 탐색을 통한 검사 자연수 N이 소수인지 아닌지 판별하는 가장 간단한 방법은 2부터 $\sqrt[]{N}$ 까지 나눠보면서 나눠지는지 아닌지 확인하는 것이다. 왜 모든 수를 나눠보는게 아니라 제곱근으로도 충분할까? N이 합성수라고 한다면 N은 $N = ab = ba$처럼 두 자연수 a, b의 곱으로 나타낼 수 있다. 이 때 a와 b는 $2 \leq a \leq \sqrt[]{N}, \; \sqrt[]{N} \leq b \leq \frac{N}{2}$ 또는.. 이전 1 ··· 3 4 5 6 다음
