동적계획법 (Dynamic Programming)
쉽게 풀면
계단을 한 칸 또는 두 칸씩 올라가는 방법이 몇 가지인지 세는 문제를 생각해봅시다. 10번째 계단에 도달하는 방법의 수를 구하려면 8번째와 9번째 계단까지의 방법 수를 더하면 되는데, 이 과정을 그냥 재귀로 풀면 같은 계단의 경우의 수를 수십, 수백 번씩 반복해서 다시 계산하게 됩니다. 동적계획법은 "한 번 계산한 값은 표(메모)에 적어두고, 다음에 같은 계산이 필요하면 다시 풀지 않고 표를 찾아본다"는 아이디어입니다. 이렇게 하면 지수적으로 늘어나던 계산량이 훨씬 줄어들어, 큰 문제도 빠르게 풀 수 있습니다.
왜 중요한가
동적계획법은 알고리즘 설계에서 가장 널리 쓰이는 최적화 기법 중 하나로, 문자열 정렬, 경로 탐색, 자원 배분 문제처럼 부분 문제가 반복적으로 등장하는 다양한 실무·연구 영역에서 계산 효율을 결정적으로 끌어올립니다. 생물정보학의 서열 정렬, 자연어처리의 편집거리 계산, 운영관리의 최적 자원배분 문제 등 여러 응용 분야에서 알고리즘의 핵심 구성요소로 등장하기 때문에, 컴퓨터과학 논문에서 시간복잡도를 논할 때 빠지지 않는 개념입니다.
논문에서는 이렇게 쓰입니다
이 문장은 모든 경우의 수를 하나하나 다 따지는 대신, 이전 단계에서 이미 계산해 둔 최적의 부분해를 재사용함으로써 계산 시간을 크게 줄였다는 뜻입니다.
생물정보학 연구에서 단백질 서열 비교라는 구체적인 문제에 동적계획법을 적용한 대표적인 사례로, 부분 서열 정렬 결과를 재사용해 전체 최적 정렬을 효율적으로 구합니다.
인공지능 연구에서 동적계획법의 아이디어가 강화학습의 가치함수 계산에 어떻게 확장되어 쓰이는지를 보여주는 예입니다.
조금 더 깊게 보면
동적계획법은 구현 방식에 따라 크게 두 가지로 나뉘는데, 재귀 호출을 하되 이미 계산한 값을 저장해두는 하향식(top-down, 메모이제이션) 방식과, 작은 부분 문제부터 차례로 표를 채워나가는 상향식(bottom-up, 타뷸레이션) 방식이 있습니다. 두 방식 모두 결과는 같지만 메모리 사용 패턴이나 구현 난이도에서 차이가 나므로 논문이나 코드에서 어떤 방식을 택했는지 명시하는 경우가 많습니다. 또한 이 기법이 성립하려면 문제가 "최적 부분구조"와 "중복되는 부분 문제"라는 두 조건을 모두 만족해야 하며, 이 조건을 만족하지 않는 문제에 억지로 적용하면 오히려 비효율적이거나 잘못된 결과를 낼 수 있습니다.
주의할 점
동적계획법은 아무 문제에나 쓸 수 있는 것이 아니라, 큰 문제의 답이 작은 부분 문제들의 답으로부터 구성될 수 있고(최적 부분구조) 같은 부분 문제가 반복해서 등장하는 경우에만 효과가 있습니다. 단순히 함수를 반복 호출하는 재귀함수와 혼동하기 쉬운데, 동적계획법은 그 재귀 호출 결과를 저장해 재사용한다는 점이 핵심적인 차이입니다.