인프런 커뮤니티 질문&답변
작성한 질문수
7-A 질문이 있습니다
해결된 질문
작성
·
248
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
강의 내용 1분~3분에서 말씀하신 내용이 이해가 가질 않습니다.
a->d로 간다 했을 때 {a, b, c}의 최소값을 찾아서 d로 가면 된다고 하셨는데 제가 저 말뜻을 제대로 이해했는지는 모르겠지만 제가 생각했을 때는 저 셋을 가는 경로에서 최솟값은 아니어도 d로 갔을 때 최솟값이 되는 경로도 존재할 거라고 생각이 들어서 {a, b, c}경로의 최솟값에서 d로 가면 그게 또 최소 경로?가 된다는 건 이해를 잘 못하겠습니다.
코드를 따라 쳐보면서 코드 자체 만으로도 이해를 해보려 했는데 tfs함수 부분에서 ret을 저렇게 메모이제이션 처리를 하면 무슨 이득이 있는지 모르겠습니다.
제 생각에는 경로가 a b c d 라고 했을 때 (경로가 모두 0이 아니라고 했을 때)
a b c d
a b d c
a c b d
a c d b
a d b c
a d c b
이런식으로 탐색을 할 거라고 생각이 드는데 결국 완전탐색 느낌으로 탐색을 한 게 아닌가? 라는 생각이 듭니다.
if (ret != -1)
return ret;
이 부분이 메모이제이션을 써서 얻을 이득일텐데 저게 a b c d를 돌면서 작동을 하지 않을 거라고 생각이 드는데... 왜 저 코드가 필요한지 잘 모르겠습니다. 막상 실제로 저 부분 빼고 제출하니까 시간초과가 나기는 하는데 제 머리로는 도저히 이해가 안갑니다.
답변 2
0
안녕하세요 성우님 ㅎㅎ
저 셋을 가는 경로에서 최솟값은 아니어도 d로 갔을 때 최솟값이 되는 경로도 존재
>>
네 맞습니다. 그러한 경로가 있을 수 있습니다.
해당 강의에서 말하는 것에서 중요한 점은 "순서는 상관이 없다" 라는 것입니다.
제가 강의에서 설명할 때 좀 헷갈리게 설명드린 거 같은데요. ㅎㅎ
편의상 {a, b, c} 최솟값 + d라고 했는데.
d + {a, b, c}의 최솟값이라고 하면 좀 이해가 쉬울까요?
d라는 정점을 방문하고.
그 다음.
{a, b, c}라는 정점들을 모두 방문해야 한다면
이 때 최적해는 d + min{a, b, c}가 되어야 하는게 아닐까요?
코드 참고부탁드립니다.
for(int i = 0; i < n; i++){
if(visited & (1 << i)) continue;
if(dist[here][i] == 0) continue;
ret = min(ret, tsp(i, visited | (1 << i)) + dist[here][i]);
이런식으로 탐색을 할 거라고 생각이 드는데 결국 완전탐색 느낌으로 탐색을 한 게 아닌가?
>> 순서를 고려하면 그렇지만 순서는 고려를 하지 않아도 됩니다.
if (ret != -1)
return ret;
>> 이 코드가 필요한 이유는. 예를 들어 {a, b, c, d}라는 해를 구한다고 했을 때 이미 구한 {a, b, c}에 해에서 d 를 더해 {a, b, c, d}를 구한다는 것입니다. 해당 {a, b,c}의 조합의 최적해가 ret에 담겨있다고 생각하시면 됩니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
안녕하세요 성우님 ㅎㅎ
int& ret = dp[here][visit];
if (ret != -1)
return ret;
이 부분이 납득이 안되는데
>> 메모이제이션 부분입니다. ret을 수정하면 dp[here][visit] 이부분도 수정이 됩니다.
dp[here][visit]에서 visit이 겹치는 케이스를 도저히 생각을 못하겠습니다.
>>
예를 들어 a, b, c로 방문하거나 a, c, b로 방문하는 경우입니다.
here은 d라고 가정해보면 됩니다.
그렇게 되면 visit는 111이 되고 111이 다시 나타나겠죠? 이 중 최솟값이 dp에 담기게 됩니다.
a b c d
a c b d
라고 해보겠습니다.
이런 식으로 가면 겹칠 거라고 생각이 들었는데
두 번째 노드를 탐색하는 과정이라고 생각했을 때
dp[b][0011]과
dp[c][0101]은 엄연히 다르고
세 번째 노드를 탐색하는 과정이라고 생각했을 때
dp[c][0111]과
dp[b][0111]은 엄연히 다른 부분이므로
처음에는 언뜻 dp가 적용이 될 거라고 생각되는 부분도 적용이 안될 거라고 생각이 들었습니다.
지금도 여기서 생각이 머무르고 있습니다.
>>
a b c d a
a c b d a
라고 해보겠습니다.
a부터 시작한 dp[a][]는 다음과 같은 과정을 통해 쌓이게 됩니다.
dp[a]
dp[a][b], dp[a][c] 중 최소
dp[a][b, c], dp[a][c, b] 중 최소
dp[a][b, c, d], dp[a][c, b, d] 중 최소
그렇게 타고 내려간 2개의 경로가 다시 a를 만나
if(visited == (1 << n) - 1){
return dist[here][0] ? dist[here][0] : INF;
}앞의 코드를 만나게 되면서 거리를 반환하게 됩니다.
그렇게 되면
dp[a][b, c, d], dp[a][c, b, d] 중 최솟값은 dp[a][{b, c, d}]에 쌓이게 됩니다.
참고로 정확히는
dp[a][a, b, c, d]입니다.
처음에는 언뜻 dp가 적용이 될 거라고 생각되는 부분도 적용이 안될 거라고 생각이 들었습니다.
>>
앞에서 설명드렸듯이
here이 같고 visit가 같은 부분이 존재합니다.
if (dp[here][visit] != -1) 이 거름망 역할을 해야 될 거라고 생각이 드는데 이게 어떻게 작동이 되는지 모르겠습니다.
>> 거름망이 되는 것은 맞습니다. 해당 부분에 최솟값이 담겨있다면 넘어갑니다.
근데 여기서 a라는 정점을 고정시키고 나서는 순열처럼 순서를 바꿔서 다 따진다고 생각이 드는데 큰돌님이 말씀하시는 건 순서가 상관이 없다라는 게 중요하다고 하시는데... 그 말 뜻을 제대로 이해를 못하겠습니다ㅠ
>> 일단 순서가 상관없는 것은 두가지 의미가 있습니다.
1)
예를 들어 이런 경우의 수를 보시면
a -> b -> c -> a
b -> c -> a -> b
이 2가지의 경우만 봐도 시작점이 어디든 상관없습니다.
2)
b -> 다른 정점 -> b 라고 했을 때 다른 정점들의 순서는 상관이 없습니다.
어찌되었든 정점들을 모두 방문한 것중에 최솟값 만 찾으면 되는 문제입니다.
즐거운 추석 보내시길바랍니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
안녕하세요, 인프런 AI 인턴이에요.
질문에 대해선 조금 더 구체적인 내용이 포함되어야 제대로된 답변을 드릴 수 있을 것 같습니다.
현재 설명하고 있는 부분은 코드에 대한 이해와 최소값 경로에 대한 이해에 관한 내용 같은데요, 코드나 논리적인 플로우에 대한 자세한 설명이 필요해 보입니다.
또한, tfs 함수에서 메모이제이션(ret) 처리를 하는 이유에 대해서도 함께 문의하셨는데, 이 부분 또한 코드에 대한 전체적인 내용과 목적에 따라 설명할 수 있을 것 같아요.
위 내용을 포함하여 다시 질문해주시면 더욱 정확한 답변을 드릴 수 있을 것 같습니다. 감사합니다.
답변 정말 감사합니다.
그렇지만 아직 이해가 안가는 부분이 있습니다.
말씀해주신 부분을 대략적으로 느낌은 알겠으나... 코드자체로만 봤을 때 매칭이 잘 안됩니다.
제 생각에는 a b c d 이렇게 타고 타고 호출이 되어서 끝점에서부터 ret이 return되면서 차츰 차츰 a b c가 dp[c][0111]에 기록이 되고, a b d가 dp[d][1011]에 기록이 되고 다시 a b가 dp[b][0011]에 기록이 되고 여기서 for문 돌면서 a c->아까와 비슷한 일련의 함수 호출과정, 다시 for문 돌아와서 a d->일련의 호출 과정
이런 느낌으로 저는 코드가 해석이 됩니다. 여기서 제가
int& ret = dp[here][visit];
if (ret != -1)
return ret;
이 부분이 납득이 안되는데
dp[here][visit]에서 visit이 겹치는 케이스를 도저히 생각을 못하겠습니다.
그래서 처음에는 dp가 적용이 안되는 것 같은데 뭐하러 dp 배열을 쓰는거지? 하면서 dp를 없애고 제출을 하니까 바로 시간 초과가 나면서 틀렸다고 떴습니다.
그래서 대략적으로 제가 적용이 될 거라고 생각이 드는 케이스를 생각해봤을 때
a b c d
a c b d
이런 식으로 가면 겹칠 거라고 생각이 들었는데
두 번째 노드를 탐색하는 과정이라고 생각했을 때
dp[b][0011]과
dp[c][0101]은 엄연히 다르고
세 번째 노드를 탐색하는 과정이라고 생각했을 때
dp[c][0111]과
dp[b][0111]은 엄연히 다른 부분이므로
처음에는 언뜻 dp가 적용이 될 거라고 생각되는 부분도 적용이 안될 거라고 생각이 들었습니다.
지금도 여기서 생각이 머무르고 있습니다.
노드를 늘려서 a b c d e f 이렇게 따져봐도 a라는 정점 고정시키고 나서는 for문으로 계속해서 탐색하지 않은 곳을 순열처럼 일정한 순서대로 탐색을 할텐데 여기서 if (dp[here][visit] != -1) 이 거름망 역할을 해야 될 거라고 생각이 드는데 이게 어떻게 작동이 되는지 모르겠습니다.
출발점이 상관이 없다는 건 이해가 됩니다.
근데 여기서 a라는 정점을 고정시키고 나서는 순열처럼 순서를 바꿔서 다 따진다고 생각이 드는데 큰돌님이 말씀하시는 건 순서가 상관이 없다라는 게 중요하다고 하시는데... 그 말 뜻을 제대로 이해를 못하겠습니다ㅠ 순서가 상관이 없으면 그건 조합이랑 비슷한 것 아닌가? 라고 해석이 되고... 그럼 그냥 a b c d 같이 경로 하나만 따지면 되지 않았나? 생각이 듭니다...
다른 DP문제는 풀면서 어렵지만 어느정도 납득하면서 넘어가는데 이 TPS문제가 저한테는 너무 어렵네요... ㅠ