[바킹독의 실전 알고리즘] 0x1B강 - 최소 신장 트리

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

질문 전에 이 글을 반드시 확인해주세요. 질문 가이드를 정확하게 따라간 질문에 대해서만 답변을 드리고 그렇지 않은 질문은 먼저 가이드에 맞게 수정을 요청할 예정입니다. github.com/encrypted-def/basic-algo-lecture/blob/master/docs/how-to-ask.md 8:06 시간복잡도가 O(V)인 것에 대해 추가 설명을 하자면 정확히는 O(V+E)인데 트리의 특성상 매번 간선의 수 E가 V-1 이하이기 때문에 결론적으로 O(V)가 됩니다. 17:23 1과 3을 연결하는 간선 -> 1과 4를 연결하는 간선입니다.

[@d.b768]

항상 잘듣고있읍니다 선생님,, 최소 스패닝 트리 기여하셨던데 역시,,👍👍

[@sungminyun233]

와 물대기 문제 풀이법 보고 기립박수 쳤습니다

[@neonetproject]

강의를 보면서 궁금한게 있습니다. 1. Kruskal Algorithm을 사용할때 tuple 배열을 priority_queue 로 사용하게 되면 문제 될게 있을까요? 제가 봤을땐 기능에는 차이가 없을 것 같은데 시간 복잡도가 늘어나려나요? 2. Kruskal Algorithm을 사용할때 is_diff_group 함수에서 if(p[u] == p[v]) p[u]--; 라는 코드를 넣은 이유는 무엇인가요?

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

1. priority_queue를 하고 매번 pop하는 것도 문제는 없습니다(다른 관점에서 보면 정렬을 그냥 힙소트로 수행한거임). 일단 big-O로 봤을 땐 정렬하는거랑 O(ElgE)로 똑같고 아마 실제 실행속도는 (아마) 전체를 한번에 정렬하는게 빠르긴 할겁니다. 2. union by rank를 하기 위함입니다. union find에 대해 찾아보세요

[@basha____]

와 물대기 아이디어 진짜 지리네요

[@daumtto]

끝이보입니다

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

끝까지 화이팅!

[@배제우-v2k]

백준 5214 환승 문제도 그래프 리모델링 문제가 맞나요?

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

넵

[@배제우-v2k]

강의 잘 듣고 있습니다 감사합니다 ㅎㅎ

[@soloplay_]

17:23에서 현재 우선순위 큐에서 비용이 가장 작은 간선은 1과 3을 연결하는 간선 혹은 3과 4를 연결하는 간선 이 부분이 조금 이상합니다.

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

"1과 4를 연결하는 간선"임을 명시하겠습니다. 알려주셔서 감사합니다!

[@ike3071]

물대기 문제 Tip을 보고 기립박수를 쳤습니다. 어떻게 하면 이런 풀이를 생각할 수 있을까요?

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

처음 접한 사람이 저걸 떠올리는걸 불가능에 가깝다고 생각하고, 이제 한 번 봤으니 비슷한게 나오면 풀 수 있겠죠ㅎㅎ

[@HW-ms4nt]

union find에서... 질문드립니다. bool is_diff_group(int u, int v){ // Union u = find(u); v = find(v); if(u == v) return 0; if(p[u] == p[v]) p[u]--; if(p[u] < p[v]) p[v] = u; else p[u] =v; return 1; } 이 것이 union 이라고 설명해주셔서 union by rank도 찾아봤는데요. p는 parent를 뜻하는 것일텐데 if(p[u] == p[v]) p[u]--; 이 부분에서 부모가 같을 때 왜 p[u]를 감소시키는지, (부모의 값을 변화시키는지) 이해가 되지 않아서 문의드립니다. unioon by rank를 검색했을 때는 rank를 변화시키는데 여기서 rank에 해당하는 배열 또는 벡터가 없는 것 같아서요 늘 좋은 강의 감사합니다.

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

p[u]가 양수일 땐 부모의 번호이고, 음수일 땐 -p[u]가 u의 랭크입니다

[@user-jy6zb5jd6u]

물대기 프림 알고리즘으로 해결~ 솔직히 힌트덕분이다 ㅇㅈ? ㅋㅋㅋㅋ

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

ㅇㅈ합니다

[@user-jy6zb5jd6u]

확실히 뒷강의로 갈수록 댓글들이 적네 ㅋㅋㅋㅋ

[@김희영-z1r1u]

강의 내용 중 11:20 부분에 나온 Union by rank 코드에서, 14행 코드대로라면 랭크가 같을 때만 랭크를 증가시키게 되는데 이렇게 되는 이유가 있을까요? 예를 들어 노드 3개가 하나의 연결그래프이고, 이 상태에서 새로운 노드를 연결시키고자 할때 각각 랭크2, 랭크1인데 합치더라도 랭크가 다르므로 2와 1을 더한 3이 아니고 2가 되는 것이 이해가 되지 않습니다.

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

그게 간단히 댓글로 설명을 드리기 힘든 다소 복잡한 이론적 배경을 가지고 있는데, 이렇게 해야 가장 최적의 시간복잡도(N*애커만 함수)가 나오고 2와 1을 더한 3으로 처리하는 union by size에서는 N*lgN이 됩니다. 하지만 union by size만 하거나, 혹은 아예 그냥 union을 마음대로 하더라도 path compression만 해도 N*lgN이 나오기 때문에 크게 신경을 쓰지 않아도 되는 부분이긴 합니다. en.wikipedia.org/wiki/Disjoint-set_data_structure#Union_by_rank 여기 내용 확인해보시는걸 추천드립니다.

[@김희영-z1r1u]

@@BaaaaaaaaaaaaaaaaaaaaarkingDog 우선 답변해주셔서 감사합니다. 고민 끝에 이해한 바로는 결국 find()함수에서 특정 노드에서 부모노드를 찾는 과정을 최적화하고자 하는 것이므로, 말단노드에서 부모노드까지의 거리가 최소가 되어야하며, 이 '거리'가 rank인 것 같습니다. 또한 최적화를 위해 rank가 서로 다른 두 연결그래프를 합칠 때 연결그래프의 최대 깊이인 rank가 변하지 않는 방향으로 합치게 되는 것 같습니다. 항상 좋은 강의 감사드립니다! :)

[@즐쌤]

갓킹독

[@zero2vec]

킹갓독

[@김김-j1m]

10:52 최소 스패닝 트리 풀이 과정에서 17열에 p[u]-를 한 이유가 뭔지 잘 모르겠습니다. 유니온 파인드의 유니온의 swap(u, v)와 같은 표현인건가요?

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

p[u]-이 뭔가요?

[@김김-j1m]

@@BaaaaaaaaaaaaaaaaaaaaarkingDog 죄송합니다 모바일로 작성하다 보니 오타가 나서 14열을 17열로 잘못썼네요. 14열에 p[u]- -; 부분입니다

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

union find에서 union by rank를 한거에요

[@김김-j1m]

@@BaaaaaaaaaaaaaaaaaaaaarkingDog 제가 질문의 내용이 좀 부족했네요. 제가 찾아본 union by rank 과정에서는 rank 변수를 따로 두고 진행 하던데 바킹독 님께서는 따로 두고 하지 않으시더라구요. 그래서 어떻게 따로 변수를 안두고 p[u]-; 연산으로 처리하신건지 궁금해서 여쭤 봤습니다. 제가 union by rank의 이해도가 좀 낮아서 그런거 같네요. 키워드를 알려주셔서 감사합니다.

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

@@김김-j1m 그냥 저기 적힌 코드가 정석적인 union by rank 구현 방법 중 하나이고 i가 루트일 경우 i의 rank가 (-1) * p[i]라는 의미이고, i가 루트가 아닐 경우 p[i]에 i의 부모가 저장되어있어요. union by rank라고 검색해보면 자료 많이 나와요.

[@andrewsohn9982]

짱킹독

[@이성진-i7o]

231017 감사합니다.

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

[@박건희-s4d1p]

킹하~

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

hi

[@zam38]

황킹독