7-a 질문
안녕하세요 큰돌님!
Tc 가 아래와 같고
5
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];
} 답변 2
0
안녕하세요 ㅎㅎ
dp[a][{b}]의 의미는
현재 정점이 a이고
{b}라는 정점들을 방문했을 때의 "남은 도시 {c}를 방문하고 다시 0으로 돌아가는 최소값을 의미합니다.
제가 한번 드림을 그려봤는데요 ㅎㅎ
dp[3][15]의 의미는 {0, 1, 2, 3}을 방문하고 -> 남은 도시 4를 방문하고 다시 0으로 돌아가는 최솟값이 됩니다.
지금 보시는 것처럼 파란색 형광펜 친 부분들은 모두 방문을 했고 남은 정점 4를 방문하고 다시 0으로 돌아가게 되면 20이 됩니다.
그렇기 때문에 dp[3][15]는 20이 됩니다.
해당 부분은 제 강의 내의 설명이 부족했던 걸로 생각이 듭니다.
충분히 수강생님 처럼 헷갈릴 수 있는 부분인 것 같습니다.
해당 부분은 추후 보강해서 재촬영하도록 하겠습니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
안녕하세요, 인프런 AI 인턴입니다. ililil님의 질문을 기반으로 관련 질문과 유사한 답변을 찾았습니다.
질문해주신 내용은 주어진 dp 배열의 일부분(dp[3][15] = 20)이 외판원 순회 문제에서 특정 경로에 해당하는 값을 가지는 이유에 관한 것입니다. 여기서 3->4->0 경로는 나머지 도시들을 방문하고 특정 위치로 돌아가는 최소 비용을 잘못 해석할 수 있습니다. 이와 관련하여 외판원 순회 문제의 다소 복잡한 DP 해답 구조를 이해하는 데는 반복적인 값을 계산한 메모이제이션을 이해하는 과정이 필요합니다.
이 문제는 외판원 순회 문제(Travelling Salesman Problem)에서 흔히 보는 패턴 중 하나로, 도시들의 순서를 고려하지 않는 최적해를 구성하는 과정에 대해 잘못 이해하면 경로의 계산이 이상하게 보일 수 있습니다. 주어진 DP 값 dp[here][visited]는 특정 상태(여기서는 here 위치와 visited 상태 표시)에 대한 최적의 경로 비용을 보관합니다.
관련된 내용을 더 이해하기 위해 다음의 유사 질문을 참고하실 수 있습니다:
위 링크에서는 메모이제이션의 역할과 DP에서 올바른 경로 추적의 중요성에 대해 논의한 답변이 담겨 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
코딩살구클럽
0
5
1
코딩살구클럽 문의
0
21
2
코딩살구클럽 승인
0
27
2
DP 경우의 수 설명이 이해가 되지 않습니다.
0
32
2
3-F 채점 관련 질문
0
26
1
BFS, DFS 활용이 되는 상황에서의 방향성
0
32
2
코딩살구클럽 승인
0
41
2
코딩살구클럽승인
0
35
3
코딩살구클럽 승인
0
50
2
3-D 관련 질문
0
35
2
코살구 회원가입 문의
0
44
2
코살구 로그인 문제
0
65
2
3-A 문제 풀이 관련 질문
0
56
3
2-O 질문 있습니다
0
38
2
2-T 문제에 관한 질문
0
40
2
코딩 살구 클럽 접속 및 사용방법 문의
0
62
2
안녕하세요~. 현재 코살코딩클럽 사이트가 접속이 안됩니다~
0
64
2
코딩살구클럽 로그인문제
0
78
3
코딩 살구 클럽 로그인 문제
0
84
2
2-J 채점관련 질문
0
65
3
코딩 살구 클럽 Python 지원 가능 여부
0
77
1
살구클럽 아이디 없음 문제
0
76
1
1-O 코딩살구클럽 채점관련 질문
0
60
2
히든 테스트 케이스가 사라졌습니다
0
57
1