집합2 [프로그래머스] 섬 연결하기 (Python) - 유니온 파인드 알고리즘 문제 설명https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 코드 구현# 실패 - 사이클을 감지하지 못함대표 예시는 통과했지만, 막상 제출하고 보니 대부분의 테스트 케이스를 통과하지 못한 저의 첫 번째 풀이입니다. 어디서부터 잘못됐는지 확인하기 위해 문제를 다시 읽어보니, 이 코드로는 사이클을 감지하지 못한다는 점을 깨달았습니다. 처음에는 최소 비용만을 고려한 단순한 트리 문제라고 생각했지만, 본질은 최소 신장 트리(MST)였던 것이죠. def solution(n, costs): ans.. 2025. 4. 10. [집합] 개념 정리 (Feat. 유니온-파인드 알고리즘) 집합 개념 유니온-파인드 알고리즘 유니온-파인드 알고리즘 구현파인드 알고리즘 (부모 노드를 찾기!)현재 노드에서 부모 노드를 확인합니다. 부모 노드가 루트 노드이면 파인드 연산을 종료합니다.파인드 연산이 종료되지 않았다면, 위 과정을 반복합니다. 유니온 알고리즘 (랭크 기반으로 합치기!)두 노드의 루트 노드를 확인합니다.루트 노드의 랭크를 비교합니다.랭크 값이 다르면, 랭크 값이 큰 루트 노드를 기준으로 삼아, 랭크가 더 큰 노드를 랭크가 작은 루트 노드의 부모 노드로 바꿉니다. 트리의 깊이는 더 깊어지지 않기 때문에, 랭크 값은 변하지 않습니다.랭크 값이 같다면, 루트 노드를 아무거나 선택해서 바꾸고 최종 루트 노드의 랭크에 1을 더합니다. """[간단한 유니온-파인드 알고리즘 구현하기]상호배타적 집합.. 2025. 4. 9. 이전 1 다음
