- 채우는 중
- 읽는 칸
- 답
동적 계획법으로 푸는 피보나치 수
피보나치 수는 동적 계획법의 대표적인 첫 예제입니다. 단순 재귀는 같은 항을 계속 다시 요청하지만, 각 항을 기억하는 표가 있으면 작업량이 n에 비례해서만 늘어납니다. 항을 고르고 상향식이나 하향식을 선택한 다음, 한 단계씩 진행하며 모든 칸이 한 번씩만 채워지는 것을 확인하세요. 재생을 눌러 표가 채워지는 모습을 보거나, 단계와 뒤로로 한 단계씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 구할 항 n과 방법을 고르세요. 상향식은 표를 왼쪽부터 채우고, 하향식은 재귀를 그대로 쓰되 먼저 표를 확인합니다. 이때 표 아래의 줄은 아직 끝나지 않은 호출의 스택입니다. 새 예제는 다른 n을 고릅니다. 보드를 선택한 상태에서 화살표 키는 단계 이동, 스페이스 바는 재생과 일시 정지, Home과 End는 처음과 끝으로 이동합니다.
작동 원리
- n번째 항에 구할 항 n을 입력하고 상향식이나 하향식을 고르세요.
- 재생을 누르거나, 단계와 뒤로로 한 단계씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다.
- 각 칸이 바로 앞 두 칸을 읽는 모습을 지켜보세요. 하향식에서는 표 아래의 줄이 아직 끝나지 않은 호출의 스택입니다.
상향식과 하향식
타뷸레이션이라고도 하는 상향식은 F(0) = 0과 F(1) = 1에서 시작해 표를 왼쪽에서 오른쪽으로 채웁니다. 새 칸은 각각 바로 앞 두 칸의 합입니다. 메모이제이션이라고도 하는 하향식은 재귀 정의를 그대로 씁니다. F(n)을 구하려면 F(n − 1)과 F(n − 2)를 요청합니다. 단순 재귀와 다른 점은, 모든 호출이 먼저 표를 확인하고 칸이 아직 비어 있을 때만 항을 계산한다는 것입니다. 두 방법 모두 모든 칸을 한 번씩 채우고 덧셈을 n − 1번 합니다.
단순 재귀는 왜 이렇게 느릴까
표가 없으면 F(n)은 F(n − 1)과 F(n − 2)를 호출하고, 그 둘은 모두 F(n − 3)을 호출하는 식으로 계속됩니다. 호출은 같은 항이 계속 반복해서 나타나는 트리를 이룹니다. 호출 수는 2·F(n + 1) − 1로, 피보나치 수 자체만큼 빠르게 늘어납니다. F(10)은 177번, F(20)은 21,891번, F(40)은 3억 3100만 번이 넘습니다. 바로 이런 중복 부분 문제를 위해 동적 계획법이 있습니다.
자주 묻는 질문
동적 계획법이란 무엇인가요?
문제를 서로 겹치는 더 작은 문제로 나누고, 작은 문제를 각각 한 번만 풀어 그 답을 표에 저장하며 푸는 방법입니다. 피보나치 수가 가장 간단한 예입니다. 모든 항이 바로 앞의 두 항으로 만들어집니다.
메모이제이션과 타뷸레이션은 어떻게 다른가요?
메모이제이션은 재귀 코드를 그대로 두고, 답을 처음 계산할 때 저장해 두어 나중의 호출은 읽기만 합니다. 타뷸레이션은 각 칸에 필요한 답이 반드시 먼저 준비되는 순서로 표를 채웁니다. 둘 다 덧셈은 똑같이 합니다. 타뷸레이션은 호출 스택이 필요 없고, 메모이제이션은 실제로 필요한 칸만 계산합니다.
F(n)에는 덧셈이 몇 번 필요한가요?
표를 쓰면 n − 1번입니다. F(2)부터 F(n)까지 항마다 한 번씩입니다. 항상 마지막 두 항만 읽으므로, 프로그램은 표 전체 대신 수 두 개만 저장해도 됩니다.
앱은 왜 n = 40까지만 되나요?
F(40) = 102,334,155는 아직 화면에 쉽게 들어가고, 단순 재귀는 이 값을 구하는 데 벌써 331,160,281번 호출해야 합니다. 그보다 큰 항은 빠르게 커집니다. JavaScript 숫자로 정확히 담을 수 있는 가장 큰 항은 F(78)입니다.
어딘가로 데이터가 전송되나요?
아니요. 모든 계산은 브라우저 안에서 이루어지며, 마지막 설정은 이 브라우저의 로컬 저장소에 남습니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
편집기로 이동