푸으름

Algorithm 공부 #12 - 정수론(유클리드 호제법과 확장 유클리드 호제법) 유클리드 호제법(최대 공약수 구하기) ● 큰 수를 작은 수로 나누는 MOD연산 ● 앞 단계에서 나왔던 작은 수와 나머지를 다시 MOD연산 ● 이렇게 반복하면서 나머지가 0이 되면 그 순간의 작은 수를 최대 공약수로 선택 ex) 270과 192 270 mod 192 = 78 192 mod 78 = 36 78 mod 36 = 6 36 mod 6 = 0 => 0이 되는 순간 6을 return, 즉 270과 192의 최대공약수는 6 백준 1934번 최소공배수 https://www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수..

Algorithm 공부 #11 - 정수론(소수 구하기&오일러 피) 소수 구하기(에라토스테네스의 체 원리) ● 구하고자 하는 소수의 범위만큼 1차원 배열을 생성 ● 2부터 시작하고 현재 숫자가 지워진 상태가 아닌 경우 현재 숫자의 배수들을 배열에서 모두 지우기 ● 처음으로 선택된 숫자들은 지우지 않고 반복문을 N의 제곱근까지만 돌림 ● 시간 복잡도는 O(Nlog(logN)) 백준 1929번 소수 구하기 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net ※ N의 범위가 1,000,..