7-V 질문있습니다 :)

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

7-V

해결된 질문

작성

안녕하세요 선생님 🙂

한 가지 이해가 되지 않는 부분이 있어서 질문 드립니다.

이 코드에서 int& result = dp[here][_time] 이라는 코드는, 항상 result = 0이라는 것을 의미합니다. 그렇기 때문에 굳이 dp라는 배열이 필요한 것인지에 대한 의문이 생겨 아래의 테스트를 해보았습니다.

int result = 0이라고 한다면, 레퍼런스 값이 아닌 복사본을 사용하기 때문에 시간초과가 되어 2번 서브태스크가 오답처리됩니다.

그렇다면, 전역에 int a = 0이라는 변수를 선언한 후에 go함수에 int& result = a라고 하는 것도 괜찮은 방법일 것이라 생각하였지만 오답처리가 됩니다.

dp배열의 값은 항상 0인데 굳이 dp를 사용해야 할까요?
int a = 0, int& result = a; 를 해도 괜찮은 방법일거라 생각했지만 완전히 다른 값이 나옵니다. 혹시 제가 놓치고 있는 개념이 따로 있는지 궁금합니다.

c++코딩-테스트

답변 2

큰돌

지식공유자

안녕하세요 유태님 ㅎㅎ

int& result = dp[here][_time] 이라는 코드는, 항상 result = 0이라는 것을 의미합니다

-> 항상은 아닙니다. 다른 값이 할당이 됩니다.

    int &ret = dp[here][_time]; 
    if(ret) return ret; 
    ret = -1e6;
    if(_time - a[here]._time >= 0)ret = max(ret, go(here + 1, _time - a[here]._time) + a[here].pay); 
    if(_time - b[here]._time >= 0)ret = max(ret, go(here + 1, _time - b[here]._time) + b[here].pay);

이 코드의 핵심은 here, time이라는 상태값을 기반으로 어떠한 값을 메모이제이션 -> 배열에 저장해놓고 -> 이를 재사용한다라는 것입니다.

int a = 0, int& result = a; 를 해도 괜찮은 방법일거라 생각했지만

-> 일단은 배열이든 다른 자료구조이든 2개의 상태값을 담을 수 있는 자료구조를 사용해야 합니다. 2차원좌표를 담는다 -> 무조건 y, x 2 개의 축이 필요하고 -> 2차원 배열이 필요하죠? 이것을 생각하시면 됩니다.

감사합니다.

인프런 AI 인턴

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

질문의 요지에 대해 기존의 유사한 질문과 답변을 참고하면 도움이 될 수 있을 것 같습니다. 특히, 동적인 프로그래밍(dp) 배열의 초기화와 사용법에 관한 질문들이 관련이 있습니다.

dp 배열의 사용 이유:
dp 배열을 사용하는 이유는 중복되는 부분 문제들을 저장하여 다시 계산하지 않기 위함입니다. 이 과정에서 메모이제이션을 통해 시간 복잡도를 줄여 보다 효율적인 알고리즘을 구현할 수 있습니다.
레퍼런스의 사용:
레퍼런스를 사용하는 주된 이유는 복사본을 만들지 않고 바로 원본을 수정하기 위해서입니다. int& result = dp[here][_time]와 같이 사용하면 dp[here][_time] 값을 수정하면서도 해당 값을 바로 접근해 사용할 수 있습니다.

아래 링크들은 유사한 질문에 대한 답변이므로 참고하시면 도움이 됩니다:

7-A 질문 에서 큰돌님은 dp를 초기에 -1로 초기화하고, 레퍼런스를 사용하여 시간복잡도를 줄이는 방법을 설명하고 있습니다.
7-A dp초기화값 관련 시간초과 질문 에서 dp 초기화 방식에 따른 시간 초과 문제에 대한 상세한 설명이 있습니다.

질문하신 내용과 관련된 해결책을 제시하고 있는 기존 답변을 참조하여 이해를 돕기를 바랍니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

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

7-V 질문있습니다 :)