유클리드 호제법

최대공약수를 구하는 빠른 방법.

호제법이란, 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 말한다.

두 수 a, b(a > b)의 최대공약수를 구하는 방법은 다음과 같다.

1. a를 b로 나눈 나머지(r)를 구한다.
2. b를 r로 나눈 나머지(r')를 구한다
3. r을 r'로 나눈 나머지를 구한다.
4. 이 과정을 나머지가 0일 때까지 반복한다.
5. 나머지가 0일 때, 나눈 값(둘 중 작은 값)이 최대공약수다.

일반적으로 소인수분해를 이용해 최대공약수를 구하지만, 이 방법을 사용하면 큰 값의 최대공약수도 빠르게 찾을 수 있다는 장점이 있다.

def euclidean(a, b):
    r = a % b
    if r == 0:
        return b
    return euclidean(b, r)    

최소공배수

초등학교 수학시간에서 최소공배수를 구할 땐, 최대공약수와 마찬가지로 소인수분해를 통해 나온 값을 이용했다. G를 최대공약수라 했을 때, a와 b를 각각

a = Gx
b = Gy

로 표현할 수 있다. 여기서 x와 y는 서로소다.

최소공배수는 최대공약수(G) * x * y 이므로, 해당 식을 구하려면 다음의 과정을 거친다.

a = Gx
b = Gy

a * b = Gx * Gy = G*G*x*y
(a * b) / G = Gxy

따라서, 두 수를 곱하고 최대공약수로 나누면 최소공배수가 나온다.

기타

동서남북

동서남북으로 움직이는 설정의 문제가 제법 있다. 그럴때마다 방향으로 분기를 나눠서 방향에 맞게 y와 x에 1을 더하거나 빼거나 했다.
이를 좀 더 간편하게 할 수 있다.

# 기존 방법

UP = 0
RIGHT = 1
DOWN = 2
LEFT = 3

if direction == UP:	
	move(y-1, x)
elif direction == DOWN:	
	move(y+1, x)
elif direction == LEFT:	
	move(y, x-1)
elif direction == RIGHT:	
	move(y, x+1)
    
# 간편한 방법

dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]

move(y+dy[direction], x+dy[direction])