• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    해결됨

동적계획법 (3) 문제로 배우는 DP

24.03.03 02:01 작성 조회수 96

1

탑다운 질문.png탑다운 방식인데 위에 그림처럼 바텀업처럼 문제를 아래서 부터 해결해 나가서요.

강의에서는 피보나치가 탑다운 방식으로 푸는 경우가 있는데 바텀업 방식처럼 문제를 아래서(위에 그림 빨간색표시처럼) 부터 해결한다고 하셨는데요.

혹시 계단 문제도 피보나치처럼 탑다운 방식인데 문제를 아래서 부터 해결해나가는 스타일인건가요?

문제를 읽고 탑다운으로 풀지 바텀업으로 풀지 어떻게 알아요?

답변 1

답변을 작성해보세요.

0

안녕하세요 zzzzz님

 

강의에서 해당 문제를 탑다운과 바텀업 방식 두 가지로 풀이를 해드렸는데요.

결국에는 DP문제는 탑다운과 바텀업 두 가지 방법으로 다 풀 수 있습니다.

 

하지만 문제를 딱 봤을 때 바텀업으로 처음 접근할지, 아니면 탑다운으로 접근할 지 정해야 하는데, 이게 사람마다 다르고 상황마다 다르고 문제마다 다르더라고요.

 

저는 사실 탑다운 방식이 편한 문제를 어떤 사람은 바텀업이 자연스럽다고 느끼고, 평소의 저는 탑다운이 편하지만 어떤 문제는 바텀업이 편한 경우가 또 있더라고요.

 

정확하게 나누기는 어려운 것 같아요. 같은 문제도 사람마다 다르게 접근방법이 떠오르기 마련이니까요.

그래서 문제를 딱 봤을 때 탑다운으로 풀지 바텀업으로 풀지 정할정도가 되려면 DP문제를 많이 풀어보면서 두 가지 방식으로 다 풀어봐야 조금씩 감이 잡히는 것 같습니다.

 

다른 알고리즘의 경우에는 문제를 읽고 어느정도 감이 올 수 있는데, DP는 점화식을 생각해 내야되는 부분이 굉장히 큰데 그건 문제마다 너무 다르고 아이디어를 떠올리는 측면이 좀 강해서 결국 똑똑한사람(또는 연습이 많이 된 사람)이 유리한 부분입니다. 요령이 잘 없어요. 그래서 DP 문제를 항상 바텀업으로 풀었으면 탑다운으로도 푸는 연습을 하면 좋습니다.