7-a 질문

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

7-A

해결된 질문

작성

안녕하세요 큰돌님!

Tc 가 아래와 같고

0 29 20 21 16

29 0 15 29 28

20 15 0 15 14

21 29 15 0 4

16 28 14 4 0

dp[3][15]=20이 나왔습니다. 이 수는 3->4->0의 경로인데

아무리 생각해도 이걸 0,1,2,3을 방문했을 때의 최솟값이라 납득하기 어렵습니다

제가 이해를 잘못한걸까요?

//이미 거리가 계산되어 있으면 반환 
    if (dp[here][visited]!=-1){
        cout<<"이미 계산한 점이 있을 때 현재 위치 : "<<here<<" "<<dp[here][visited]<<" && ";
        print(visited);
        return dp[here][visited];
    }

c++코딩-테스트

답변 2

큰돌

지식공유자

안녕하세요 ㅎㅎ

dp[a][{b}]의 의미는

현재 정점이 a이고

{b}라는 정점들을 방문했을 때의 "남은 도시 {c}를 방문하고 다시 0으로 돌아가는 최소값을 의미합니다.

제가 한번 드림을 그려봤는데요 ㅎㅎ

dp[3][15]의 의미는 {0, 1, 2, 3}을 방문하고 -> 남은 도시 4를 방문하고 다시 0으로 돌아가는 최솟값이 됩니다.

지금 보시는 것처럼 파란색 형광펜 친 부분들은 모두 방문을 했고 남은 정점 4를 방문하고 다시 0으로 돌아가게 되면 20이 됩니다.

그렇기 때문에 dp[3][15]는 20이 됩니다.

해당 부분은 제 강의 내의 설명이 부족했던 걸로 생각이 듭니다.

충분히 수강생님 처럼 헷갈릴 수 있는 부분인 것 같습니다.

해당 부분은 추후 보강해서 재촬영하도록 하겠습니다.

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

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

감사합니다.

강사 큰돌 올림.

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다. ililil님의 질문을 기반으로 관련 질문과 유사한 답변을 찾았습니다.

질문해주신 내용은 주어진 dp 배열의 일부분(dp[3][15] = 20)이 외판원 순회 문제에서 특정 경로에 해당하는 값을 가지는 이유에 관한 것입니다. 여기서 3->4->0 경로는 나머지 도시들을 방문하고 특정 위치로 돌아가는 최소 비용을 잘못 해석할 수 있습니다. 이와 관련하여 외판원 순회 문제의 다소 복잡한 DP 해답 구조를 이해하는 데는 반복적인 값을 계산한 메모이제이션을 이해하는 과정이 필요합니다.

이 문제는 외판원 순회 문제(Travelling Salesman Problem)에서 흔히 보는 패턴 중 하나로, 도시들의 순서를 고려하지 않는 최적해를 구성하는 과정에 대해 잘못 이해하면 경로의 계산이 이상하게 보일 수 있습니다. 주어진 DP 값 dp[here][visited]는 특정 상태(여기서는 here 위치와 visited 상태 표시)에 대한 최적의 경로 비용을 보관합니다.

관련된 내용을 더 이해하기 위해 다음의 유사 질문을 참고하실 수 있습니다:

7-A 메모이제이션 되어 이미 계산된 상태에서 왜 경로 값이 다를 수 있나요?

위 링크에서는 메모이제이션의 역할과 DP에서 올바른 경로 추적의 중요성에 대해 논의한 답변이 담겨 있습니다.

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

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

7-a 질문