----------------
title : 모두의 알고리즘 - 1. 어떤 알고리즘이 효율적인가?
cat_title :  1. 어떤 알고리즘이 효율적인가?
path : /알고리즘
next_page: 247
--------------

안녕하세요 여러분! 이번 강좌에서는 먼저 여러가지 알고리즘에 대해 다루기 앞서, 어떤 알고리즘이 효율 적이라 할 때 이를 나타내는 지표들에 대해 다루어 보도록 하겠습니다.

### 효율적인 알고리즘이란?

앞서 알고리즘이란 어떤 문제를 해결하는 방식이라고 하였습니다. 하지만 여기서 중요한 점은 어떤 문제를 어떻게 하면 **잘** 해결하느냐 입니다. 즉 동일한 문제를 해결하는 알고리즘이라 하더라도, 좀 안좋은 알고리즘은 오래 걸리겠지만, 효율적인 알고리즘이라면 훨씬 빠른 속도로 문제를 풀 수 있을 것입니다.

그렇다면, 여기서 중요한 것이 이 **빠른 속도**라는 것을 어떻게 하면 체계적으로 표현할 수 있느냐 입니다. 만약에 이 속도를 해당 알고리즘으로 문제를 해결하는데 걸리는 시간이라고 정의를 해봅시다. 문제는 이런식으로 정의를 하게 된다면, 컴퓨터 마다 그 결과가 제각각이 된다는 문제가 생깁니다. 

따라서 컴퓨터 과학자들이 택한 방식은 그 알고리즘으로 문제를 해결하는 동안 총 몇 번의 연산을 수행하느냐가 되었습니다.

예를 들어서 1 부터 100 까지 더하는 연산을 수행한다고 해봅시다. 만약에 단순하게 1 부터 100 까지 쭈르륵 더한다면, 총 100 번의 연산을 수행하겠지요. 

하지만, 좀 더 머리를 써서 등차수열의 합이 $$\frac{n(n+1)}{2}$$ 이 된다는 공식을 사용한다면, 덧셈 한번, 곱셈 한번, 나눗셈 한번 총 3번의 연산으로 답을 구할 수 있습니다.\sidenote{물론 컴퓨터 CPU 의 경우 덧셈과 뺄셈이 곱셈 나눗셈 보다 훨씬 빠릅니다. 쉽게 생각하면 덧셈 뺄셈이 곱셈 나눗셈보다 대략 3~4배 정도 빠르다고 보시면 됩니다. 하지만 전체 스케일로 볼 때 이는 크게 중요하지 않습니다.}

그렇다면, 좀 더 확장해서 1 부터 n 까지를 더한 값을 구한다고 생각해봅시다. 단순한 알고리즘으로는 총 $$n$$ 번의 연산을 수행하겠지만, 좀 더 똑똑하게 공식을 사용하는 알고리즘의 경우 여전히 3 번의 연산으로 끝낼 수 있습니다. 즉, 두 번째 방식이 분명 첫 번째 방식 보다는 훨씬 빠르게 수행될 것입니다.

이렇게, 알고리즘의 속도는 어떠한 크기의 입력값($$n$$)에 대해서 이 알고리즘을 수행하는 동안 몇 번의 연산을 실행하는지로 나타내며, 이를 **시간 복잡도(time complexity)** 라고 부릅니다.

우리의 단순 덧셈 알고리즘의 경우 입력값(여기서는 $$n$$)이 커지면 커질 수 록 알고리즘의 시간 복잡도도 더 커집니다 (정확히 말하자면 $$n$$ 에 비례해서 커지겠지요). 반면에 두 번째 공식을 사용한 알고리즘의 경우 입력값의 크기와는 무관하게, 항상 거의 상수 시간 안에 처리됩니다.

![caption=더 이상 CPU 는 예전 처럼 미친속도로 빨라지지는 않는다.](/img/cpu_growth.png)

시간 복잡도가 매우 중요한 이유는 실제 이 알고리즘의 수행 시간이 얼마나 걸리는지 알려주는 척도와 거의 직결되기 때문입니다. 당연하게도 알고리즘이 요구하는 연산의 속도가 적으면 적을 수 록 실제 컴퓨터에서도 대부분 더 빠르게 처리됩니다.\sidenote{물론 항상 그런 것은 아닙니다. 실제 컴퓨터에서 돌아가는 알고리즘은 필요한 연산 수 외에도 많은 것이 영향을 받습니다.}

물론 옛날 처럼 대략 2년 마다 CPU 집적도가 두 배씩 증가하는 **무어의 법칙(Moore's Law)** 가 딱딱 들어맞던 때에는 더 빨리 돌아가는 알고리즘을 고민할 시간에 차라리 새 CPU 를 사는 것이 더 나앗을지도 모릅니다. 예컨대 지금 여러분이 사용하는 CPU 는 1993년에 세상에서 제일 빨랐던 슈퍼 컴퓨터 보다도 아마 빠를 것입니다.\sidenote{당시 최대 속도를 자랑했던 Fujitsu Numerical Wind Tunnel 에서 사용한 컴퓨터는 124.5 GFLOPS 를 자랑했는데, 현재 여러분이 흔히 사용하는 Intel 의 SkyLake CPU 의 경우 대략 128 GFLOPS 정도 된다} 

하지만 이제는 더이상 예전처럼 컴퓨터 하드웨어의 발전 속도가 빠르지 않기 때문에, **더 빠른 알고리즘을 고민하는 것이 매우 중요**합니다.

두 번째로 알고리즘의 효율성을 평가하는데 있어서 중요한 점으로 얼마만큼의 메모리를 사용하느냐가 있습니다. 

1 부터 $$n$$ 까지의 덧셈을 수행하는 알고리즘을 조금 특이한 방법으로 만들어볼 것입니다. 일단, $$n$$ 의 범위는 int 의 범위라고 가정을 한다면 $$n$$ 은 최대 $$2^{32}$$ 이 되겠지요. 그런 다음에, 큰 배열을 생성한 다음, 첫 번째 원소에는 그냥 1, 두 번째 원소에는 1 부터 2 까지 더한거, 세 번째 원소에는 1 부터 3 까지 더한거, ... 쭉 해서 $$n$$ 번째 원소에는 1 부터 $$n$$ 까지 더한거를 저장해놓습니다.

그런 다음에, 사용자가 임의의 $$n$$ 에 대해서 1 부터 $$n$$ 까지 더한 값을 요청한다면, 덧셈을 새로 수행할 필요 없이 그냥 배열의 $$n$$ 번째 원소를 리턴해주면 됩니다. 만약에, 앞서 배열을 생성하는 작업을 무시한다면 (아니면 남이 만들어놓은 배열을 그냥 가져다 쓴다고 생각하셔도 됩니다), 사용자에 요청에 대해서 단 한 번의 연산 (배열의 $$n$$ 번째 원소를 가져옴)으로 덧셈을 수행할 수 있습니다. 

즉, 이 알고리즘의 시간 복잡도는 단 1 이 되겠지요. 그렇다면 이 알고리즘은 효율적인 것일까요? 아마 아무도 그렇게 생각하지 않을 것입니다. 왜냐하면 크기가 무려 $$2^{32}$$, 즉 4 기가 바이트에 달하는 배열이 필요하기 때문이지요. 

이러한 문제 때문에 시간 복잡도와는 별개로, 알고리즘이 작동하는데 메모리를 얼마나 사용하는지 나타내는 **메모리 복잡도(Memory complexity)** (혹은 **공간 복잡도(Space complexity)** 라고도 합니다) 도 알고리즘의 중요한 특징이 됩니다. 이 바보 같은 알고리즘의 경우 메모리 복잡도가 int 의 최대 크기 만큼 되겠네요.

반면에 우리가 처음에 다루었던 두 개의 알고리즘의 경우 한 몇 바이트 정도면 충분할 것입니다. 이 메모리 복잡도가 중요한 이유 역시, 실제 컴퓨터의 경우 메모리의 크기가 한정되어 있기 때문입니다. 따라서, 알고리즘을 설계할 때 이 알고리즘의 얼마나 많은 메모리를 소모하는지 확인하는 것도 중요합니다.

정리하자면, 좋은 알고리즘이란

* 시간 복잡도가 비교적 낮고
* 메모리 복잡도 역시 비교적 낮은

알고리즘을 의미합니다. 보통 둘 다 낮추는 것은 힘들어서, 시간이나 메모리 복잡도 둘 중 하나를 많이 낮추는 쪽으로 가는데, **메모리는 돈으로 살 수 있지만, 시간을 돈 주고 살 수 있는 것이 아니기 때문에** 대개 시간 복잡도를 낮추는 것을 중점으로 합니다.\sidenote{물론 CPU 역시 돈주고 더 살 수는 있지만, 여러개의 CPU 를 사용해서 한 개의 알고리즘을 돌리는 것은 쉬운일이 아닙니다. 반면에 메모리의 경우 더 큰 메모리를 사용하는 것은 크게 어렵지 않습니다.}


### Best, Worst, Average running time

앞서 컴퓨터에서 알고리즘의 시간 복잡도를 이야기 할 때, 입력값의 크기가 $$n$$ 일 때 몇 번의 연산을 수행하는지로 나타낸다고 하였습니다.

그런데 문제는 위에 나왔던 1 부터 $$n$$ 까지 더하는 알고리즘과 같은 간단한 경우 말고는, 알고리즘의 연산 횟수가 단순히 $$n$$ 에 의해 결정되는 경우는 많지 않습니다.

예를 들어서 우리가 문자열을 순서대로 정렬하는 알고리즘을 만들었다고 생각해봅시다. 같은 $$n$$ 개의 문자열이 있더라도, 만약에 문자열이 이미 정렬된 상태라면, $$0$$ 번의 연산으로도 데이터를 정렬 시킬 수 있을 것입니다 (이미 정렬되어있으니까요). 하지만, 데이터가 무작위로 있는 경우 여러번의 연산을 수행해야겠지요.

따라서, 이 알고리즘의 입력값이 $$n$$ 일 때 정확히 몇 번 연산을 하느냐에 대한 질문에는 딱히 대답할 수 없습니다. 그 대신에 

> 이 알고리즘의 입력값이 $$n$$ 일 때 **최대** 몇 번의 연산을 하느냐?

와

> 이 알고리즘의 입력값이 $$n$$ 일 때 **최소** 몇 번의 연산을 하느냐?

가 더 의미 있는 질문이겠지요. 이를 보통 *Best case running time* 과 *Worst case running time* 이라고 일컫습니다.

물론 이 두 질문은 매우 극단적이기 때문에, 만약에 이 알고리즘이 **보통 어떻게 작동하는지가 궁금**하다면

> 이 알고리즘의 입력값이 $$n$$ 일 때  **평균적**으로 몇 번의 연산을 하느냐?

로 알고리즘의 시간 복잡도를 표현하게 됩니다. 이를 보통 *Average case running time* 이라고 합니다. 

알고리즘의 시간 복잡도가 최대와 최소의 간격이 적으면 적을 수 록 좋습니다. 왜냐하면 안정적으로 동일한 성능을 보장한다는 뜻이니까요. 대개 자주 쓰이는 알고리즘들은 최대와 최소 횟수가 비슷한 경우가 많습니다.

### 점근적 표기법 (Asymptotic notation)

예를 들어서, 평균 연산 횟수가 $$n^2 + 100n + 2$$ 인 알고리즘을 생각해봅시다. 만약에 이 알고리즘의 시간 복잡도를 그냥 $$n^2$$ 이라고 그러면 어떨까요? 물론 $$n$$ 이 작을 때에는 오차가 클 것입니다.

![caption=빨간색이 원래 그래프고 초록색이 n 제곱으로 나타낸 것](/img/asymptotic_1.png)

위 그림의 경우 빨간색이 $$n^2 + 100n + 2$$ 그래프 이고, 초록색이 $$n^2$$ 을 나타낸 그래프 입니다. 위와 같이 $$n$$ 이 작을 경우 $$n^2 + 100n + 2$$ 가 $$n^2$$ 보다 훨씬 큰 것을 알 수 있습니다. 

하지만 $$n$$ 이 커진다면 어떨까요?

![caption=두 그래프의 차이가 거의 없다](/img/asymptotic_2.png)

위 그림에서도 보여지듯이, 두 그래프의 차이가 거의 없다는 것이 보입니다. 그도 그럴 것이, 두 그래프의 차이는 $$100n + 2$$ 인데, $$n$$ 이 5000 정도 된다면, $$100n + 2$$ 가 원래의 그래프에서 담당하는 양이 

$$\frac{100 \cdot 5000 + 2}{5000^2 + 100 \cdot 5000 + 2} \approx 2\%$$

2 퍼센트 밖에 되지 않기 때문입니다. 물론 이 값은 $$n$$ 이 점점 커지면 커질 수 록 작아질 것입니다. 따라서, 굳이 이 알고리즘의 시간 복잡도를 표현하는데 구질구질 하게 끝에 $$100n + 2$$ 를 붙일 필요가 사라졌습니다. 왜냐하면 어차피 $$n$$ 이 커지면 그 효과는 미미 하기 때문이지요.

컴퓨터로 알고리즘을 돌릴 때 $$n$$ 은 대개 매우 크기 마련입니다. 물론 $$n$$ 이 작다면, $$100n + 2$$ 의 영향은 오히려 $$n^2$$ 보다 크겠지만, 일반적인 상황에선 굳이 그 항을 포함시키지 않아도 알고리즘의 실행 성능을 가늠하는데에는 큰 영향이 없습니다. 

따라서, 컴퓨터 과학에서는 흔히 알고리즘의 시간 복잡도를 이야기 할 때 **점근적 표기법 (Asymptotic notation)**을 사용합니다. 점근적 표기법이란, 어떤 함수가 $$n$$ 이 클 때, 다른 어떤 함수로 근사될 수 있는지를 이야기 합니다.

위 경우 $$n^2 + 100n + 2$$ 의 경우 $$n$$ 이 커질 때 $$n^2$$ 으로 근사할 수 있고, 이를

$$ n^2 + 100n + 2 = \mathcal{O}(n^2)$$

로 표현합니다. 이를 보통 Big-$$\mathcal{O}$$ 표기법이라 부릅니다.

수학적으로 엄밀히 정의하자면 다음과 같습니다.

함수 $$f(x), g(x)$$ 에 대해 $$f(x)$$ 가 $$\mathcal{O}(g(x))$$ 를 만족한다면, $$x > x_0$$ 를 만족하는 모든 $$x$$ 에 대해 $$|f(x)| \le M|g(x)|$$ 인 양의 실수 $$M$$ 과 $$x_0$$ 가 존재한다.

즉 $$O$$ 안에 들어가는 함수는 근사하려는 함수의 **상한선** 을 담당하게 됩니다. 물론, **하한선**을 의미하는 Big-$$\Omega$$ 표기법도 있고, **상한 하한**을 모두 포함하는 Big-$$\Theta$$ 표기법도 있습니다. 당연히도 $$\Theta$$ 표기법이 좀 더 엄밀한 범위를 나타내기는 하지만 대부분의 경우 Big-O 표기법으로 알고리즘의 복잡도를 나타냅니다. 

그림으로 보면 아래와 같습니다.

![caption=각 표기법에 따른 함수들의 모습](/img/algorithm/1.1.1.png)


Big-$$O$$ 의 정의가 조금 어렵긴 하지만, 그냥 쉽게 생각하면, 그 함수의 최고차항이 대부분 Big-O 가 됩니다. 예를 들어보자면

* $$f(n) = 10n^3 + 2000n^2 + 100000n\rightarrow f(n) = \mathcal{O}(n^3)$$. 왜냐하면 최고차항이 $$n^3$$ 이니까. 물론 최고 차항의 계수도 무시해도 됩니다. (왜 그런지는 위 Big-O 의 정의를 다시 한번 읽어보세요)
* $$f(n) = e^n + n^{10000}\rightarrow f(n) = \mathcal{O}(e^n)$$. 지수 함수는 그 어떠한 다항 함수보다도 빠르게 증가한다고 생각하면 됩니다. 만약에, 알고리즘이 지수 함수적으로 늘어난다면, $$n$$ 이 조금만 커져도 컴퓨터가 계산할 수 없을 만큼 연산의 양이 많아집니다.
* $$f(n) = 100n\log n + n\rightarrow f(n) = \mathcal{O}(n\log n)$$. 많은 경우 알고리즘에 $$\log$$ 가 들어가게 됩니다. 보통은 밑이 2 인 $$\log$$ 를 사용하지만, 크게 중요하지는 않습니다. (왜 그럴까요?)
* $$f(n) = 100n\log n + n^{1.001}\rightarrow f(n) = \mathcal{O}(n^{1.001})$$. 지수 함수와는 반대로 로그 함수는 어떠한 다항 함수 보다도 느리게 증가합니다. 즉 $$\log_n$$ 보다 $$n^{0.001}$$ 이 훨씬 빠르게 증가합니다. 
* $$f(n) = 100\rightarrow f(n) = \mathcal{O}(1)$$. 보통 상수 함수는 $$\mathcal{O}(1)$$ 로 나타냅니다.

Big-O 의 종류 별로 얼마나 빠르게 증가하는지 보고 싶다면 아래의 그림을 보면 됩니다.

![caption=종류별 점진적 증가 속도](/img/big-o.jpeg)

보시다시피, 만약에 내가 만든 알고리즘이 $$O(n!)$$ 이나 $$O(2^n)$$ 단위라면, 알고리즘의 개선을 심각하게 고민해봐야 합니다. 보통 $$n$$ 이 100 만 넘어가도 연산 불가능한 양이 됩니다.

대부분의 경우에는 알고리즘의 복잡도를 $$O(n^2)$$ 안으로 끊을 수 있을 것입니다. 보통 $$n^2$$ 알고리즘에서 머리를 조금 쓰면 $$O(n\log n)$$ 으로 만들 수 있는 경우가 많습니다. $$\log n$$ 은 매우 느리게 증가하므로, 적당한 범위 안에 $$n$$ 이라면 거의 $$O(n)$$ 과 비슷한 속도로 동작합니다.

가장 이상적인 상황은 $$O(\log n)$$ 이거나 $$O(1)$$ 인데, 이 말은 **데이터 전부를 보지 않고도 알고리즘을 실행할 수 있다** 와 동일합니다. 보통, 이와 같은 알고리즘이 돌아가는 경우 여러 특수한 상황에 정의되어 있어야만 합니다. 

이 것으로 이번 강좌를 마치도록 하겠습니다. 다음 강좌에서 부터는 본격적으로 알고리즘에 대해 다루어 볼 것입니다. 

### 생각 해보기

#### 문제 1

버블 소트(Bubble sort) 의 최악의 경우, 최고의 경우, 평균적인 경우의 시간 복잡도는 어떻게 될까요?