동적계획법 (3) 문제로 배우는 DP
탑다운 방식인데 위에 그림처럼 바텀업처럼 문제를 아래서 부터 해결해 나가서요.
강의에서는 피보나치가 탑다운 방식으로 푸는 경우가 있는데 바텀업 방식처럼 문제를 아래서(위에 그림 빨간색표시처럼) 부터 해결한다고 하셨는데요.
혹시 계단 문제도 피보나치처럼 탑다운 방식인데 문제를 아래서 부터 해결해나가는 스타일인건가요?
문제를 읽고 탑다운으로 풀지 바텀업으로 풀지 어떻게 알아요?
답변 1
0
안녕하세요 zzzzz님
강의에서 해당 문제를 탑다운과 바텀업 방식 두 가지로 풀이를 해드렸는데요.
결국에는 DP문제는 탑다운과 바텀업 두 가지 방법으로 다 풀 수 있습니다.
하지만 문제를 딱 봤을 때 바텀업으로 처음 접근할지, 아니면 탑다운으로 접근할 지 정해야 하는데, 이게 사람마다 다르고 상황마다 다르고 문제마다 다르더라고요.
저는 사실 탑다운 방식이 편한 문제를 어떤 사람은 바텀업이 자연스럽다고 느끼고, 평소의 저는 탑다운이 편하지만 어떤 문제는 바텀업이 편한 경우가 또 있더라고요.
정확하게 나누기는 어려운 것 같아요. 같은 문제도 사람마다 다르게 접근방법이 떠오르기 마련이니까요.
그래서 문제를 딱 봤을 때 탑다운으로 풀지 바텀업으로 풀지 정할정도가 되려면 DP문제를 많이 풀어보면서 두 가지 방식으로 다 풀어봐야 조금씩 감이 잡히는 것 같습니다.
다른 알고리즘의 경우에는 문제를 읽고 어느정도 감이 올 수 있는데, DP는 점화식을 생각해 내야되는 부분이 굉장히 큰데 그건 문제마다 너무 다르고 아이디어를 떠올리는 측면이 좀 강해서 결국 똑똑한사람(또는 연습이 많이 된 사람)이 유리한 부분입니다. 요령이 잘 없어요. 그래서 DP 문제를 항상 바텀업으로 풀었으면 탑다운으로도 푸는 연습을 하면 좋습니다.
노션 공유 링크
0
87
2
수업 중간에 내주신 문제는 해답을 알 수 없는걸까요?
0
77
2
최신 강의와 비교
0
85
2
Min Cost Climbing stairs 질문
0
76
2
노션 공유 부탁드립니다!
1
88
2
for 문에 sort 함수 를 사용하면
1
90
2
노션 공유 부탁드립니다.
0
104
2
디스코드가 올바르지 않다고 뜹니다..!
0
107
1
그래프
0
98
2
노션 공유
1
123
2
시간복잡도 질문
2
125
3
11강 질문
1
78
2
노션 공유 부탁드립니다
0
84
2
linkedList - BrowserHistory 코드 질문
0
76
1
list1.append(list2)와 list1.append(list2[:])의 차이가 무엇인가요?
1
168
1
라이브러리 사용
1
136
2
문제 교재는 따로 없는 거 맞나요?
1
202
2
LCA 관련해서 질문이 있습니다.
1
118
2
[Unique Paths] 완전탐색 / DP (후반부)
0
108
1
dp 계단오르기최소비용질문입니다.
0
109
1
Dynamic Array 의 size 정보가 저장되는 곳
2
161
2
노션공유가 안된듯 합니다
1
163
2
[코테 적용] 👉 [3번 문제] 완전탐색 (DFS, BFS) (전반부)
1
122
1
강의자료 만들 때 사용하신 프로그램이 뭘까요?
1
203
1