집합 표현하기(백준 1717) union 함수 질문
안녕하세요 강의 잘 보고 있습니다.
강의를 보다가 질문이 생겨 질문드립니다.
강의 영상에서 union 함수에서 a,b의 크기와 상관없이
a와 b가 다르다면 parent[b] = a; 라고하시는데
이렇게 해도 되는 이유가 어차피 나중에 find 함수의 재귀함수부분 return parent[a] = find(parent[a]); 에서 경로 압축이 되기 때문에 크기 상관없이 parent[b] = a; 선언 해주신 건가요?
답변 1
1
안녕하세요 반갑습니다.
일반적으로는
if(a<b) parent[b] = a;
else if(a>b) parent[a] = b;
이렇게 작은수를 항상 root노드로 선정하거나 문제에 따라 반대로 일관되게 구현 합니다.
다만 해당 문제에서는 특별히 이렇게 통일해야하는 제약조건이 보이지 않았고 말씀하신대로
경로압축을 하면 크게 성능에도 문제가 없다고 생각하여 크기에 상관없이 유니온을 하였습니다.
일반적으로는 대부분 작은 수가 root노드가 되도록 많이 하시더라구요.
(문제의 조건이 있으면 꼭 조건에 맞게 구현하셔야합니다.!!)
감사합니다. 즐거운 하루되세요 :)
백준 1940 주몽의 명령 시간복잡도
0
62
0
다음영상이 문제 풀이 영상이라고 하셨는데 문제풀이 영상이 누락되어있는 것 같습니다
0
129
1
코딩테스트 디버깅
0
352
1
탐색 순서 질문
0
149
1
[P11726 2*N 타일채우기] top down 방식을 사용하니 런타임 에러가 발생합니다.
0
106
1
2018 연속된 자연수의 합 구하기 백준 사이트에서 메모리 초과 오류가 발생합니다.
0
204
1
1강 시간복잡도 중간에 중첩for문 직전에 상수는 상관없어요 하신 부분이 이해가 안됩니다
0
162
1
왜 int, long은 안되는지 궁금합니다.
0
225
1
DNA 비밀번호 (백준 12891) 통과가 안됩니다.
0
528
2
LCA 빠르게 구하기 Java 코드 시간초과
0
245
1
스택문제 백준 1874
1
460
1
백준11659 구간합 런타임 에러
0
308
1
백준 2178 미로탐색 질문 입니다.
0
449
1
구간합구하기1 (백준11659)
0
424
1
혹시 다른 ide에서 잘 돌아가는 프로그램이
0
352
1
내림차순으로 정렬하기 강의에서..
0
272
1
백준 11720 숫자의 합 질문 있습니다
0
436
1
(숫자의 합)1<=N <=100 사이의 값
0
385
1
소수구하기-백준 1929 질문
0
351
1
12891_DNA비밀번호
0
635
3
숫자의 합 구하기
0
393
1
안녕하세요 질문있습니다.
0
338
0
union 코드에 질문 있습니다.
0
407
2
[그리디 실전 문제] 최솟값을 만드는 괄호 배치 찾기 (백준 1541) - 반례를 못찾겠습니다 ㅠㅠ
1
312
1