-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
7-D 질문드려요 (메모이제이션)
24.04.05 19:27 작성 조회수 99
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
안녕하세요. 강의 잘듣고있습니다.!
메모이제이션 부분이 이해가 잘 안되서 질문드립니다.
dp에 어떤 값이 들어가 있을 때 재귀 호출하지 않고 dp에 담겨져 있는 값을 리턴하는 것에 대한 추가 설명 가능할까요?
#include <bits/stdc++.h>
using namespace std;
int T, W;
vector<int> I;
int mx = 0;
int DP[1001][3][31];
// tree: 트리번호
// cnt: 움직인 횟수
int go(int idx, int tree, int cnt){
int another_tree;
if (tree==1) another_tree =2;
else another_tree =1;
if (idx == T) return 0; // 기저사례
int &ret = DP[idx][tree][cnt]; // 메모이제이션
if (ret) return ret;
if (cnt > 0) ret = max(go(idx+1, another_tree, cnt-1), go(idx+1, tree, cnt)) + (tree == I[idx]? 1:0);
else ret = go(idx+1, tree, cnt) + (tree==I[idx]? 1:0);
return ret;
}
int main(){
cin.tie(NULL);
cout.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> T >> W;
I = vector<int>(T,0);
for(int i =0 ; i < T; ++i){
cin >> I[i];
}
cout << max(go(0, 2, W-1), go(0, 1, W));
return 0;
}
dp에 어떤값이 들어가있다는 것은 이미 한번 수행한 이력이 있는 정점이라는 의미로, 더 이상 아래 정점을 탐구할 필요가 없다 라는 의미겠는데.., 완전히 이해를 하지 못하여 질문드려요
답변을 작성해보세요.
0
큰돌
지식공유자2024.04.06
안녕하세요 ㅎㅎ
dp에 어떤 값이 들어가 있을 때 재귀 호출하지 않고 dp에 담겨져 있는 값을 리턴하는 것에 대한 추가 설명 가능할까요?
>>
일단은 DP를 위해 어떤 것들을 하죠? 크게 5가지라고 보시면 됩니다.
문제를 해결하기 위한 재귀 함수를 정의합니다. 이 함수는 주어진 문제의 상태를 나타내는 매개변수를 받고, 해당 상태에 대한 결과를 계산하여 반환합니다.
결과를 저장할 자료구조를 준비합니다. 이 자료구조(dp 배열 또는 맵 등)는 문제의 상태를 나타내는 매개변수를 키로, 그 상태에 대한 결과값을 값으로 저장합니다. 초기에는 모든 상태가 계산되지 않았다는 것을 나타내는 값(예: -1, 또는 문제범위 제외 등)으로 초기화합니다.
재귀 함수 내에서 해당 상태에 대한 결과가 이미 계산되었는지 확인합니다. 재귀 함수가 호출될 때 마다, 먼저 dp 배열(또는 맵 등)에서 해당 상태에 대한 결과값이 저장되어 있는지 확인합니다. 만약 저장된 결과값이 있다면, 그 값을 바로 반환합니다.
결과가 저장되어 있지 않다면, 문제를 더 작은 문제로 나누어 재귀 호출을 통해 해결합니다. 이 때의 결과를 dp 배열에 저장합니다.
저장된 결과를 반환합니다. 이제 이 상태에 대한 결과는 dp 배열에 저장되어 있으므로, 나중에 같은 상태의 문제를 다시 만나게 되면 재귀 호출 없이 바로 dp 배열에서 결과를 가져와 사용할 수 있습니다.
예를 들어 피보나치를 들어볼까요?
피보나치 수열을 계산하는 문제를 예로 들어 메모이제이션을 설명해 보겠습니다.
피보나치 수열의 n번째 항을 구하는 함수 fib(n)이 있다고 가정합시다. 이 때, fib(n) = fib(n-1) + fib(n-2)라는 점을 이용하여 재귀적으로 문제를 해결할 수 있습니다.
int fib(int n, vector<int>& dp) {
if (n <= 1) return n; // 기본 경우
if (dp[n] != -1) return dp[n]; // 이미 계산된 값이면 재귀 호출 없이 반환
dp[n] = fib(n-1, dp) + fib(n-2, dp); // 결과 계산 후 저장
return dp[n]; // 저장된 결과 반환
}
이 코드에서 dp는 이미 계산된 피보나치 수열의 항들을 저장하는 배열입니다. 함수가 호출될 때, 먼저 dp 배열에서 해당 항이 계산되었는지 확인하고, 계산되지 않았다면 재귀 호출을 통해 계산합니다. 계산된 결과는 dp 배열에 저장되어, 나중에 같은 항을 다시 계산해야 할 때 재귀 호출 없이 바로 결과를 가져올 수 있습니다.
이를 통해 재귀호출을 다시해야할 부분 -> 그냥 계산한 값으로 return 해서 재귀호출을 줄일 수 있는 것이죠.
이해가 되셨을까요?
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
인프런 AI 인턴
2024.04.05
안녕하세요, 인프런 AI 인턴입니다.
윽쓰욱스님의 질문과 관련하여, ‘2240번 자두나무’ 문제에 대한 메모이제이션과 관련된 궁금증을 해결해 드릴 수 있을 것 같습니다. 해당 문제는 다이나믹 프로그래밍을 이용하여 문제 해결 과정에서 메모이제이션을 활용하는 방법을 질문하신 것과 유사한 맥락을 갖고 있습니다.
메모이제이션은 중복된 계산을 피하기 위해 함수의 각 매개변수 조합에 대한 결과를 저장해 두었다가 재사용하는 기법입니다. 이를 통해 프로그램의 성능을 크게 향상시킬 수 있습니다. 답변드릴 내용은 큰돌님의 답변 중 2240번 자두나무 문제와 관련된 내용을 기반으로 합니다.
- 메모이제이션 설명:
int &ret = dp[idx][tree][cnt]; if(~ret) return ret;이 코드 라인에서 먼저ret는dp배열의 특정 위치를 참조합니다. 이 말은,ret에 대한 어떤 수정은 실제dp배열의 해당 위치에도 반영됨을 의미합니다. 여기서 중요한 점은, 이미 값이 계산되어 저장되어 있다면 (즉,ret가 초기값이 아니라면), 그 값을 재사용하여 재귀 호출을 피하고 바로 반환하는 것입니다. 이는 계산 시간을 크게 절약해주는 효과가 있습니다.
if(~ret) 구문은 C++에서 ret가 아직 기본값(-1)이 아닐 경우를 체크합니다. 즉, 이미 값이 계산되어 있다면 해당 값을 반환하고, 그렇지 않을 경우에만 함수의 나머지 부분을 실행합니다.
구체적인 작동 방식:
문제 해결 과정에서 메모이제이션을 활용하면, 이미 탐색한 경로의 결과값을 저장해 두었다가 같은 상황에서는 저장된 결과값을 재활용할 수 있습니다. 이는 특히 반복되는 상황이 많은 동적 계획법(Dynamic Programming)에서 계산 시간을 대폭 줄여줍니다.참조자(
&)의 사용 이유:
참조자를 사용하여dp배열의 값을 참조하는 방식을 채택함으로써, 직접 배열을 수정하고 그 결과를 다시dp배열에 저장하는 과정 없이 결과값을 바로 업데이트할 수 있습니다. 이는 추가적인 메모리 할당을 줄이고, 코드의 실행 속도를 향상시키는 데 기여합니다.관련 질문 링크:
질문 내용과 유사한 문제해결 과정에서 메모이제이션을 적용하는 방법과 그 이유에 대한 설명을 찾으신다면, 위의 링크가 도움이 될 것입니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
답변 2