알고리즘이란?
어떤 문제를 해결하기 위한 일련의 절차를 공식화한 형태로 표현한 것.
- 집에서 학교로 가는 길 찾기
- 샌드위치 만드는 방법
- 매점에 가서 물건 구매하기
프로그래밍에서의 알고리즘
input 값을 통해 output 값을 얻기 위한 계산 과정을 의미
이러한 문제를 해결할 때, 정확하고 효율적으로 결과값을 얻기 위해서 알고리즘이 필요
알고리즘의 조건
- 입력 : 외부에서 제공되는 자료가 0개 이상 존재
- 출력 : 적어도 2개 이상의 서로 다른 결과를 내어야 함. 즉 모든 입력에 하나의 출력이 나오면 X
- 명확성 : 수행 과정은 명확하고 모호하지 않은 명령어로 구성되어야 함
- 유한성 : 유한 번의 명령어를 수행 후 유한 시간 내에 종료
- 효율성 : 모든 과정은 명백하게 실행 가능(검증 가능)한 것이어야 함
알고리즘의 효율성 표현
- 빠른 알고리즘을 만들기 위해 가장 먼저해야 할 일 ➡ 알고리즘의 속도를 어떻게 측정할지 정하는 것
Q) 두 알고리즘의 속도를 비교하는 가장 좋은 방법이 뭘까?
A) 같은 입력에 대해 두 프로그램의 수행 시간을 측정해보자
➡ 부적합
WHY?
1) 프로그램의 수행 시간은 사용한 프로그래밍 언어, 운영체제, 컴파일러 등 수많은 요소에 의해 바뀔 수 있음
2) 외적인 요인을 전부 통일해도 사용한 문자열 구현, 함수 인자를 어떻게 넘겼는지 등에 따라 크게 달라짐
3) 프로그램의 실제 수행 시간이 다양한 입력에 대한 실행 시간을 반영하지 못함
➡ 수행시간을 측정할 다른 기준이 필요
시간 복잡도
시간복잡도 (time complexity) : 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수료 표현
- 가장 널리 사용되는 알고리즘의 수행 시간 기준
- 최악 경우 분석 (worst case analysis)
: 어떤 입력이 주어지더라도 얼마 이상을 넘지 않는다 - 평균 경우 분석 (average case analysis)
: 입력의 확률 분포를 가정하여 분석
: 대부분 균등 분포 (uniform distribution)을 가정 = 입력이 무작위로 주어진다고 가정 - 최선 경우 분석(best case analysis)
: 거의 사용되지 않지만 최적(optimal) 알고리즘을 고안하는 데 참고 자료로서 활용됨
일반적으로 최악 경우 분석으로 알고리즘의 복잡도를 나타냄
대부분의 알고리즘이 입력에 따라 수행 시간이 다를 수 있기 때문
분석 방법 EX)
- 최선 경우 : 집을 나와서 6분 후 지하철 역에 도착하고 운이 좋게 바로 열차를 탄 경우 (6 + 20 + 10 = 36분)
- 최악 경우 : 역에 도착 후 승차하려는 순간 문이 닫혀서 다음 열차를 기다려야 하는 경우 (36 + 4 (기다리는 시간) = 40분)
- 평균 경우 : 최악과 최선의 중간이라 가정 (36 + 2 = 38분)
"늦어도 40분이면 간다" → 최악 경우를 뜻함
복잡도의 점근적 표기
- 시간복잡도 → 입력 크기에 대한 함수로 표기 → 여러 개의 항을 가지는 다항식
- 단순한 함수로 표현하기 위해 점근적 표기 (asymptotic notation)을 사용
- 입력 크기 n이 무한대로 커질 때의 복잡도를 간단히 표현하기 위해 사용하는 표기법
EX) 3n3 - 15n2 + 10n - 18 ➡ n3
- 상한, 하한, 동일한 증가율의 개념을 적용하여 점근적 표기를 사용함
- O (Big - Oh) 표기
: 복잡도의 점근적 상한 - Ω (Big - Omega) 표기
: 복잡도의 점근적 하한 - θ (Theta) 표기
: 복잡도의 상한과 하한이 동시에 적용되는 경우
- O (Big - Oh) 표기
O (Big - Oh) 표기법
- 함수의 점근적 상한을 나타냄
- 간단히 말하면 주어진 함수에서 가장 빨리 증가하는 항만을 남긴 채 나머지를 다 버리는 표기법
N 에 대한 함수f (N)이 주어질 때, f(N) = O(g(N))
아주 큰 N0 와 C (N0 , C > 0)를 적절히 선택하면 N0 ≤ N인 모든 N에 대해 |f(N)| ≤ C × |g(N)|이 참이 되도록 할 수 있다
EX) N2 + 100 × N + 1 = O(N2)
N2은 N2 + 100 × N + 1 보다 작지만, 이 중 가장 빠르게 증가하는 항
- N 이 엄청나게 커지게 되면 N2 과 N2 + 100 × N + 1 사이에는 큰 차이가 없게 됨
적절한 상수 C 를 선택해 N2 에 곱해주면 항상 N2이 더 크다고 할 수 있음
- N0 = 1000, C = 2 라고 하면 위 조건이 항상 성립
O (Big - Oh) 표기법 성능비교
| O(1) | 상수 시간 (constant time) | 짝수 인지 홀수인지 결정 |  |
| O(logN) | 로그(대수) 시간 (logarithmic time) | 이진 탐색 | |
| O(N) | 선형 시간 (linear time) | 선형 탐색 | |
| O(NlongN) | 로그 선형 시간 (log-linear time) | 합병 정렬 | |
| O(N2) | 이차 시간 (quandratic time) | 버블 정렬 | |
| O(2N) | 지수 시간 (exponential time) | 피보나치 수열 (재귀함수) |
- 상수시간 O(1)은 입력 크기 n에 대하여 변하지 않는 일정한 시간이 걸린다는 뜻
- 일반적으로 k가 상수일 때, O(Nk)을 다항식 시간 (polynomial time)이라고 말함
참고문헌
1) 양성봉, 『알기 쉬운 알고리즘』, 생능출판 (2013)
2) 구종만, 『프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략』, 인사이트 (2012)