Algorithm이란?

 

• Algorithm이란?

 

 

어떤 문제를 해결하기 위한 방법과 절차 등의 집합체를 말한다. 알고리즘의 어원은 약 9세기 페르시아의 수학자인 무함마드 알콰리즈미의 이름에서 유래되었다고 한다. 문제 해결을 위해서는 여러 알고리즘을 고안하고, 이들의 효율성을 평가한 후 최적의 알고리즘을 사용한다. 알고리즘은 다음과 같은 조건을 가지는데, 이 5가지를 모두 만족해야 알고리즘이라고 할 수 있게 된다.

 

 

 

1. 0개 이상의 입력이 존재
2. 1개 이상의 출력이 존재
3. 각 명령어의 의미가 명확해야함(명백성)
4.  한정된 수의 단계 후에는 반드시 종료(유한성)
5. 각 멍령어가 실행 가능해야함(유효성)

 

 

---

 

 

• 알고리즘의 표기

 

 

알고리즘을 표기하는 방법은 크게 자연어, 흐름도, 유사 코드, 프로그래밍 언어가 있다.

자연어는 한국어와 같이 알고리즘을 우리가 사용하는 언어로 풀어서 설명하는 것으로 이해는 쉬우나 가독성이 떨어질 수 있다. 흐름도는 알고리즘의 진행 과정을 나타낸 것이고, 유사 코드는 코드를 조금 쉽고 간결하게 쓴 것이다. 프로그래밍 언어는 알고리즘을 구현한 코드를 의미한다. 일반적으로는 간결하면서도 이해하기 쉬운 유사 코드로 많이 나타낸다.

 

 

---

 

 

• 알고리즘의 효율성 분석

 

 

좋은 알고리즘은 실행 시간이 빠르고, 메모리 사용량이 적은 알고리즘이다. 하지만 일반적으로 실행시간이 빠르면 그만큼 많은 메모리 공간을 필요로 하고, 메모리 공간을 적게 사용할수록 실행시간이 느리다. 따라서 우리는 실행 시간과 메모리 사용량 모두 적절하게 고려하여 알고리즘을 선정해야한다. 알고리즘의 효율성을 판단하기 위해 우리가 분석해야하는 것은 다음과 같다.

 

1. 실행 시간 분석(시간복잡도)

2. 메모리 분석(공간 복잡도)

 

 

보통은 메모리 사용량보다는 실행시간 개선에 더욱 초점을 둘 것이다. 따라서 우리는 시간복잡도 계산에 대해 중점적으로 알아볼 것이다.

 

 

시간 복잡도는 알고리즘이 실행될 때 소모되는 시간을 근사적인 식으로서 나타내는 방법이다. 시간 복잡도는 작업량을 기준으로 계산한다. 시간 복잡도 계산법은 다음에서 다루고, 일단 알고리즘에서 우리가 고려해야할 사항에 대해 생각해보면 크게 아래와 같이 세 경우를 생각해볼 수 있다.

 

 

1. 최선의 경우 : 알고리즘의 성능을 개선하는데 최선의 경우를 고려할 필요는 없다.
2. 평균적인 경우 : 일반적인 상황에서 소모되는 실행 시간이다.
3. 최악의 경우 : 해당 알고리즘이 가장 실행 시간이 오래 걸리는 경우로, 알고리즘 선정 시 가장 중요한 요소로 작용한다. 최악의 경우보다 시간이 더 오래 걸릴 수는 없기 때문에 일반적으로 최악의 경우를 가장 중점적으로 고려한다.

 

 

 

---

 

 

 

• 시간복잡도와 공간복잡도의 표현(점근적인 표기법)

 

 

알고리즘의 실행시간을 표기할 때는 불필요한 요소들을 배제하고 실행 시간에 가장 영향을 크게 미치는 요인에 대해 고려해야한다. 따라서 우리는 점근적인 표기법을 사용한다.

 

점근적인 표기법은 어떤 함수의 증가 양상을 다른 함수와의 비교로서 나타내는 방법으로, 식을 단순화한다는 뜻과 비슷하다.

 

위에서 언급했듯이 시간복잡도는 최선의 경우, 평균적인 경우, 최악의 경우의 세 가지 경우를 고려하는데, 최악의 경우는 Big-O(빅 오),  평균의 경우는 Big-θ(빅 세타), 최선의 경우는 Big-Ω(빅 오메가)로 나타낸다.

 

 

 

 

• 1. Big-O 표기법

 

상한 점근 표기법으로, 최악의 경우에도 이를 넘지 않는다는 뜻이다.

1 이상의 자연수 N을 입력받고, 1부터 N까지 모든 자연수를 오름차순으로 출력하는 알고리즘에 대해 생각해보자.

단순하게 생각하면 N번 반복하면서 자연수를 출력하므로 실행횟수는 N번이다. 따라서 해당 알고리즘의 시간복잡도는

O(N)이라고 나타낸다.

 

그렇다면 다음과 같은 알고리즘을 생각해보자.

1부터 N까지의 정수 N개가 한 줄로 랜덤하게 배치되어 있을 때, 1이상 N이하의 어떤 정수 K가 몇 번째 줄에 있는지 찾는

알고리즘에서 실행 횟수를 생각해보자.

 

만약 1부터 10까지의 정수 중 5를 찾는다고 해보자. 이 때 운이 좋으면 5가 맨 앞에 있어 1번만에 5를 찾을 수 있고

운이 나쁘다면 10번째에 5가 있어서 10번 반복해야할 수 있다.

이 때, Big-O 표기법은 최악의 경우를 고려하므로 N=10이면 10번, N=100이면 100번 반복하는 것이 최악의 경우이기 

때문에 시간복잡도는 O(N)이다.

 

 

 

• 2. Big-θ 표기법

 

상한 점근과 하한 점근의 평균적인 시간복잡도라고 생각할 수 있는데, 만약 O(N), Ω(N)이면 θ(N)이다.

 

 

 

• 3. Big-Ω 표기법

 

하한 점근 표기법으로, 최선의 경우에도 이보다 빠를 수 없다는 뜻이다.

예를 들어 입력값 N에 대해 알고리즘의 실행횟수가 최소 $N^{2}$이라면 Ω(N^{2})이다.

ex)

    Ω(N)∋$N^{2}$ ($N^{2}$번 반복하는 알고리즘은 최선의 경우에도 N번 이상 연산한다)

    Ω(1)∋NlogN (NlogN번 반복하는 알고리즘은 최선의 경우에도 1번 이상 연산한다)

 

위에서 나온 N개의 수 중 특정한 값 K를 찾는 알고리즘은 Ω(1)이고, 구구단 2단~9단을 출력하는 알고리즘은 Ω($N^{2}$)이다. 구구단을 출력하면 2단부터 9단까지 9줄이 출력되는데, 이 때 반복횟수는 (9-1)*9로, 이를 입력값 N으로 나타내면 (N-1)*N이다. 이를 근사적으로(점근적으로) 나타내면 $N^{2}$이므로 이 때 시간복잡도는 Ω($N^{2}$)이다.

 

 

 

---

 

• 시간복잡도에 영향을 미치는 요인

 

 

어떤 알고리즘의 입력값이 N일 때 반복횟수가 N에 대한 다항식으로 표현된다고 하자. 이 때, 시간복잡도에 가장 영향을 크게 미치는 것은 N에 대한 다항식의 최고차항의 차수, 각 문자에 곱해진 계수일 것이다.

ex) 어떤 알고리즘의 연산 횟수가 $N^{3}+2N^{2}+3$일 때 실행시간에 가장 영향을 많이 끼치는 것은 $N^{3}$이다.

 

 

위에서 언급했듯이 시간복잡도는 점근적인 표기법으로 나타내는데, 점근적인 표기법은 식을 근사해서 나타낸다. 따라서 예시로 최대 연산 횟수가 $3N^{3}+5N^{2}+7N+9$인 알고리즘의 시간 복잡도를 계산하기 위해선

 

 

1. 먼저 최고차항을 제외한 나머지 항은 지운다.

 

 

2. 그러면 $3N^{3}$만 남고 계수도 지우면 증가 함수는 $N^{3}$만 남는다.

 

 

 

그러면 이 알고리즘의 시간 복잡도는 $O(N^{3})$으로 나타내어진다. 이러한 방법으로 일반적으로 시간복잡도를 표현한다.

 

 

 

 

example

 

1. $N^{2}+3N+1$번 연산하는 알고리즘의 시간복잡도는?

$O(N^{2})$

 

 

2. $4*2^{N}+3$번 연산하는 알고리즘의 시간복잡도는?

$O(2^{N})$

 

 

 

 

위의 Big-Ω에서 살짝 언급했는데, $O(f(n))$은 연산 횟수가 $f(n)$을 넘지 않는 모든 함수들의 집합이라고도 볼 수 있다.

따라서 예를 들면 O($N^{3}$)∋$N^{2}+2N+1$이다.

 

 

 

시간복잡도의 종류와 예시

 

• $O(1)$

가장 빠른 시간복잡도로, 입출력 혹은 덧셈 등의 단 한 번 이루어지는 연산이 O(1)의 시간복잡도를 가진다.

 

 

 

• $O(logN)$

나중에 배우는 알고리즘인 이분 탐색이라는 알고리즘은 간단하게 설명하면, 탐색 범위를 반으로 쪼개 나가며 탐색이 이루어지는 알고리즘이다. 만약 1,024개의 원소를 탐색한다고 하면 1,024=$2^{10}$이므로 이분탐색을 적용하면 10번만에 값을 찾을 수 있는 알고리즘이다. 따라서 이 때의 연산횟수는 밑을 2로 하는 N의 로그인데, 이는 O(logN)으로 나타낸다.

 

 

 

• $O(N)$

위에서 설명한 예시 중, N개의 값들 중 특정한 값 K를 찾는 알고리즘의 시간복잡도이다.

 

 

 

• $O(NlogN)$

어떤 N개의 값들을 오름차순 혹은 내림차순으로 정렬하는 효율적인 알고리즘들이 $O(NlogN)$에 동작한다.

 

 

 

• $O(N^{2})$

구구단을 출력하는 등, 중첩해서 반복하는 알고리즘의 시간복잡도이다.

 

 

 

• $O(N^{3})$

서로 다른 주사위를 세 번 던저셔 나올 수 있는 모든 수의 순서쌍을 출력하는 알고리즘 등이 해당한다.

 

 

 

• $O(2^{N})$

동전 N개를 앞면 혹은 뒷면으로 배치할 때, 가능한 모든 동전의 배열을 출력하는 알고리즘 등이 해당한다.

 

 

 

• $O(N!)$

가장 비효율적인 시간복잡도로, 추후에 다룰 외판원 순회 문제를 완전탐색으로 해결할 때 발생한다.