7-E 수업질문

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

7-E

해결된 질문

작성

239

안녕하세요 큰돌 선생님 좋은강의 항상 감사합니다.

dp문제를 계속 풀고있는데, 아직까지 문제를 처음 보았을때 메모이제이션을 어떻게 걸어야 하는지, 무슨값을 반환해야하는지 등에 대해서 많이 헷갈려서 질문드립니다.

해당 7-E번 문제를 그냥 완탐으로는 풀 수 있겠는데 어떻게 메모이제이션을 해야하는지 잘 모르겠습니다. '메모이제이션을 건다' 의 정확한 의미가 무엇인가요?

또한 그냥 완탐으로 풀었을때 시간복잡도가 너무 크면 메모이제이션을 걸어서 시간복잡도를 줄인다는 큰 틀은 알겠는데, 좀더 자세한 생각의 흐름이 궁금합니다. 어떤 매개변수를 dp배열의 인자로 가져야 하는지 등이 헷갈립니다.

다음 아래는 해당 문제를 완탐으로 푼 코드입니다. 이렇게 완탐으로는 해결하겠는데 그 다음 이 코드에 메모이제이션을 적용하는 세세하고 자세한 흐름이 궁금합니다.

#include <bits/stdc++.h>
using namespace std;

int N, ret;

void go(int whole, int not_whole) {
    if (whole == 0 && not_whole == 0) {
        ret++;
        return;
    }
    if (whole > 0) go(whole - 1, not_whole + 1);
    if (not_whole > 0) go(whole, not_whole - 1);
}

int main() {
    cin >> N;
    go(N, 0);
    cout << ret << '\n';
    return 0;
}

c++코딩-테스트

답변 1

큰돌

지식공유자

안녕하세요 명운님 ㅎㅎ

>> 보통은 함수의 매개변수가 DP배열의 인자가 됩니다.

문제를 풀 때 경우의 수에 핵심적인 변수를 뽑아서 DP배열을 만드시면 되는데요.

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];
    ll &ret = dp[whole][not_whole]; 
    if(whole > 0) ret += go(whole - 1, not_whole + 1); 
    if(not_whole > 0) ret += go(whole, not_whole - 1);
    return ret;   
}

이 문제 같은 경우 알약 한알짜리. 반알짜리의 갯수가 중요합니다.

{1개, 1개}

라는 상태값을 기준으로 W이며 H라는 문자열 등이 결정되고 경우의 수에 영향을 미치는 상태값이기 때문입니다.

예를 들어 반알짜리가 0개라면 아예 H라는 문자열을 만들 수 없겠죠?

이렇듯.

어떠한 경우의 수에 있어서 연관이 되어있는 변수를 설정해서 배열로 만드시면 됩니다.

메모이제이션에 대해 설명하자면.

DP[2][2] = DP[1][3] + DP[2][1] 로 예로 들면요.

한알짜리 2개 + 반알짜리 2개로 만들 수 있는 경우의 수는. DP[2][2]

그 때 당시 한알을 먹어 반알짜리로 만드는 경우의 수. DP[1][3]

반알을 먹어 만드는 경우의 수를. DP[2][1]

더한 값이 되는 것은 자명합니다. (이 경우의 수밖에 존재하지 않으니까요.)

그리고...

DP[1][3], DP[2][1]

는 또 이러한 것들을 반복해서 쌓여져 만든 배열이 되겠지요?

이렇게 배열들의 값이 차곡차곡쌓여서 DP[2][2]가 되는 것입니다.

플로우를 정리하자면 다음과 같습니다.

경우의 수가 뭔지를 파악.
경우의 수에 연관되어있는 변수를 설정한다.
해당 변수를 배열이나 맵 등에 담을 수 있는지 없는지를 파악한다.
메모이제이션

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

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

감사합니다.

강사 큰돌 올림.

이명운

질문자

답변 감사합니다 지문속 값을 넣어서 다시 설명해주시니 이해가 됩니다.

더욱 노력하겠습니다!

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

7-E 수업질문