수학

[수학] 유클리드 호제법; 최대공약수를 구하는 빠른 방법

소개 임의의 2개 수에 대한 최대공약수를 구하는 과정에 대하여, 각 수를 임의의 수로 나눠보는 과정 없이 빠르게 최대공약수를 구해내는 방법 개념 두 양의 정수 a, b에 대하여, a = bq + r (0 ≤ r < b)일 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 만약 r이 0이라면, a와 b의 최대공약수는 b이다. public static int gcd( int a, int b ) { int r = a % b; while( r != 0 ) { a = b; b = r; r = a % b; } return b; } 시간복잡도: O(logn) 원리 [수학알고리즘] 유클리드 호제법 [수학알고리즘] 유클리드 호제법 이 글에서는 유클리드 호제법의 증명과 원리를 다룹니다. justicehui.git..

[수학] 소수판정 알고리즘

개요 백준 문제풀이과정에서 유용하게 사용했던 알고리즘들을 유형별로 정리하여 분석 및 복습하고자 별도의 글로 정리하게 됨 정의: 소수(Prime Number) 소수란 자신보다 작은 수들의 곱으로 만들어질 수 없는, 약수를 1과 자신밖에 가지지 못하는 수를 말합니다. 소수가 등장하는 순서에 규칙이 존재하지 않기 때문에, 소수를 판정하는 알고리즘은 시간복잡도가 중요합니다. 방법1. 약수범위 내에서 하나씩 나눠보며 소수여부 판단 1) 2부터 1씩 늘려가며 나눠보고 판단하기 1은 모든 소수의 약수이므로, 2부터 1씩 늘려가며 판별하고자 하는 숫자와 일일히 나눠보는 방법으로, 가장 간단하면서 원초적인 방법입니다. // 판독하고자 하는 숫자: n i값을 2부터 n까지 1씩 늘리며 순회하는 과정에서 아래 작업을 반복수..