인프런 영문 브랜드 로고
인프런 영문 브랜드 로고

Inflearn Community Q&A

hyb95791982's profile image
hyb95791982

asked

Learning Algorithm Basics with Python

배낭문제와 동적계획법

Resolved

Written on

·

467

0

안녕하세요!배낭문제와 동적계획법을 풀면서 궁금한점이 있습니다.

앞선 동적계획법 강의에서는 동적계획법이란,

  1. 문제를 해결할 수 있는 재귀 관계식을 구한다
  2. 가장 작은 입력사례로부터 상향식 방법으로 문제를 해결한다

인데,

 

위 재귀 관계식은 그냥 식 사이의 관계로 인해 도출된 것이고 이것을 그대로 옮긴것이 다음의 코드인데,

제가 봤을 때 이 코드는 그냥 재귀적을 문제를 해결하고,

작은 입력사례로부터 Memoization하며 bottom-up하지도 않고 있지도 않고

Top-Down으로 문제를 해결하고 있는데 이것이 왜 동적계획법인지 궁금합니다!

algorithm

Answer 1

0

joonion님의 프로필 이미지
joonion
Instructor

좋은 지적을 해 주셨네요.

이거 원래 메모이제이션으로 구현해야 하는데,

제가 예제 만들다가 메모이제이션을 빼먹은 것 같네요.

재귀 호출의 결과를 배열에 저장하고

배열이 초기값인지 검사하는 메모이제이션 구현으로  변경해야 합니다.

hyb95791982님의 프로필 이미지
hyb95791982
Questioner

아 그렇군요... 알겠습니다!

hyb95791982's profile image
hyb95791982

asked

Ask a question