유클리드 호제법 두 개의 자연수가 주어졌을 때, 두 수의 최대공약수를 구하는 알고리즘의 하나이다. 두 자연수 a, b (a > b) 에 대해서 a를 b로 나눈 나머지를 r이라 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수가 된다. gcd(a, b) = gcd(b, r) gcd(a, b, c) = gcd(gcd(a, b), c) a = 36, b = 28 36 % 28 = 8 gcd(36, 28) = gcd(28, 8) 28 % 8 = 4 gcd(28, 8) = gcd(8, 4) 8 % 4 = 0 gcd(8, 4) = gcd(4, 0) 따라서, 36과 28의 최대공약수는 4가 된다. ..
문제 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 설명 자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구해야 한다. 먼저 입력된 수보다 작거나 같은 소수를 구한다. 에라토스테네스의 체를 이용하면 쉽게 구할 수 있다. 소수인 수의 배수만 지우면 나머지는 소수가 된다는 방식이다. 나중에 연속된 소수의 합을 구하기 쉽게 소수인 수만 primeList에 저장해놓는다. boolean[] prime = new boolean[N + 1]; List primeList = new ArrayList(); // 소수는 false로 표시, 0..
에라토스테네스의 체 소수가 되는 수의 배수를 지우면 남은 건 소수가 된다. 아래는 위키백과에 나온 에라토스테네스의 체를 이용해 소수를 구하는 방법이다. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색) 자기 자신을 제외한 2의 배수를 모두 지운다. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색) 자기 자신을 제외한 3의 배수를 모두 지운다. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색) 자기 자신을 제외한 5의 배수를 모두 지운다. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색) 자기 자신을 제외한 7의 배수를 모두 지운다. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다. 위의 그..
문제 https://www.acmicpc.net/problem/9202 9202번: Boggle 각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개 www.acmicpc.net 설명 Boggle에서 단어는 인접한 글자(가로, 세로, 대각선)를 이용해서 만들 수 있다. 하지만, 한 주사위는 단어에 한 번만 사용할 수 있다. 단어는 게임 사전에 등재되어 있는 단어만 올바른 단어이다. 단어 사전을 만들어 단어를 빠르게 검색할 수 있는 방법으로는 트라이가 있다. 트라이를 구현하기 위해 TrieNode 클래스를 만들고 필요한 메서드들을 만든다. class ..
문제 https://www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이 www.acmicpc.net 설명 각각의 사탕은 그 맛의 좋고 나쁨이 1부터 1,000,000까지의 정수로 구분된다. 1이 가장 맛있는 사탕을 의미하며, 1,000,000은 가장 맛없는 사탕을 의미한다. A가 1인 경우에는 순위가 B인 사탕을 꺼내는 것이고 2인 경우는 맛이 B인 사탕을 C만큼 넣거나 빼는 것이다. 이를 구현하기 위해 인덱스 트리를 사용한다. if (A == 1) { long ..
문제 https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 설명 배열에 자연수 x를 넣는다. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다. 최대 힙은 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙이다. 최대 힙을 구현하기 위해 MaxHeap 클래스를 만들고 추가 기능과 제거 기능을 추가한다. class MaxHeap { List list; public MaxHeap() { list = new Arra..
문제 https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 설명 1. 중간에 수의 변경이 빈번히 일어난다. 2. 그 중간에 어떤 부분의 합을 구하려 한다. N개의 수가 있고 위의 두 조건을 M번 실행한다고 가정한다. 매번 연산을 새로 하는 일반적인 방법으로는 1번 조건의 수행시간은 O(1) 이고 2번 조건의 수행시간은 \(O(N)\) 이다. 최종적으로 \(O(NM)\) 의 시간복잡도를 가진다..
트라이 (Trie) 문자열을 빠르게 검색할 수 있는 K진 트리 구조의 자료구조 단어 사전을 트라이로 생성한 후 찾을 단어가 생기면 트라이를 사용하여 검색한다. 트라이의 루트 노드는 항상 공백문자열 상태를 의미한다. 트라이에 단어 삽입하기 루트 노드부터 시작하여 삽입할 단어의 첫 글자부터 트라이를 탐색 만약 현재 노드의 자식 중 현재 입력 중인 철자에 해당하는 자식이 있다면 해당하는 자식 노드로 이동하고, 없다면 새로운 자식을 추가 단어를 삽입한 후에, 탐색된 마지막 노드에 현재 입력된 단어의 정보를 추가 트라이에 존재하는 가장 긴 문자열의 길이를 L이라 하고 총 문자열들의 수를 M이라 하자. 처음 트라이를 구축할 때에는 M개에 대해서 L만큼 걸리기 때문에 수행시간은 \(O(L \times M)\) 이다...
