메모이제이션과 타뷸레이션 비교

순진한 재귀는 같은 작업을 계속 반복합니다. 동적 계획법은 각 답을 한 번만 저장하므로 다시 계산하지 않습니다.

문제가 겹치는 부분 문제로 나뉠 때 동적 계획법을 적용할 수 있습니다. 재귀의 여러 분기에서 같은 작은 문제가 반복해서 나타납니다.

메모이제이션은 재귀에 캐시를 더한 방식입니다. 필요할 때 계산하고, 각 입력을 처음 만났을 때 결과를 저장합니다.

lru_cache 데코레이터는 한 줄만으로 느린 재귀를 빠른 동적 계획법으로 바꾸고 모든 호출을 자동으로 캐시합니다.

테이블화는 가장 작은 문제부터 답까지 표를 채워 가는 방식이며, 재귀 대신 반복문을 사용합니다.

기본값을 설정한 다음 각 칸이 이미 계산된 값들을 읽도록 합니다. 호출 스택 없이 깔끔한 반복문만 사용합니다.

메모이제이션과 테이블화는 같은 점화식을 해결합니다. 차이는 계산 방향뿐입니다. 필요할 때 하향식으로 계산하거나, 순서대로 상향식으로 계산합니다.

점화식을 자연스럽게 작성할 수 있고 모든 상태가 필요하지 않을 수도 있다면 메모이제이션을 사용합니다.

반복문을 빠르게 실행해야 하거나, 재귀 한도 오류를 피해야 하거나, 어차피 전체 표를 계산할 예정이라면 테이블화를 선택합니다.

깊은 메모이제이션 재귀는 파이썬의 재귀 한도에 도달할 수 있으며, 큰 입력에서 실행 시간 오류 판정과 함께 중단될 수 있습니다.

어느 방식을 사용하든 속도 향상의 원천은 각 상태를 한 번만 해결하는 것입니다. 전체 시간은 상태 수에 상태 하나를 처리하는 데 필요한 작업량을 곱한 값입니다.

반복문으로 표를 상향식으로 채우는 방식은 무엇인가요?

이제 부분 문제를 두 가지 방식으로 캐시할 수 있습니다. 메모이제이션은 하향식 재귀를 사용하고, 테이블화는 상향식 반복문을 사용합니다. 더 읽기 쉬운 방식을 선택하면 됩니다. ✨