커다란 문제를 여러 단계로 나누어 해결하는 알고리즘들이 있어요. 그 중에 동적 프로그래밍(Dynamic Programming)은 문제를 해결하면서 얻은 체험 정보를 이용하여 문제를 해결하는 알고리즘이예요.
“동적 프로그래밍(Dynamic Programming)은 문제를 해결하면서 얻은 체험 정보를 이용하여 문제를 해결하는 알고리즘”
동적 프로그래밍을 이용하면 한 번 해결했던 문제를 다시 해결하지 않을 수 있기 때문에 문제 해결 비용을 줄일 수 있어요. 그리고 여러 단계를 거쳐 문제를 해결하는 복잡한 문제에서 이미 수행한 정보에서 다음 단계를 해결하기 때문에 똑같은 경험을 하지 않고 모든 경우의 경험을 할 수 있어요.
물론 여러 단계로 문제를 해결해야 하는 복잡한 문제에서 모든 경우를 경험하는 것은 컴퓨터로 계산하더라도 지구가 소멸할 시기까지 계산하지 못하는 문제들도 있어요. 이럴 때는 동적 프로그래밍보다 더 빠르게 계산할 수 있는 다른 방법이 필요하겠죠. 그렇다고 하더라도 이러한 문제들도 기본적인 개념은 동적 프로그래밍에서 출발할 때가 많습니다.
여기에서는 피보나치 수열처럼 일부 재귀적인 문제를 동적 프로그래밍으로 해결하는 방법을 알아볼 거예요. 그리고 순열 문제와 그래프에서 경로 찾기 문제를 동적 프로그래밍으로 해결하는 방법을 알아봅시다.
피보나치 수열은 기존에 해결한 항의 값을 기억해 두었다가 다음에 이를 구할 때는 계산하지 않고 기억해 두었던 값을 이용하여 수행 속도를 개선할 수 있어요.
하지만 순열 문제나 그래프에서 경로 찾기 문제는 문제를 해결하기 위해 여러 단계로 나누어 풀어야 합니다. 그리고 이전 단계에서 발생할 수 있는 여러 개의 단계를 임시 버퍼에 기록해 두었다가 하나씩 꺼내와서 다음 단계를 다시 조사하는 방법을 반복해서 수행합니다. 이 때 동적 프로그래밍은 스택을 임시 버퍼로 사용합니다.
하지만 한 단계에서 다음 단계로 경험할 수 있는 경우의 수가 많아져서 자료의 개수가 많아지면 컴퓨터로 계산하는 데 걸리는 시간은 기하급수적으로 늘어납니다.
여기에서는 그럼에도 불구하고 n을 비교적 작게 하여 나올 수 있는 모든 경우를 조사하는 것을 할 거예요. 이 책에서는 동적 프로그래밍으로 해결할 때 자료의 수가 클 때 수행 시간이 기하급수적으로 늘어나는 문제를 탐욕 알고리즘으로 해결하는 것은 소개하지만 의사결정 알고리즘은 소개하지 않습니다. 여러분께서 보다 깊이 있게 알고리즘을 학습하기 원하신다면 인공 지능에 사용하는 다양한 의사결정 알고리즘도 학습해 볼 것을 추천합니다.
하지만 현실적으로 알고리즘과 자료구조 외에 다른 프로그래밍 기술을 익히기를 원하신다면 이 책에 나와있는 자료구조와 알고리즘 수준에서 문제 해결 능력을 키우시고 다른 기술을 익히세요. 그리고 실무적인 프로젝트 주제를 선정하여 프로그래밍하면서 필요한 알고리즘을 학습하는 것이 나을 수도 있어요.
여러분이 실무에 진입하는데 시간적 여유가 있다면 보다 깊은 알고리즘을 학습하는 것도 하나의 선택일 수 있어요. 하지만 실무에 진입하는데 시간적 여유가 없다면 이 책에서 나온 알고리즘 수준까지 익힌 후에 다른 기술들을 익히는 것이 나은 선택일 확률이 높을 거예요.