알고리즘을 배우기 위한 준비

알고리즘이란 문제를 해결하는 단계적 절차 또는 방법이다.
알고리즘에는 입력이 주어지고, 알고리즘은 수행한 결과인 해(또는 답)를 출력한다.

알고리즘의 특성

• 정확성: 알고리즘은 주어진 입력에 대해 올바른 해를 주어야 한다. (안정적 정확성)
• 수행성: 알고리즘의 각 단계는 컴퓨터에서 수행 가능하여야 한다. (잘 정의된 동작 명령)
• 유한성: 알고리즘은 일정한 시간 내에 종료되어야 한다.
• 효율성: 알고리즘은 효율적일수록 그 가치가 높아진다.

최초의 알고리즘

가장 오래된 알고리즘은 기원전 300년경 유클리드(Euclid)의 최대공약수 알고리즘이다. 유클리드 호제법이라고도 부른다.

- 유클리드의 최대공약수 알고리즘

2개의 자연수의 최대공약수는 큰 수에서 작은 수를 뺀 수와 작은 수와의 최대공약수와 같다는 성질을 이용한다.

a = a'G, b = b'G
a', b'는 서로소이고, G는 최대공약수이다.
a - b = a'G - b'G = (a' - b')G
a + b = a'G + b'G = (a' + b')G
(a' - b')와 b'도 서로소이므로, G는 (a - b)와 b의 최대공약수이다.
a' - b'와 b'가 서로소가 아니라고 하면 a', b'가 서로소라는 가정에 위배된다.

GCD(u, v) = GCD(u-v, v)
GCD(u, v) = GCD(v, u)
GCD(u, 0) = u

유클리드의 최대공약수 알고리즘은 다음과 같다.

Euclid(a, b)
입력: 정수 a, b; // 단, a>=b>=0
출력: 최대공약수(a, b)
1. if (b=0) return a
2. return Euclid(b, a mod b)

알고리즘의 표현 방법

- 자연어 (natural language)

인간이 사용하는 말로 표현된다.
이해가 쉬우나 모호성이 존재한다.

- 순서도 (flow chart)

어떤 일을 처리하는 과정을 도형과 화살표로 도식화한 것이다.
구조적으로 이해하기 쉬우나 재코딩이 불편하다.

- 의사코드 (pseudo code)

프로그램을 작성할 때 각 모듈이 작동하는 논리를 표현하기 위한 언어이다. 일반적으로는 자연어를 이용해 만든 문장을 프로그래밍 언어와 유사한 형식으로 배치한다.
프로그래밍 언어와 유사하여 코딩이 용이하다.

1. max = a[0]
2. for i = 1 to 9
3. if (a[i] > max) max = a[i]
4. return max

입력으로 배열 a에 10개의 숫자가 있다고 가정했을 때의 의사코드이다.

알고리즘의 분류

문제 영역(domain)에 기반한 분류

• 정렬 알고리즘
• 그래프 알고리즘
• 기하 알고리즘

특정 환경에 따른 분류

• 병렬(Parallel) 알고리즘
• 분산(Distributed) 알고리즘
• 양자(Quantum) 알고리즘

기타 알고리즘들

• 확률 개념이 사용되는 랜덤(Random) 알고리즘
• 유전자(Genetic) 알고리즘

알고리즘의 효율성 표현

• 시간 복잡도(time complexity): 알고리즘이 수행하는 기본적인 연산 횟수를 입력 크기에 대한 함수로 표현한다.
• 공간 복잡도(space complexity): 알고리즘이 수행하는 동안 사용되는 메모리 공간의 크기이다.

일반적으로 알고리즘을 비교할 때는 시간 복잡도가 주로 사용된다.

알고리즘의 복잡도 표현 방법

• 최악 경우 분석 (worst case analysis)
• 평균 경우 분석 (average case analysis)
• 최선 경우 분석 (best case analysis)

복잡도의 점근적 표기(Asymptotic Notation)

시간(또는 공간) 복잡도는 입력 크기에 대한 함수로 표기한다. 이 함수는 주로 여러 개의 항을 가지는 다항식이다.
차수가 작은 항과 계수는 무시한다.
-> 유의미한 차이만을 부각해 알고리즘 성능을 그룹핑함으로써 단순하고 명확한 분석을 가능하게 한다.

O(Big-Oh)-표기

복잡도의 점근적 상한을 의미한다.
복잡도가 f(n) = 2n²-8n+3일 때, f(n)의 O-표기는 O(n²)이다.
cg(n)(c>0인 임의의 상수)은 n이 증가함에 따라 f(n)의 점근적 상한이다.

Ω(Big-Omega)-표기

복잡도의 점근적 하한을 의미한다.
복잡도가 f(n) = 2n²-8n+3일 때, f(n)의 Ω-표기는 Ω(n²)이다.
cg(n)(c=1)은 n이 증가함에 따라 f(n)의 점근적 하한이다.

Θ(Theta)-표기

O-표기와 Ω-표기가 같은 경우이다.
f(n) = 2n²+10n+3 = O(n²) = Ω(n²)이므로, f(n) = Θ(n²)이다.
f(n)은 n이 증가함에 따라 상한과 하한 동시에 만족한다.

자주 사용하는 O-표기

• O(1): 상수 시간(Constant time)
• O(logn): 로그(대수) 시간(Logarithmic time)
• O(n): 선형 시간(Linear time)
• O(nlogn): 로그 선형 시간(Log-linear time)
• O(n²): 제곱 시간(Quadratic time)
• O(n³): 세제곱 시간(Cubic time)
• O(2ⁿ): 지수 시간(Exponential time)

O-표기의 포함 관계

효율적인 알고리즘이 필요한 이유

슈퍼컴 사용 < 효율적인 알고리즘

이 표로 설명이 될 것 같다.
10억 개의 숫자를 정렬하는데 알고리즘에 따라 300여 년이 5분으로 단축되는 것이 놀랍다.

값비싼 H/W의 기술 개발보다 효율적인 알고리즘 개발이 훨씬 더 경제적이라고 한다.
효율적인 알고리즘이 굉장히 중요하다는 걸 깨달았다.

[참고] 알기 쉬운 알고리즘