[알고리즘] 알고리즘이란?

알고리즘이란 무엇인가

어떤 문제에 대해 입력을 받아서 수학적이고 논리적으로 정의된 연산과정을 거쳐 원하는 출력으로 변환/계산하는 절차이다. 이것을 프로그래밍 언어로 표현하면 프로그램 또는 코드가 된다. 입력 받은 정보는 배열, 연결리스트, 트리, 해시테이블 등의 접근과 수정이 빠른 자료구조에 저장된다. 자료구조에 저장된 입력 값은 단순한 연산과정을 거쳐 원하는 출력으로 계산된다. 

 

 

최대공약수 구하는 알고리즘(GCD)

유클리드의 GCD 알고리즘

유클리드의 최대공약수를 구하는 알고리즘이 최초의 알고리즘으로 알려져 있다. 최대공약수를 구하는 방법으로 유클리드가 고안한 것이 빼기를 이용하는 방법이다. 두 수 중 큰 수에서 작은 수를 빼는 행위를 큰 수가 더 작아질 때까지 반복하고, 둘의 역할을 바꿔 이를 반복한다. 그래서 두 수 중 하나가 0이 될 때까지 반복하면 0이 아닌 수가 바로 최대 공약수이다. 

 

 이 방법을 유클리드 호제법이라고 하는데,  A와 B의 (A >B) GCD는 A를 B로 나눈 나머지 r과 B의 GCD와 같다는 것을 통해 최대 공약수를 구한다. 이 정리를 증명하기 위해서는 최대 공약수의 정의를 이용한다. 

 

<유클리드 호제법 증명>

1. A = a*G, B = b*G (a, b는 서로소)

    → a와 b는 서로소이므로 G가 A와 B의 최대 공약수이다.

 

2. A = q*B + r  → a*G = q*b*G + r → r = (a-qb)*G

 

3. r = (a-qb)*G, B = b*G

    → r과 B의 최대 공약수 또한 G라는 걸 보이기 위해서는 a-qb와 b가 서로소이면 됨

 

 

> a-qb와 b가 서로소임을 증명

    1. a - qb = mp, b = np (앞에서 정의한 바에 따라 a, b는 서로소)

    → a - qb와 b가 서로소가 아니라고 가정

 

    2. a - q*np = mp → a = (m+qn)p

 

    3. a = (m+qn)p, b = np 

    → a와 b가 서로소라는 전제에 모순 발생 

 

    => a - qb와 b가 서로소가 아니라고 가정 틀림 -> a - qb와 b는 서로소임

 

결론 :  A와 B의 (A >B) GCD는 A를 B로 나눈 나머지 r과 B의 GCD와 같다.

 

GCD 알고리즘 구현

파이썬 코드로 구현할 때 3가지 방법으로 구현할 수 있다. 빼기를 통해서 구현할 수 있고, 나머지 연산을 통해서도 구현할 수 있다. 또 gcd_mod를 재귀적으로 표현할 수도 있다.

def gcd_sub(a, b):
	while a * b != 0:
		if a > b:
			a -= b
		else:
			b -= a
	return a + b
	
def gcd_mod(a, b):
	while a * b != 0:
		if a > b:
			a = a % b
		else:
			b = b % a
	return a + b
		
def gcd_rec(a, b):
	if a * b == 0:
		return a + b
	if a > b:
		gcd_rec(a%b, b)
	else:
		gcd_rec(a, b%a)

 

알고리즘의 시간복잡도

T(n)

 시간복잡도에서 중요한 것은 최악의 경우의 입력을 가정하여, 최악의 경우의 입력에 대한 알고리즘의 수행시간을 측정한다. 따라서 알고리즘의 수행시간은 최악의 경우의 입력에 대한 기본 연산의 수행 횟수를 의미한다. 최악의 경우 수행시간은 T(n)으로 표기 된다. 

 

Big-O 표기법

n은 입력으로 주어지는 값의 개수를 의미한다. 

결국 시간 복잡도에 영향을 주는 항은 최고차항이다. 따라서 최고차 항만을 남기고 나머지는 생략하는 식으로 수행시간을 간략히 표현하는 방법을 Big-O표기법이라고 부른다. 가장 빨리 증가하는 항에 곱해진 상수 역시 생략하고 남은 항을 O(~) 이런 식으로 표현한다.