안녕하세요. 늘 잘보고있습니다. 서로소집합을 활용한 사이클 판별 질문있습니다. 예를들어 정점 1,2, 3, 이 있고 간선이 (1,2) (2,3) 만 있는 경우 사이클이 발생하지 않는데, 작성하신 코드로 돌려보면 cycle이 true로 발생하지 않나요?! 답변 주시면 감사하겠습니다!
유니온 파인드 관련 알고리즘을 수정하셔야 할듯 보입니다. 지금 코드에선 서로 다른 집합을 union 하는 경우에 해당 정점만 값이 바뀌고 집합에 포함되어 있는 정점들은 변하질 않네요. 그래서 크루스칼 알고리즘 저렇게 짜시면 35번 간선도 포함 됩니다. 정확히 얘기하자면 34번 간선이 합쳐 질 때 (1, 2) (3, 4, 6, 7) 두 집합이 있어서 union 하는 경우 (1, 2, 6), (3, 4, 7) 이 따로 묶이게 됩니다. 정상적으로는 (1, 2, 3, 4, 6, 7) 이겠죠. 그래서 35번 간선을 union 하게 되면 서로 다른 집합으로 보게 되어 (1, 2, 3, 6) (4, 7) 이렇게 묶이네요. 잘못 묶이네요.
안녕하세요, 동건 님. 충분히 헷갈리실 수 있는데요. 각 노드에 대해서 "어떤 집합에 속해 있는지" 확인할 때는 parent 테이블에 직접 접근하는 것이 아니고, findParent() 함수의 결과를 사용한다는 점을 기억하셔야 합니다. findParent() 함수를 호출하면 parent 테이블도 자동으로 갱신이 되겠죠? 동영상 내에 설명이 포함되어 있으므로, 조금 더 고민해보시면 좋을 것 같습니다 :)
![[이것이 코딩 테스트다 with Python] 36강 위상 정렬](http://i.ytimg.com/vi/xeSz3pROPS8/mqdefault.jpg)
![[알고리즘 강의] 심화 그래프 알고리즘 1. 위상 정렬](http://i.ytimg.com/vi/HxHISRelNuM/mqdefault.jpg)
![Seungmin "그렇게, 천천히, 우리(As we are)" | [Stray Kids : SKZ-PLAYER]](http://i.ytimg.com/vi/kAzmhLHePqU/mqdefault.jpg)
![[텍스트 분류 모델 공격 기법] TextFooler: Is BERT Really Robust?](/img/1.gif)
오늘도 학습하러 들렀습니다. 너무 수준 높고 깔끔한 강의 감사합니다 ^^ (1회: 21:39)
이렇게 좋은 강의를 무료로 올려주시다니 님은 복받으실 겁니다.
진짜 이런 깔끔한 강의 시리즈 올려주셔서 너무 감사합니다. 잘 보고 갑니다.
동빈님 감사합니다. 코테 공부 하기 위해서 이 책은 2회독을 먼저 하려 하는데 많은 도움 되고 있습니다. 이전에 다른 교육을 받은 적이 있는데, 하나부터 차근차근히 진행하는게 아니어서 힘들었어요. 동빈님 강의 보니 바닥부터(?) 하나씩 쌓아가며 이해가되어서 좋습니다.
개발자들의 친절함은 다른 분들과는 결이 다른 부분도 있는데(그것만 있다는건 아닙니다) 나만의 지식이 아니라 그걸 나눠주는 친절함... 동빈님, 스택오버플로우 형님들... 항상 감사합니다 ㅠㅠ
안녕하세요. 늘 잘보고있습니다.
서로소집합을 활용한 사이클 판별 질문있습니다.
예를들어 정점 1,2, 3, 이 있고 간선이 (1,2) (2,3) 만 있는 경우 사이클이 발생하지 않는데, 작성하신 코드로 돌려보면 cycle이 true로 발생하지 않나요?! 답변 주시면 감사하겠습니다!
cycle이 발생하기 전, for loop이 종료될 것 같아요..! (1,2), (2, 3) 간선에 대해 각각 union_parent 함수가 실행되고, 모든 노드의 루트 노드가 1인 상태에서 for loop이 종료되어 cycle은 그대로 False이지 않을까요?
항상 감사합니다
나중에 구입해서 공부해보고 싶다.. ㅠㅅㅠ (그전에 시험부터 어떻게좀)
간선을 입력받으면서 경로압축의 find_parent를 실행시키면 원하는 값이 안나오네요
압축을 제대로 하기 위해서는 간선을 모두 입력받은 후 다시한번 모든 노드에 대해서 압축과정을 거쳐야 하네요.
전에 자바로 이 영상의 크루스칼 알고리즘으로 코테보다가 comparison method violates its general contract 이슈때문에 떨어진적이있습니다
찾아보니 input데이터가 많을때 날 수 있고 compareTo 함수에서 this.distance
커리큘럼 문제에서 코드 그대로 입력예시 넣어봐도 출력값이 10 20 14 14 3 이 나오는데 저만 이런가요...?
유니온 파인드 관련 알고리즘을 수정하셔야 할듯 보입니다.
지금 코드에선 서로 다른 집합을 union 하는 경우에 해당 정점만 값이 바뀌고 집합에 포함되어 있는 정점들은 변하질 않네요.
그래서 크루스칼 알고리즘 저렇게 짜시면 35번 간선도 포함 됩니다.
정확히 얘기하자면 34번 간선이 합쳐 질 때
(1, 2) (3, 4, 6, 7) 두 집합이 있어서 union 하는 경우 (1, 2, 6), (3, 4, 7) 이 따로 묶이게 됩니다. 정상적으로는 (1, 2, 3, 4, 6, 7) 이겠죠.
그래서 35번 간선을 union 하게 되면 서로 다른 집합으로 보게 되어 (1, 2, 3, 6) (4, 7) 이렇게 묶이네요. 잘못 묶이네요.
안녕하세요, 동건 님. 충분히 헷갈리실 수 있는데요. 각 노드에 대해서 "어떤 집합에 속해 있는지" 확인할 때는 parent 테이블에 직접 접근하는 것이 아니고, findParent() 함수의 결과를 사용한다는 점을 기억하셔야 합니다. findParent() 함수를 호출하면 parent 테이블도 자동으로 갱신이 되겠죠? 동영상 내에 설명이 포함되어 있으므로, 조금 더 고민해보시면 좋을 것 같습니다 :)
앗 감사합니다 참고할게요 잘못된게 아니군요 ㅎㅎ
확인해보니 코드를 제가 잘못짰었네요 ㅋㅋㅋ 감사합니다~ 도움 많이 되고있너요
반복문 안에 cost,a,b= edge 왜 써주는지 아시는분 있나요?
비용 순으로 정렬된 간선 리스트(edges)를 for 문에서 하나씩 사용하기 위함입니다
21:05
이 영상부터 조회수와 댓글이 엄청 줄어드는군요..
나왔다!
문제 부시러 가쯔아!
29:22