코딩 테스트 단골 '동적 계획법'의 황당한 유래... "장관님 눈치 보여서 지음"

요약 컴퓨터 과학과 코딩 테스트에서 빠지지 않고 등장하는 핵심 알고리즘 기법인 '동적 계획법(Dynamic Programming, DP)'의 독특한 탄생 배경과 기본 개념을 다룬 글이 화제가 되었습니다. 1950년대 DP를 창안한 미국의 수학자 리처드 벨만(Richard Bellman)의 자서전에 따르면, 사실 '동적 계획법'이라는 거창한 이름은 당시 미 국방부의 연구비 삭감을 피하기 위해 지어낸 일종의 말장난이었습니다. 당시 벨만이 일하던 랜드 연구소(RAND)의 주요 고객은 미 공군이었는데, 당시 국방장관이었던 찰스 윌슨은 '연구(Research)'나 '수학(Mathematical)'이라는 단어 자체에 병적인 거부반응을 보이며 연구비 지원을 꺼렸습니다. 이에 벨만은 자신이 진행하던 다단계 의사결정 연구를 숨기기 위해 정치인이나 의회에서 결코 트집을 잡을 수 없는 단어를 찾았습니다. 부정적인 뉘앙스로 쓰일 수 없는 단어인 '동적(Dynamic)'과 컴퓨터 연산/계획을 뜻하는 '프로그래밍(Programming)'을 조합해 방패막이용 이름을 만들어낸 것입니다. 이러한 유래와 달리 기술적으로 DP는 문제를 더 작은 하위 문제(Sub-problems)로 쪼개어 해결하는 매우 실용적인 최적화 기법입니다. 일반적으로 $O(2^n)$ 같은 지수 시간이 걸리는 문제를 해결할 때 탁월한 효율을 발휘합니다. 핵심은 '메모이제이션(Memoisation)'으로, 한 번 계산한 작은 문제의 결과를 배열 등에 저장해 두고 다시 필요할 때 재계산 없이 바로 불러와 사용하는 방식입니다. 대표적인 예시로 피보나치 수열을 들 수 있습니다. 단순 재귀 함수로 피보나치 수를 구하면 동일한 연산(예: $F(2)$ 계산)이 트리 구조를 타고 기하급수적으로 중복 호출되지만, DP 방식을 적용해 계산된 값을 메모리에 저장하고 순차적으로 접근하면 불필요한 중복 연산을 획기적으로 줄여 훨씬 빠른 시간 안에 답을 도출할 수 있습니다. 결과적으로 국방장관의 눈을 속이기 위해 급조된 이름이 반세기가 지난 지금까지도 컴퓨터 알고리즘 분야 최고의 핵심 개념 중 하나로 자리 잡게 되었습니다.