디피 질문 드립니다. 탑다운의 경우 어느정도까지 재귀 호출이 허용 되는지
큰돌님 안녕하세요?
제가 디피 문제를 풀 때 탑다운으로 풀까 바텀업으로 풀까 고민하는데, 탑다운으로 풀 때 스택 오버플로우 난 경우가 있어 질문 드리게 되었습니다.
어디선가 말씀해주셨을거 같은데 제가 못찾아서.. 양해말씀을 드리고..
디피 탑다운 혹은 재귀 호출을 사용하는 코드에서 재귀호출 댑스? 몇회까지 호출이 되는지 공유해 주실 수 있을까요?
(천번이었나.. 기억이 안나서..)
답변 미리 감사합니다 :)
답변 2
0
안녕하세요 ㅎㅎ
다운으로 풀 때 스택 오버플로우 난 경우가 있어
-> 어떤 코드인지 공유부탁드립니다.
디피 탑다운 혹은 재귀 호출을 사용하는 코드에서 재귀호출 댑스? 몇회까지 호출이 되는지 공유해 주실 수 있을까요?
(천번이었나.. 기억이 안나서..)
-> 음.. DP는 어차피 메모이제이션이 되기 때문에... 몇회가 중요하지 않습니다. 제가 몇번까지 된다 라고 얘기한 적은 없는 것 같습니다. ㅎㅎ
감사합니다.
0
안녕하세요, 인프런 AI 인턴입니다.
mhyim님께서 질문하신 내용은 DP의 탑다운 방식을 사용할 때 재귀 호출의 깊이가 어느 정도까지 허용되는지에 관한 것입니다. 이와 관련하여, 일반적으로 C++에서는 스택 메모리 제한이 존재하기 때문에 재귀 호출의 깊이가 깊어지면 스택 오버플로우가 발생할 수 있습니다.
일반적으로, C++의 기본적인 스택 메모리 제한은 약 1MB이며, 이는 재귀 호출의 깊이로는 보통 수천 번 정도의 호출을 감당할 수 있음을 의미합니다. 그러나, 이 숫자는 사용하는 컴퓨터의 환경이나 설정에 따라 달라질 수 있습니다. 만약 재귀 호출이 깊어질 가능성이 있다면, 이러한 환경적 제약을 고려하여 바텀업 방식을 사용하거나, 재귀를 반복문으로 대체하는 것도 좋은 방법입니다.
이에 대해 더 자세한 토론과 예시를 확인하시려면 다음의 유사한 질문들을 참고하시면 좋습니다:
탑다운dp와 버텀up dp에 대한 설명을 좀 더 알 수 있을까요?: 이 게시물에서는 탑다운 및 바텀업 방식에 대한 설명과 함께, 각 방식의 장단점 및 효율성에 대해 논의하고 있습니다. 특히 재귀 호출이 가지는 한계점에 대해 참고할 만한 내용이 있습니다.
DP 풀이방법에 있어 탑바텀, 바텀업 풀이 방식의 선택 방식: 이 링크에서 배우실 수 있듯이, 탑다운 방식의 한계와 함께 바텀업 방식을 선택하기 위한 기준에 대해서도 설명하고 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
2-I) 왜 이 문제가 그래프이론 카테고리에 있는지 잘 모르겠습니다.
0
26
2
2주차 개념#12 트리 순회
0
20
2
백준사이트가 종료된다고 합니다.
0
244
2
백준 서비스 종료
9
776
1
sk 하이닉스 코테 대비
0
359
2
3-G 최댓값 질문
0
50
1
모듈러 연산 값이 10이 아닌 경우도 있지 않나요?
0
82
2
3-I 코드 질문드립니다.
0
62
2
3-N 질문 있습니다.
0
66
2
학습방법
0
100
2
4-H 질문 있습니다 (코드 리뷰)
0
66
2
코딩테스트 어디까지 준비해야 하는지 질문이 있습니다.
0
166
2
2-O 반례가 무엇일지 어떤 부분이 틀렸는지 잘 모르겠습니다.
0
69
2
2주차 개념 #4-2. 인접행렬 질문있습니다.
0
64
2
1-A 문제풀이 후 궁금한 점이 생겨서 질문드립니다.
0
49
2
조합 재귀 풀이 확인 해주시면 감사하겠습니다.
0
67
2
함수별 시간복잡도
0
72
2
3-h 질문입니다.
0
49
1
안녕하세요 선생님. 시간 복잡도 4번 질문있습니다.
0
52
2
1-I 문제 질문 드립니다.
0
76
2
2-P 질문입니다.
0
56
1
mac에서 시작하기 관련
0
88
2
5-Q 질문
0
63
2
풀이 코드 질문
0
64
2