인프런 커뮤니티 질문&답변
작성한 질문수
DP 풀이방법에 있어 탑바텀, 바텀업 풀이 방식의 선택 방식
작성
·
224
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
안녕하세요 ^^
강의 너무 잘 듣고 있습니다.
DP 문제를 풀다보면..,
시작하기 전에 해당 문제를 바텀업으로 풀어야할지, 탑바텀으로 풀어야할지 어떻게 결정할 수 있을까요?
제 느낌은 바텀업풀이가 점화식을 유도할 수 있다면 코드 자체가 간단하여(재귀호출x) 구현 난이도가 쉬운데, 점화식을 생각하는 과정이 경우에 따라 매우 어려운것 같습니다.
탑바텀 풀이는 완전탐색과 동일한 상태에서 메모이제이션 을 잘 정의함으로써 문제를 풀 수 있는데, DP배열의 상태정의를 어떻게 하느냐에 따라, 테스트케이스는 맞지만 제출시 틀리는 결과가 나오는 경우가 종종있습니다 (구현에서 실수 잦음)
어떤 식으로 DP의 풀이를 결정하고 문제를 들어가는지 질문드려요.
감사합니다.!!
답변 2
0
안녕하세요 윽쓰님 ㅎㅎ
제 느낌은 바텀업풀이가 점화식을 유도할 수 있다면 코드 자체가 간단하여(재귀호출x) 구현 난이도가 쉬운데, 점화식을 생각하는 과정이 경우에 따라 매우 어려운것 같습니다.
>>
사실 어떤 경우에는 탑버텀을 써야 한다. 이런 것은 없습니다. 탑버텀으로 풀 수 있는 문제는 바텀업으로도 풀 수 있습니다. 구현하기 쉬운 쪽은 = 탑버텀입니다. 근데 이것도 개인차가 있는 거 같아요. 저는 탑버텀이 쉽긴한데 다른 분은 또 바텀업이 쉽다고 하거든요.
먼저 점화식을 짜고 -> 풀이를 만드는게 맞습니다. 바텀업이든 탑바텀이든.
효율성을 따지면...
sparse하게 데이터가 분포된 경우 탑다운 방식이 유리할 수 있으며, 특정 조건에서는 바텀업 방식이 더 효율적일 수 있습니다. 하지만 보통은 반복적 - for문을 쓰는 바텀업이 더 효율적이긴 합니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
안녕하세요, 인프런 AI 인턴입니다.
윽쓰욱스님의 질문은 다이나믹 프로그래밍(DP) 문제를 접근할 때 탑다운(Top-down) 방식과 바텀업(Bottom-up) 방식 중 어떤 방식을 선택해야 하는지에 대한 고민으로 해석됩니다. 이와 관련하여, 큰돌님의 답변을 참조할 수 있는 링크를 제공드리겠습니다. 해당 답변은 DP 문제를 접근할 때 탑다운과 바텀업 방식 선택에 대한 고민을 해소할 수 있는 유용한 정보를 담고 있습니다.
- dp 관련 질문드립니다: 이 링크에서 큰돌님은 일반적으로 DP 문제는 탑다운 방식과 바텀업 방식 모두 사용 가능하다고 언급합니다. 단, sparse하게 데이터가 분포된 경우 탑다운 방식이 유리할 수 있으며, 특정 조건에서는 바텀업 방식이 더 효율적일 수 있음을 설명합니다. 특히, 문제를 접근할 때 구현의 용이성, 메모리 사용량, 실행 시간 등을 고려하여 방식을 선택하는 것이 좋다고 조언합니다.
이 답변은 DP 문제를 효과적으로 접근하기 위해 필요한 기본적인 지식과 더불어, 탑다운과 바텀업에 따른 실행 속도와 메모리 사용량의 차이를 고려하여 문제유형에 맞는 방식을 선택할 수 있는 방법을 제공합니다. DP 문제에 접근할 때, 특정 상황에서 더 유리한 방식을 선택하는 것이 중요하며, 이는 문제의 성격과 요구하는 해결책에 따라 달라진다는 점을 강조합니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.