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

안녕하세요 ㅎㅎ

    check[y][x] = 1;
    int value = (int)b[y][x] - '0';
    for(int i = 0; i < 4; i++){
        int ny = y + dy[i] * value;
        int nx = x + dx[i] * value;
        ret= max(ret,down(ny,nx) + 1);
    }
    check[y][x] = 0;

지금 코드를 보시면 원복을 하고 있습니다.

즉, a -> b -> c -> d, a -> b -> d -> c

이런 경우의 수를 다 독립적으로 놓고 보는 것이죠.

1로 셋팅된 값이 그 이상의 값으로 셋팅되는 경우의 수는 없을까요? 저렇게 가차없이 바로 return해도 되나 좀 복잡합니다..

-> 네 그렇기 때문에 그 이상의 값으로 셋팅되는 경우의 수도 판단하게 됩니다.

    for(int i = 0; i < 4; i++){
        int ny = y + dy[i] * value;
        int nx = x + dx[i] * value;
        ret= max(ret,down(ny,nx) + 1);
    }

지금 코드를 보시면 모든 경우의 수중에서 -> 타고타고 올라와서 max 값만 저장하게 되죠?

이 떄문에 ret은 지금의 정점에서 다른 정점으로 갈 때의 모든 경우의 수 중에서 max값만을 저장하는것은 자명하게 됩니다.

그러면 한면 디피를 찍어볼까요?

#include <bits/stdc++.h>

using namespace std;
int t,a,d[54][54];
string s; 
char b[54][54];
bool check[54][54];
const int dy[4] = {-1, 0, 1, 0};
const int dx[4] = {0, 1, 0, -1};
bool in(int aa,int bb){
    return(1<=aa && aa<=t && 1<=bb && bb<=a);
}  
int down(int y,int x){
    if(!in(y, x) || b[y][x] == 'H') return 0;
    if(check[y][x]){
        cout << -1 << "\n";
        exit(0);
    } 
    int &ret = d[y][x];
    if(ret) return ret;

    check[y][x] = 1;
    int value = (int)b[y][x] - '0';
    for(int i = 0; i < 4; i++){
        int ny = y + dy[i] * value;
        int nx = x + dx[i] * value;
        ret= max(ret,down(ny,nx) + 1);
    }
    check[y][x] = 0;
    return ret;
}
int main(){
    cin >> t >> a;
    for(int i = 1; i <= t; i++){
        cin >> s;  
        for(int j = 1; j <= a; j++){
            b[i][j] = s[j - 1];
        }
    }
    cout << down(1, 1) << "\n"; 
    for(int i = 1; i <= t; i++){ 
        for(int j = 1; j <= a; j++){ 
            cout << d[i][j] << " ";
        }
        cout << "\n"; 
    }
    
}
/*
3 7
3942178
1234567
91235323

5 1 0 4 0 1 1 
0 0 0 0 0 0 0 
1 0 0 3 1 0 2 
*/

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

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

감사합니다.

강사 큰돌 올림.

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

메모이제이션은 계산된 결과를 저장하여 동일한 계산을 반복하지 않도록 하는 기법입니다. 이것은 특히 동일한 입력 집합에 대해 함수가 여러 번 호출될 가능성이 있는 문제를 해결할 때 유용합니다.

mch473700님이 언급하신 부분은 메모이제이션의 갱신에 대한 문제인데, 이와 관련된 설명을 몇 가지 단계로 정리해 보겠습니다.

1. 메모이제이션의 기본 원리: 메모이제이션은 이미 계산된 결과를 저장하여 같은 입력이 주어질 때 호출을 피하는 것입니다. 이는 시간 복잡도를 줄이고 효율성을 높이는 방법입니다. DP 배열에 저장된 값은 동일한 상태에 대한 최적의 결과를 의미합니다.

2. 갱신과 조건: 새로운 경로가 기존의 값보다 더 나은 결과를 제공할 경우 최신 결과로 갱신할 필요가 있습니다. 이 과정은 다양한 방법으로 이루어질 수 있으며, 그 과정에서의 조건 검사(ret 등)를 통해 이전 값과 새로 계산된 값 중 더 나은 것을 선택합니다.

3. 예시로 이해하기:

   • 만약 어떤 점 (x, y)에 도달할 때의 비용이 다르고 여러 경로를 통해 접할 수 있는 경우, 최솟값 조건을 통해 항상 가장 비용이 적게 드는 경로를 선택합니다.
     
   • 예를 들어, (1, 4)에서 도달했을 때 값이 갱신되어야 하는 상황이라면, 이전에 계산된 값과 새로 계산된 값을 비교하여 더 작은 값을 갱신합니다.
     

4. 구체적인 예제:

   • 피보나치 수열: 피보나치 수열을 계산할 때 중복되는 계산을 줄이기 위해 사용될 수 있습니다. fib(n) = fib(n-1) + fib(n-2)와 같이 계산한다고 할 때, n-1과 n-2의 결과를 저장하면 다시 계산하지 않고 바로 사용할 수 있습니다.
     
   • 최단 경로 문제에서 DP로 갱신하는 경우. 각 지점에서의 최소 비용 경로 값을 저장하고, 다음 지점에서 이 값들 중 최소를 선택하고 더하면서 최적의 값을 찾습니다.
     

mch473700님의 상황에서, 처음에는 최적의 값이 아닌 경우도 있지만 계속 경로를 갱신하면서 더 나은 경로를 찾고 그 결과를 업데이트할 것입니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여, 유사한 답변 링크를 추천해드리고 있습니다. 아래 링크는 다이나믹 프로그래밍과 메모이제이션에 관련된 설명입니다:
- 7 - K 문제 질문입니다.

현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.