18강 - 합집합 찾기(Union-Find) [ 실전 알고리즘 강좌(Algorithm Programming Tutorial) #18 ]

18강 - 합집합 찾기(Union-Find) [ 실전 알고리즘 강좌(Algorithm Programming Tutorial) #18 ] 강의 동영상입니다. 합집합 찾기 알고리즘은 두 개의 노드를 선택해서 해당 노드가 서로 연결이 되어있는지 여부를 파악하기 위해 사용되는 알고리즘입니다.

[@thugken]

8:30 이해 안되시는분들을 위해
UnionParent 함수에서 2와 8의 부모값을 찾은후 변수 2의 부모값 1을 a에, 8의 부모값 5를 b에 넣고 a값이 더 작기때문에 b(=5)의 부모값 5를 a인 1로 바꿔줌으로써 5를 부모로 하는 모든 자식들이 결국엔 1(5의 부모값)을 부모로 하게 됨으로 1부터8까지 모두 연결되는것입니다.
Union함수안에 변수 a,b를 무시하고읽다가 이해하는데 1시간 걸렸네요 ㅠㅠ 열공하세요~~

[@인사이드-e7h]

이 코드는 결함이 있네요;; 집합을 합칠때는 테이블을 다 순회하면서 두 집합의 합집합의 요소중에 가장 작은 요소를 부모로 둬야합니다.

[@허새-u8w]

알맹이만 쏙쏙 이해할 수 있어서 너무 좋네요 ! 좋은 영상 너무 도움이되요 !감사합니다.

[@choogyullee2818]

진짜 당신이 최고입니다...

[@yoojeong7484]

책으로 혼자 하려니깐 이해하기 너무어려웠눈데 설명을 쉽게해주시네요!!감사합니당

[@송문선-k7c]

귀에 쏙속 들어오네요!! 감사합니다!!

[@you3667]

최고의 설명. 감사합니다

[@이동욱-t9b]

궁금한게 있는데 unionParent 함수는 void 가 되야하는게 아닌가요? 리턴값이 없어서요 void 로 바꾸고 실행하니 강의와 같은 결과가 나오는데 visual studio 환경이랑 dev c++ 이랑은 좀 다른것같네요

[@김성호-r8r]

안녕하세요. 강의잘봤습니다. 이해도잘되구요! 그런데 질문이 있는데 그럼 이 함수들은 union하는 두값에 대해서만 parent[]값을 갱신하는데요, 그럼 그래프를 연결할때마다 연결된성분의 모든 parent[]값을 갱신하려면 연결할때마다 getparent를 연결된 성분에 수행해야하는건가요? 만약 1234 가 연결되어있고 5678이 연결되어있다면 4와5를 union 하면 5678 모두 parent 값이 1로 바뀌게갱신하고싶다면요! 아니면 함수를 아예 다르게 짜야하는건가요?

[@김성호-r8r]

아... 그냥 비교를할때 getParent 를 하므로 그냥 다바꿔줄필요가없고 O(1)이 드는거군요...

[@GGz8112]

진짜 잘가르치네요

[@ryuwldnjs]

설명 잘하시네요..이해잘됐습니다

[@np_research2772]

자세한 설명 감사합니다.

[@똔-z6v]

진짜 최고....

[@양기모-n2e]

강의 너무 잘 보고 있습니다.
질문이 있는데요, 4랑 6을 연결하면 parent 값은 둘 다 4가 되는데, 여기서 6과 1을 연결하면 getParent 값이 1이 더 작기 때문에 6의 parent 값이 1이 되어서 4(parent 값: 4)랑 6(parent 값: 1)의 연결이 끊어지는거 아닌가요?

[@uyr7059]

그래서 전 값이 큰 노드의 부모 노드의 부모값도 변경하는 코드 추가했습니다. 이렇게 추가했더니 정상적으로 연결이 이어지더라구요

[@skiddieahn8436]

소스 코드에는 부모노드끼리 연결합니다. 즉 6의 부모인 4와 1이 연결돼서 문제가 발생되지 않습니다. (1-4-6) 형태가 되겠네요.

[@BalanceGamers]

함수인자에 굳이 parent[]가 있는 이유는 뭔가요? 전달받지 않아도 참조할 수 있지 않나요? 궁금합니다.

[@user-vc5vo4ol2g]

와 뭐 이렇게 쉽게 가르쳐요..

[@pkj6962]

1과 7을 연결한 뒤 1과 5의 연결성을 검증할 때, 5의 부모노드는 5 자신이기 때문에 다른 노드로의 재귀를 거치지 않아 연결되지 않았다고 결과가 나와야 하는 것 아닌가요? 헷갈립니다.

[@193오]

1과 7을 연결할때 5의 부모노드가 1로 바뀌죠

[@복잡볶음면]

감사합니다 ㅎㅎ

[@hyungeollee27]

감사해요.. 근데 "값을"을 발음하실 때 [갑슬] 이라고 발음하셔야 되는데 [가플]이라고 발음하시는거 같아요ㅎㅎ

[@dongbinna]

향후 강의 촬영에 있어서 유의하겠습니다. 최근 영상에서는 [갑쓸]로 바르게 발음하고 있습니다.

[@한수빈-i2o]

책에 나온 코드보다 이게 훨씬 쉽네요 ㄳ

[@서울변호사]

4:10 소스코드 시작

[@user-ri3lj1kq9w]

안녕하세요 혹시 차집합 구하는 법 알려주실 수 릴나요..?ㅠㅠㅠ

[@김누렁-o7w]

parent[ ] 로 쓸때랑 parent 라고 그냥 쓸때랑 차이를 모르겟습니다. ㅠㅠㅠ

[@cookiboi1234]

미친사람인가 ㅈㄴ잘알려주네

[@김종민-l8t]

getParent함수에서 return parent[x] = getParent(parent, parent[x]) 가 아니라 return getParent(parent, parent[x])를 해야하지 않을까요?

[@가-o8k]

1 2 3이 연결되어있고 5 6 7이 연결되어있을때 3과 5를 연결한다고 가정한다면 6과 7은 여전히 5를 부모로 가집니다. 이때 6에대해 getParent를 하게되면 재귀를타고 1을 돌려받는데 이경우에 parent테이블상 6의 부모를 5에서 1로 갱신하기 위함입니다.