IT's 2 EG

에라토스테네스의 체(Sieve of Eratosthenes) 고대 그리스의 수학자 에라토스테네스가 만들어 낸 비교적 작은 구간(10^8 이하)에서 소수를 빠르게 찾는 방법 입니다. 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체라고 부릅니다. 에라토스테네스의 체 소수 확인 과정 N개의 자연수를 모두 적습니다. 이 중 1을 제외한 2부터 진행을 합니다. 여기서 자기 자신을 제외한 자기자신의 배수를 제외시키면서 소수를 확인 합니다. 2의 경우 2를 소수로 지정하고, 2의 배수인 4, 6, 8, 10 등은 소수에서 제외합니다. 위와 같은 행위를 반복하여 소수를 찾습니다. 에라토스테네스의 체 예제 www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N..

유클리드 호제법이란? 2개 정수의 최대공약수를 구하는 방법 중 하나입니다. 2개의 정수 a, b (a>b) 에 대하여 a를 b로 나눈 나머지를 r이라 할때, a와 b의 최대공약수는 b와 r의 최대공약수와 같음을 활용합니다. 이 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수 입니다. 유클리드 호제법 구현 int a, b; int gcd(int a, int b) { if (b > a) swap(a, b); int r = a % b; if (r == 0) return b; else return gcd(b,r); } 유클리드 호제법 예제 www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄..

유니온 파인드란? 이름 그대로 Union 연산과 Find 연산을 지원하는 자료구조입니다. 상호 배타적(중복되지 않은) 부분집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는데 사용합니다. 유니온 파인드 연산 일반적으로 트리 형태의 자료구조로 표현하며 아래 3가지 연산을 사용합니다. - 초기화: N개의 원소가 각각 자기자신을 루토 노드로 설정합니다. - UNION 연산: 두 원소 a, b가 주어질때, 로트 노드를 동일하게 설정하여 이들이 속한 두 집합을 합칩니다. - FIND 연산: 원소 a에 대한 로트 노드를 재귀함수로 탐색을 합니다. 유니온 파인드 구현 아래와 같이 초기화, UNION, FIND 함수를 구현할 수 있습니다. const int MAX_SIZE = 1000000; int root[MAX..