1. Introduction 이번 포스팅에서는 호제법보다 빠른 최대공약수 식별 알고리즘을 소개한다. 스테인 알고리즘 (Stein's algorithm) 이라고도 불리는 알고리즘이며, 기존의 호제법보다 60%의 효율개선을 보이는 획기적인 알고리즘이다. 는 그렇게 대단한 알고리즘이 아니다... 스테인 알고리즘은 이진 GCD 알고리즘이라고도 불리며, 호제법의 이진버전이라고 생각하면된다. 호제법에서 각 루틴마다. $A \bmod B (A>B)$ 를 수행하지만, 스테인 알고리즘에서는 A와 B를 모두 반으로 나눈다. 2. Approach 다음과 같은 규칙을 따른다. 두 수가 짝수일 때는 2로 나눈다. a 변수를 1증가시킨다. 한 수만 짝수일 때는 그 수를 2로 나눈다. 두 수가 홀수일 때는 큰 수에서 작은 수를 뺀..

1. Introduction 소수는 1과 자기 자신외에는 약수를 가지지 않는 수를 의미한다. 소수를 판별하는 가장 간단한 방법은 2부터 자기자신까지의 수 (효율적으로는 $\sqrt {n}$까지)를 차례로 나눠보는 것이다. 하지만 대량의 소수를 얻어야 할 경우에도 위와 같은 방법을 쓰는 것이 최선일까? 이번 포스팅에서는 대량의 소수를 효율적으로 얻는 에라토스테네스의 체라는 방법을 소개한다. 2. Approach 에라토스테네스의 체의 기본적인 아이디어는 단일 소수판별법처럼 n에 대한 약수로 접근하는 것이 아니라, n의 배수를 기반으로 접근한다. 먼저 1은 소수가 아니므로 제외한다. 2부터 시작해서 소수를 찾으면서 합성수를 제거해 나간다. 2의 배수들은 모두 2를 약수로 가지므로 제외한다. 이제 다음으로 제외..

1. Introduction $a^b \bmod m$형태를 계산하는 방법은 여기에 포스팅했다. 이번 포스팅에서는 이것을 돌리기 위한 코드를 최적화하는 방법을 소개한다. 2. Approach $a^b$의 형태의 자연수에 대한 나머지 계산에 대한 방법들을 소개한다. 2.1 일반적인 방법 def powMod1(base, index, mod): r = 1 for i in range(index): r *= base r %= mod return r 시간복잡도가 $O(b)$이다. r이 $a^b$까지 커지기 때문에 overflow일어나기 매우 쉽다. 2.2 개선된 방법 def powMod2(base, index, mod): if index == 1: return base if index % 2 == 0: r = pow..

1. Introduction 순열이란, 어떤 데이터들에 대해서 해당 데이터로 줄을 세우는 것을 말한다. 예를 들어, (1,2,3) 에 대한 순열은 다음과 같다. (1,2,3) (1,3,2) (2,1,3) (2,3,1) (3,1,2) (3,2,1) 필자는 알고리즘에서 순열을 처음 배울 때 재귀로 푼다는 말을 듣고도 틀렸고, 나중에 시간이 한참지나서 시험칠 때 다시 공부했을 때도 틀렸고, 지금 포스팅할때도 틀렸다... 2. Approach 앞서 설명했듯, 순열은 재귀로 푼다. 다만 그 과정이 쉽게 머리에 박히지 않아서 그림을 통한 설명이 필요하다. 아래 그림은 순열을 구하는 과정을 시각화한 것이다. 사전순으로 얻는 과정을 (즉, 결과가 뒤에서 부터 swap됨) 앞에서 부터 순서대로 고정한다는 개념으로 설명하..