인프런 커뮤니티 질문&답변

안녕하세요 ㅎㅎ

큰돌님 해설에는 조금 다르게 되어 있는 것 같아서요

>>

ret을 선언했으면 그걸 쓰는게 더 맞는 코드입니다.

물론 의미상 틀린부분은 아니지만

해당 부분은 다음과 같이 바꿨습니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, dp[31][31];
ll go(int whole, int not_whole){
    if(whole == 0 && not_whole == 0) return 1;  
    ll &ret = dp[whole][not_whole]; 
    if(ret) return ret;
    if(whole > 0) ret += go(whole - 1, not_whole + 1); 
    if(not_whole > 0) ret += go(whole, not_whole - 1);
    return ret;   
}
int main(){ 
    while(true){
        cin >> n; if(n == 0)break; 
        cout << go(n, 0) << "\n";
    }
    return 0;
}

이렇게 변경되었습니다. (해당 부분은 오늘내로 수정될 예정입니다.)

사실 근데 ret을 안써도 됩니다.

ret은 그저 dp 라는 배열 자체가 길기 때문에 ret을 담는 하나의 임시 변수라고 보시면 됩니다.

즉, 이렇게 해도 맞다고 뜹니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, dp[31][31];
ll go(int whole, int not_whole){
    if(whole == 0 && not_whole == 0) return 1;   
    if(dp[whole][not_whole]) return dp[whole][not_whole];
    if(whole > 0) dp[whole][not_whole] += go(whole - 1, not_whole + 1); 
    if(not_whole > 0) dp[whole][not_whole] += go(whole, not_whole - 1);
    return dp[whole][not_whole];   
}
int main(){ 
    while(true){
        cin >> n; if(n == 0)break; 
        cout << go(n, 0) << "\n";
    }
    return 0;
}

Q2. 아래 두 코드는 사실상 의미가 같은건가요?

네 같습니다.

Q3. 강의 1분 54에서도 "dp가 있으면 그냥 dp를 반환한다"고 설명해주셨는데 위 질문과 관련이 있을까요?

>> DP에 값이 있다. = 해당부분을 앞서서 방문했다. 즉, 메모이제이션이 가능한 상태.

DP를 바로 반환한다. = 해당 부분을 다시 방문하지 않고 미리 방문해놓은 값을 기반으로 리턴한다 = 메모이제이션

다시 말하면,

이는 이미 배열에 계산된 하위 문제의 결과가 있을 경우, 그 값을 그대로 반환한다는 의미입니다. 즉, 불필요한 중복 계산을 피하기 위한 조건문이며 이렇게 함으로써 동일한 하위 문제를 여러 번 계산하는 것을 방지할 수 있습니다.

ex) 피보나치입니다. 주석달았습니다. 참고부탁드립니다.

#include <bits/stdc++.h>
using namespace std; 
vector<int> memo;
int fibonacci(int n) {
    // 이미 계산된 값이 있으면 반환 : 메모이제이션
    if (memo[n] != -1) {
        return memo[n];
    }
    // 기저 사례: n이 0이나 1일 때 그 값을 반환
    if (n <= 1) {
        memo[n] = n;
        return n;
    }
    // 값을 계산하고 메모에 저장
    memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
    return memo[n];
}

int main() {
    int n = 10;  // 계산할 피보나치 수열의 인덱스
    memo.resize(n + 1, -1);  // 메모 벡터를 -1로 초기화
    cout << "Fibonacci(" << n << ") = " << fibonacci(n);
    return 0;
}

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

안녕하세요, 인프런 AI 인턴입니다, mhyim님.

제공된 정보와 질문을 바탕으로, 메모이제이션과 관련된 궁금증을 해결해 드릴 수 있는 유사한 논의를 찾았습니다.

mhyim님께서 주신 질문은 메모이제이션 시 ret와 dp 지역변수를 활용하는 방식의 차이점에 대한 것으로 해석됩니다. 여기서 ret를 사용하는 이유와, 이것이 메모이제이션에서 어떻게 작동하는지에 대한 이해를 돕고자 관련 답변을 참고할 것을 권장드립니다.

7-E 수업질문에서 큰돌님은 메모이제이션을 활용할 때, 베이스 케이스 혹은 재귀 호출을 통해 계산된 값을 dp 배열에 저장하는 방식을 설명하셨습니다. 이때, 이 방법론은 특정 매개변수 조합에 대한 결과값을 재계산하는 것을 피함으로써 시간 효율성을 높이는데 목적이 있습니다.

질문에서 언급된 &ret = dp[F][H]; (ret !=0) return ret;와 if(dp[whole][not_whole]) return dp[whole][not_whole]; &ret = dp[whole][not_whole]; 두 코드 조각은 핵심적으로 메모이제이션의 구현 방식에 있어서 의미가 유사합니다. 주 차이점은 ret를 참조자로 사용하여 dp 배열 값을 간접적으로 업데이트하고, dp 배열 값이 이미 존재할 경우 즉, 0이 아닐 경우 해당 값을 재활용하여 직접 반환한다는 점입니다.

좀 더 구체적으로는, 첫 번째 코드가 ret 참조자를 통해 dp배열의 값을 업데이트하는 방식을 사용하는 반면, 두 번째 코드는 dp 배열에 직접 접근하여 동일한 작업을 수행한다는 점에서 차이가 있습니다. 이러한 차이는 주로 가독성 또는 개발자의 선호도에 따라 다를 수 있으나, 핵심적으로는 동일한 목적을 가진 메모이제이션 기법의 구현일 뿐입니다.

“dp가 있으면 그냥 dp를 반환한다”는 말은, 특정 매개변수 상태에 대해서 이미 계산된 결과값이 dp 배열에 저장되어 있다면, 재계산을 하지 않고 저장된 값을 재활용한다는 의미입니다. 이 방식은 중복 계산을 방지하여 알고리즘의 실행 시간을 단축시키는 데 중요한 역할을 합니다.

질문 내용에 대한 더 자세한 설명을 원하실 경우, 직접 해당 7-E 수업질문 링크를 통해 큰돌 님의 답변을 확인하시는 것도 좋은 방법입니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.

현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏

추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.