작은값을 대표노드로 해야한다 생각해서 아래처럼 min이 쓰일 줄 알았는데 private static void union(int a, int b) { //대표노드를 찾아서 연결 int ua = find(a); int ub = find(b); int max = Math.max(ua, ub); int min = Math.min(ua, ub); parent[max] = min; } 아래 댓글보니 '유니온 파인드 알고리즘 자체가 합집합을 만드는 개념이기 때문에 하나로 연결해준다라고 생각해주시면 되고 결론적으로는 어떤 방식으로 풀어도 차이가 없습니다. ' -> 작은값으로 안해도 연결만 되면 된다는 거죠? 항상 하루코딩 강의 잘보고 있습니다. 감사합니다.
안녕하세요! 반갑습니다. 네 맞습니다. 다만 문제 특성에 따라 다를 수 있지만 일반적인 유니온파인드에서는 항상 큰 수를 대표 노드로 한다거나 항상 작은 수를 대표 노드로 하는 형식으로 일관된 형태로 유니온을 해주는 것이 좋습니다. 그렇게 하여야 나중에 실제 합쳐진 무리의 대표노드를 찾을 수 있고, 경로 압축등을 쓰는것도 편하기 때문입니다. 새해복 많이 받으세요~
안녕하세요 하루코딩님! 책을 구매하여 매번 좋은 강의 잘 보고 있습니다! 질문드릴 부분이 있는데요, find 매서드에서 제 머리로의 이해는, return parent[a] = find(parent[a]); 이 부분이 재귀를 빠져나오며 parent[a]에 find(parent[a])를 할당하고, 바로 상위 return 값도 방금 전에 할당해준 find(parent[a]) ]로 해주는 로직으로 이해가 되는데, 제 이해가 맞는지 궁금합니다...! 글이 두서없어 보일 수 있는 점 미리 죄송합니다 ㅠㅠ
인건님 안녕하세요 반갑습니다. 네 말씀하신 부분이 맞습니다. 예를들어 아래와 같이 부모노드 배열이 있었다고 생각을 하면 ( 배열의 index가 자신이고 아래 값이 부모노드) 1 2 3 4 5 1 1 2 3 4 여기에서 find(5)를 한다고 가정을 하면 해당 로직에 의해서 find(5) -> find(4) -> find(3) -> find(2) -> find(1) => 1은 index와 값이 같기때문에 현재의 부모 노드로 판단 그럼 자연스럽게 재귀를 빠져나오며 (빠져 나올때는 역순이기 때문에) find(2)에 1을 리턴 -> find(3)에 1을 리턴 -> find(4)에 1을 리턴 -> find(5)에 1을 리턴 // 각각 리턴하면서 1을 부모노드로 저장 결국 find(5)를 하고나서 배열의 값은 아래와 같이 모든 노드가 1번을 부모로 다이렉트하게 바라보는 형태가 됩니다.
안녕하세요 하루코딩님 ! 해당 50 집합표현하기 상에서는 union(1,3)일시 작은 값이 대표 노드로 반환되는데, 51 여행계획짜기 상에서 union(1,2)에서는 큰 값이 대표 노드로 반환된다는 점이 혹시 두 문제 사이에서 어떤 차이가 있어서 발생하는 건지? 코테문제를 풀때 어떤점을 유심히 봐야 차이점을 찾을 수 있는지 궁금합니다 !
안녕하세요. rkdcoding님 반갑습니다 :) 해당 부분은 유니온 파인드에서 큰 수를 대표 노드로 하는 방식으로 손으로 풀기를 한 부분인데, 결론적으로는 어떤 방식으로 풀어도 차이가 없습니다. 말씀을 기준으로 내용을 천천히 봐 보았는데 해당 부분 문구가 오히려 혼란스러우실 수 있으실 것 같다는 생각이 들었습니다. ( 다음 쇄에 설명을 추가 보완 하여야 할 것 같습니다.~. ) 유니온 파인드 알고리즘 자체가 합집합을 만드는 개념이기 때문에 하나로 연결해준다라고 생각해주시면 될 것 같습니다. 다만 문제의 조건에 따라 항상 작은 수를 대표노드로 해야하거나 큰 수를 대표노드로 해야하는 경우가 발생 할 수 있습니다 . 이럴 때는 union 함수안에서 값을 비교하여 연결해 주도록 수정해주시면 됩니다. 아래 기존의 코드에서 - public static void union(int a, int b) { a = find(a); b = find(b); if (a != b) { parent[b] = a; // 해당 부분에서 a값이 더 크면 parent[a] = b; 작으면 parent[b] = a; 이렇게 수정해주시면 항상 작은 수가 대표노드가 되도록 설정됩니다. 큰 수로 하는 것은 반대로 설정하면 되구요 ~ } } 질문해주셔서 감사드리고 오늘도 좋은 하루 되세요 :)
음 혹시 예제 입력 파일 만들어 주실수 있나요??? txt 파일로 예제 입출력 파일을 만들어 주시면 입력 받을 때 따로 클릭 안하고 바로 할수 있을거 같은 데 참고 부탁드립니다 문제 예제만 있으면 될거 같습니다 System.setIn(new FileInputStream("./src/1.txt")); 이런 식으로 값이 들어가면 사용자들이 만족감을 높일수 있다고 생각합니다.
최성현님 안녕하세요. 댓글 감사드립니다. 말씀하신 내용을 제가 정확하게 이해한것이라면 예제를 편하게 테스트 하는 방식을 제안해주신 것으로 이해하였습니다. 보통 말씀하신데로 txt파일로 제공하는 방식이 있는데, 해당 영상에서 다루는 문제는 영상 제일 앞에 설명드린 것처럼 모두 백준 온라인 저지의 문제와 맵핑이 되어있습니다. www.acmicpc.net/problem/1717 때문에 위 영상을 통해 풀이 방법을 익히고 코딩을 해보셨다면 예제의 경우 해당 사이트에서 예제입력1 오른쪽에 복사하기 버튼을 누르시면 바로 복사가 가능하여 로컬에서 테스트 하여 보실 수 있으십니다. 추가로 보통 가장 문제를 푸실 때 스스로 판단이 어려운 부분이 예제는 맞는데 실제 로직이 틀리는 경우입니다. (반례가 있거나..) 이 부분 역시 해당 링크의 코드 제출하기를 통하여 자신의 코드가 모든 경우에도 정답을 출력하는 코드인지 확인이 가능합니다. 답변이 되었는지 모르겠네요. 감사드리고 좋은하루 되십시오!!
작은값을 대표노드로 해야한다 생각해서 아래처럼 min이 쓰일 줄 알았는데
private static void union(int a, int b) {
//대표노드를 찾아서 연결
int ua = find(a);
int ub = find(b);
int max = Math.max(ua, ub);
int min = Math.min(ua, ub);
parent[max] = min;
}
아래 댓글보니
'유니온 파인드 알고리즘 자체가 합집합을 만드는 개념이기 때문에 하나로 연결해준다라고 생각해주시면 되고 결론적으로는 어떤 방식으로 풀어도 차이가 없습니다. '
-> 작은값으로 안해도 연결만 되면 된다는 거죠?
항상 하루코딩 강의 잘보고 있습니다. 감사합니다.
안녕하세요! 반갑습니다.
네 맞습니다. 다만 문제 특성에 따라 다를 수 있지만 일반적인 유니온파인드에서는
항상 큰 수를 대표 노드로 한다거나 항상 작은 수를 대표 노드로 하는 형식으로 일관된 형태로 유니온을 해주는 것이 좋습니다.
그렇게 하여야 나중에 실제 합쳐진 무리의 대표노드를 찾을 수 있고, 경로 압축등을 쓰는것도 편하기 때문입니다.
새해복 많이 받으세요~
안녕하세요 하루코딩님! 책을 구매하여 매번 좋은 강의 잘 보고 있습니다! 질문드릴 부분이 있는데요,
find 매서드에서
제 머리로의 이해는, return parent[a] = find(parent[a]); 이 부분이
재귀를 빠져나오며 parent[a]에 find(parent[a])를 할당하고,
바로 상위 return 값도 방금 전에 할당해준 find(parent[a]) ]로 해주는 로직으로 이해가 되는데,
제 이해가 맞는지 궁금합니다...!
글이 두서없어 보일 수 있는 점 미리 죄송합니다 ㅠㅠ
인건님 안녕하세요 반갑습니다. 네 말씀하신 부분이 맞습니다.
예를들어 아래와 같이 부모노드 배열이 있었다고 생각을 하면 ( 배열의 index가 자신이고 아래 값이 부모노드)
1 2 3 4 5
1 1 2 3 4
여기에서 find(5)를 한다고 가정을 하면 해당 로직에 의해서
find(5) -> find(4) -> find(3) -> find(2) -> find(1) => 1은 index와 값이 같기때문에 현재의 부모 노드로 판단
그럼 자연스럽게 재귀를 빠져나오며 (빠져 나올때는 역순이기 때문에)
find(2)에 1을 리턴 -> find(3)에 1을 리턴 -> find(4)에 1을 리턴 -> find(5)에 1을 리턴 // 각각 리턴하면서 1을 부모노드로 저장
결국 find(5)를 하고나서 배열의 값은 아래와 같이 모든 노드가 1번을 부모로 다이렉트하게 바라보는 형태가 됩니다.
안녕하세요 하루코딩님 !
해당 50 집합표현하기 상에서는 union(1,3)일시 작은 값이 대표 노드로 반환되는데,
51 여행계획짜기 상에서 union(1,2)에서는 큰 값이 대표 노드로 반환된다는 점이 혹시 두 문제 사이에서 어떤 차이가 있어서 발생하는 건지?
코테문제를 풀때 어떤점을 유심히 봐야 차이점을 찾을 수 있는지 궁금합니다 !
안녕하세요. rkdcoding님 반갑습니다 :)
해당 부분은 유니온 파인드에서 큰 수를 대표 노드로 하는 방식으로 손으로 풀기를 한 부분인데,
결론적으로는 어떤 방식으로 풀어도 차이가 없습니다.
말씀을 기준으로 내용을 천천히 봐 보았는데 해당 부분 문구가 오히려 혼란스러우실 수 있으실 것 같다는 생각이 들었습니다.
( 다음 쇄에 설명을 추가 보완 하여야 할 것 같습니다.~. )
유니온 파인드 알고리즘 자체가 합집합을 만드는 개념이기 때문에 하나로 연결해준다라고 생각해주시면 될 것 같습니다.
다만 문제의 조건에 따라 항상 작은 수를 대표노드로 해야하거나 큰 수를 대표노드로 해야하는 경우가 발생 할 수 있습니다 .
이럴 때는 union 함수안에서 값을 비교하여 연결해 주도록 수정해주시면 됩니다.
아래 기존의 코드에서 -
public static void union(int a, int b) {
a = find(a);
b = find(b);
if (a != b) {
parent[b] = a; // 해당 부분에서 a값이 더 크면 parent[a] = b; 작으면 parent[b] = a; 이렇게 수정해주시면 항상 작은 수가 대표노드가 되도록 설정됩니다. 큰 수로 하는 것은 반대로 설정하면 되구요 ~
}
}
질문해주셔서 감사드리고 오늘도 좋은 하루 되세요 :)
@@codingtest 항상 좋은 말씀 감사드립니다 좋은 주말 보내세요 :)
음 혹시 예제 입력 파일 만들어 주실수 있나요??? txt 파일로 예제 입출력 파일을 만들어 주시면 입력 받을 때 따로 클릭 안하고 바로 할수 있을거 같은 데 참고 부탁드립니다 문제 예제만 있으면 될거 같습니다
System.setIn(new FileInputStream("./src/1.txt"));
이런 식으로 값이 들어가면 사용자들이 만족감을 높일수 있다고 생각합니다.
최성현님 안녕하세요. 댓글 감사드립니다.
말씀하신 내용을 제가 정확하게 이해한것이라면 예제를 편하게 테스트 하는 방식을 제안해주신 것으로 이해하였습니다.
보통 말씀하신데로 txt파일로 제공하는 방식이 있는데,
해당 영상에서 다루는 문제는 영상 제일 앞에 설명드린 것처럼 모두 백준 온라인 저지의 문제와 맵핑이 되어있습니다.
www.acmicpc.net/problem/1717
때문에 위 영상을 통해 풀이 방법을 익히고 코딩을 해보셨다면
예제의 경우 해당 사이트에서 예제입력1 오른쪽에 복사하기 버튼을 누르시면 바로 복사가 가능하여 로컬에서 테스트 하여 보실 수 있으십니다.
추가로 보통 가장 문제를 푸실 때 스스로 판단이 어려운 부분이 예제는 맞는데 실제 로직이 틀리는 경우입니다. (반례가 있거나..)
이 부분 역시 해당 링크의 코드 제출하기를 통하여 자신의 코드가 모든 경우에도 정답을 출력하는 코드인지 확인이 가능합니다.
답변이 되었는지 모르겠네요. 감사드리고 좋은하루 되십시오!!
@@codingtest 넵 ㅎㅎ