앞으로 알고리즘 시리즈에 올라오는 모든 내용은 Sanjoy Dasgupta, Christos Papadiimitriou, Umesh Vazirani 저자의 Algorithms과 POSTECH의 안희갑 교수님의 강의를 기반으로 하며, 추가로 공부한 내용을 개인적으로 정리하고자 글을 작성할 것이다. 이 외에도 여러 알고리즘과 관련된 문제들을 풀거나 아이디어가 있으면 남길 것이다.
알고리즘의 시작
우리는 십진수를 사용하는데 익숙하다. 서기 600년 즈음에 인도에서 십진법이 발명이 되었고, 이는 아무리 큰 숫자라도 단 10개의 기호들만을 가지고 간결하게 표현할 수 있는 기본적인 단계들을 거쳐서 효율적인 사칙연산도 가능하다. 이러한 십진법이 널리 퍼지는 데는 여러 장벽들로 인해 오랜 시간이 걸렸다. 9세기에 바그다드에 살았던 누군가가 쓴 아랍어로 된 교과서로 인해 십진법의 전파가 시작 되었다.
여기서 알고리즘이란 단어가 등장하며, 수 세기가 지난 후에 유럽에서 십진법을 발명한 사람을 기리기 위해서 채택 된 용어다. 그 후로 십진법과 십진법의 수치 알고리즘들은 서구 문명화에 큰 기여를 했다. 시간이 흐르면서 세계 곳곳의 학자들은 더 복잡한 알고리즘을 개발하고, 이는 세상을 바꾸고 있다.
피보나치
피보나치(Fibonacci)란 무엇인가? 이는 수열의 일종으로 수열 내에서 각 숫자는 이전 두 숫자의 합으로 나타낸다. 정확하게는 다음과 같은 간단한 규칙에 의해서 생성이 된다.
피보나치 수열은 여러 분야에 적용이 되고, 컴퓨터에서는 2n과 함께 가장 인기 있는 수열 중 하나이다. 그렇다면 Fn에서 n의 값이 증가하게 된다면, 정확한 값은 무엇일까? 이를 알기 위해서는 n번째 피보나치 숫자를 구하는 알고리즘이 필요하며 이는 다음과 같다.
우리는 이제부터 알고리즘을 볼 때 항상 3가지를 확인할 것이다.
1. 올바른 알고리즘인가?
2. n이 가지는 값에 따라 어떤 수행 시간을 보이는가?
3. 더 좋은 알고리즘은 없는가?
첫번째 질문은 당연히 패스다. 피보나치 수열의 정의를 가지고 만들었기 때문이다. 두번째 질문을 확인해보면, 우리는 여기서 T(n)을 fib1(n)을 계산하기 위한 기본적인 컴퓨터 연산의 개수라고 할 것이다. 보통 T(n)을 구하면 되는데, 우선 n이 2보다 작다면 몇 개의 연산만 수행하고 종료될 것이다.
n이 더욱 커지면, T(n-1)과 T(n-2)만큼의 시간이 걸리는 fib1의 재귀 호출을 해야하고, 3번의 연산을 더 해야 한다.
이를 Fn의 점화식과 비교해 보면 T(n)이 Fn보다 크거나 같게 될텐데, 이는 곧 알고리즘의 수행 시간이 피보나치 수열값만큼 빠르게 늘어나는 셈이다. 즉, T(n)은 n에 대해서 지수 시간의 수행 시간이 필요하게 되어 n이 매우 작지 않으면 이 알고리즘은 쓸모없을 만큼 느리다는 것을 의마한다.
물론 컴퓨터의 발전 속도로 인해 이 또한 느린 것은 아니지만, 결과적으로 정의에 따라 만든 알고지름은 올바른 결과를 찾기는 하지만 속도적인 측면에서 좋지 않다.
지수 시간보다는 다항 시간 알고리즘
fib1이 느린 이유는 함수 호출시 연쇄적으로 호출되는 재귀 함수 속에서 수많은 계산이 반복되기 때문이다.
이를 해결하기 위해서 더 합리적인 방법으로 중간 결과들을 나오는대로 저장해서 재사용하는 것이다.
이는 fib1처럼 정의를 그대로 사용하기에 알고리즘이 올바른 것은 타당하다. 그렇다면 수행 시간을 보게 되면, n-1번 반복 되는 루프 안에서 연산이 단 한번만 수행된다. 이 방법을 통해서 우리는 지수 시간 알고리즘을 다항 시간 알고리즘으로 대체할 수 있음을 확인 했다. 물론 이 방법보다 더 빠른 방법도 존재한다. 여기서 중요한건 알고리즘이 타당하더라도 수행 시간을 반드시 고려해야 한다는 것이다.
Compuational Efficiecy
앞서 다항 시간 알고리즘이 지수 시간 알고리즘보다 더 나은 알고리즘이라고 했다. 이렇게 계산적인 측면에서 효율이 다르기에 우리는 앞으로 여러 알고리즘을 생각할 때 더 나은 방향으로 생각하는 것이 중요하다. 다음은 n의 수가 증가함에 따라 시간이 얼마나 차이가 나는지 보여주는 그래프이다.
로그(log) 시간은 문제를 해결하기 위한 필요한 단계들이 연산마다 특정 요인에 의해 줄어들게 되는 만큼 속도가 굉장히 빠른반면, 팩토리얼(factorial) 시간은 급격하게 속도가 느려지는 것을 알 수 있다.
