우리는 경험을 통해 배운다. 셈과 구구단에서부터 어려운 알고리즘에 이르기까지, 우리가 경험한 것들을 바탕으로 얻은 규칙을 정제해 왔다. 경험하고, 잘 정리하고, 같은 상황에서 다시 불러와 쓰는 것은 기술의 기본이라는 뜻이다.
계속 기술적 발전을 추구하는 개발자의 입장에서, 내가 경험하는 것 뿐만 아니라 '기술자체가 경험하는 것은 어떨까?'라는 생각은 누구나 충분히 해볼만한 생각이다. 알고리즘의 혁신이 마치 속도의 향상이라고 하면, 가속도의 향상이라고 할 수 있는 동적 계획법(Dynamic Programming)을 알아보자.
동적 계획법(Dynamic Programming)
동적계획법은 위에 얘기한 인간의 기술적 발전과 같은 순서를 프로그램에 적용한 것이다. 연산(경험)하고, (연산 결과를) 잘 정리한 다음, 같은 상황에서 다시 불러와 쓰는 알고리즘이다. 이미 진행했던 연산을 다시 실행하지 않고 결과값을 불러오는 형태이기 때문에, 반복적인 연산이 진행되는 알고리즘일 수록 효과적이다.
문제를 파악하여 일정한 단위로 쪼갤 수 있다면, 연산 값을 저장해놓는 것만으로 많은 연산을 생략할 수 있는 알고리즘이다.
피보나치 알고리즘과 동적 계획법
피보나치 수열의 n번째 값을 구하는 알고리즘은 재귀함수로 구현할 수 있는 알고리즘의 대표이다. 반복적인 연산이 많고 직관적이기 때문에, 동적 계획법의 예시로 제격이다. 참고로 피보나치 수열은 n번째 수의 값이 (n-1)+(n-2)인 수열(단 첫 번째와 두 번째(혹은 0번째)는 1)이다.
기존의 재귀 함수 알고리즘은 fibo(0)과 fibo(1)이 호출되기 전까지 계속 재귀호출을 반복하지만, 동적계획법으로 개선된 알고리즘은 fibo(2), fibo(3), fibo(4), ... 등을 단 한번만 연산하고 그 이후 동일한 인자를 가진 함수는 메모에 저장된 값을 호출하여 계산한다. 때문에 연산 수에서 큰 차이를 보인다.
마무리
일을 시키려면, 내가 더 잘 알아야 한다.
