인프런 커뮤니티 질문&답변
작성한 질문수
탑다운 재귀 방식 - 초기화 값(INF vs. -1)
해결된 질문
작성
·
44
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
안녕하세요 항상 좋은 강의 감사드립니다!
해당 문제를 풀면서 생겼던 문제 관련해서 문의드리고자 합니다.
제가 처음 풀었던 방식은 기존 탑다운 방식과 유사하게 (초기메롱) 방식으로 풀이를 진행하였으나 아래와 같이 시간 초과가 떴습니다.
https://www.acmicpc.net/submit/2294/97783160
이로 인해 재귀 방식으로 인한 시간초과인가? 바텀업 방식을 써야되구나라고 생각은 하였으나 아래와 같이 초기값을 -1로 초기화하고 진행하였을 때는 바텀업(반복문)방식보다는 조금 느렸지만 통과하였습니다.
https://www.acmicpc.net/submit/2294/97784123
두 코드의 차이가 어디서 발생하는지 와닿지 않아 이렇게 문의드립니다.
감사합니다!
답변 4
0
안녕하세요 우영님 ㅎㅎ
먼저 코드공유하는 방법은 질문하는 방법 - 강의 참고부탁드립니다.
계속해서 안보이네요 ㅠㅠ
이거의 차이는 캐싱이 되는가 안되는가의 차이입니다.
첫 코드:
dp를 -1로 초기화하고,if (ret != -1) return ret;
→ret가 가능한 값이든INF(불가능)이든 한 번 계산된 값은 그대로 캐싱되어 다시 계산하지 않습니다.둘째 코드:
dp를 INF로 초기화하고,if (ret != INF) return ret;
→INF가 아직 미계산과 계산했더니 불가능이면 INF가 되겠죠?
→ 어떤 금액이 정말로 불가능해서ret가INF로 남아 있어도, 다음 호출에서if (ret != INF)가 거짓이라 메모이제이션이 불가능합니다. 그래서 다시 -> 매번 재귀로 같은 부분문제를 다시 풀게 되어 시간 초과가 납니다.
즉, 둘째 코드에서는 불가능 상태가 캐싱되지 않는 차이점이 있습니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
[시간초과:INF 초기화]
https://www.acmicpc.net/submit/2294/97812363
[-1: 초기화]
https://www.acmicpc.net/submit/2294/97812392
링크 다시 드립니다!
0
혹시 몰라 직접 코드 첨부드립니다!
[INF 초기화: 시간초과]
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 987654321;
int n,k;
int dp[100004];
int value[104];
int go(int won){
if(won==0) return 0;
if(won <0) return INF;
int &ret = dp[won];
if(ret!=INF) return ret;
for(int i=0;i<n;i++){
ret=min(ret,go(won-value[i])+1);
}
return ret;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k;
for(int i=0;i<n;i++){
cin>>value[i];
}
// memset(dp, INF, sizeof(dp));
fill(dp, dp+k+1, INF);
int ans = go(k);
if(ans==INF) ans = -1;
cout << ans <<'\n';
return 0;
}
[-1 초기화]
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 987654321;
int n,k;
int dp[100004];
int value[104];
int go(int won){
if(won==0) return 0;
if(won <0) return INF;
int &ret = dp[won];
if(ret!=-1) return ret;
ret = INF;
for(int i=0;i<n;i++){
ret=min(ret,go(won-value[i])+1);
}
return ret;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k;
for(int i=0;i<n;i++){
cin>>value[i];
}
// memset(dp, INF, sizeof(dp));
fill(dp, dp+k+1, -1);
int ans = go(k);
if(ans==INF) ans = -1;
cout << ans <<'\n';
return 0;
}
0
안녕하세요, 인프런 AI 인턴입니다.
김우영님의 질문에 대한 답변을 드리겠습니다. 김우영님이 경험하신 문제는 동적 계획법(dynamic programming, dp) 초기화 방식과 관련이 있을 가능성이 큽니다. 두 코드 사이의 주요 차이점은 아마도 초기화 값 설정과 그로 인한 dp 배열의 처리 과정에 있을 것으로 보입니다.
동적 계획법 초기화 전략
INF 값 사용: INF 값을 사용하여 초기화하는 경우, 이는 일반적으로 최솟값을 구하는 문제에서 유용합니다. 모든 값을 업데이트할 수 있도록 매우 큰 값으로 dp를 설정합니다. 하지만, 재귀적으로 값을 계산할 때는 쓸데없는 계산을 방지하기 위해 INF와 함께 초기화된 값을 비교할 필요가 있습니다.
-1 값 사용: -1로 초기화하는 경우, -1은 보통 아직 방문하지 않았음을 나타냅니다. 이 방식은 특정 상태를 방문했는지 안 했는지 빠르게 판단할 수 있어서, 재귀적인 dp에서 자주 사용됩니다. 이는 초기화 값에 특별히 종속적이지 않은 모든 값에 대해서만 업데이트를 하기 때문에, 필요하지 않은 호출들을 피할 수 있습니다.
재귀와 반복문 구현의 차이
재귀 방식 (탑다운): 재귀 방식은 메모리 및 호출 스택 문제로 인해 시간이 많이 걸릴 수 있습니다. 불필요한 재귀 호출을 줄이기 위해서는 초기화와 함께 이전에 계산된 값을 잘 활용해야 합니다.
반복문 방식 (바텀업): 반복문 방식은 모든 상태를 미리 계산해 두기 때문에 비교적 안정적이며 효율적으로 작동할 가능성이 높습니다. 특히 dp 배열을 순서대로 채우기 때문에 상태전이 또한 명확합니다.
추천하는 참조 링크
기존 수강생들의 질문과 답변에서 유사한 문제를 다루고 있습니다. 이러한 질문들이 도움이 될 수 있을 것입니다:
- 7-A dp초기화값 관련 시간초과 질문에서, 초기화 값이 프로그램의 실행 시간에 미치는 영향에 대한 설명이 있으며 이는 현재 질문과 유사한 부분이 있습니다.
초기화 값 설정이 문제마다 다른 성능을 발휘할 수도 있으니, 문제에 맞게 적절한 초기화 값을 사용하는 것이 중요합니다. -1 초기화가 재귀 호출 최적화에 도움을 준 사례를 참고하시면 도움이 될 것입니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
[시간초과:INF 초기화]
https://www.acmicpc.net/submit/2294/97812363
[-1: 초기화]
https://www.acmicpc.net/submit/2294/97812392
링크 다시 드립니다!