hyunkookim 님의 블로그

721. Accounts Merge 이 문제는 Union-Find(Disjoint Set) 을 사용하는 대표적인 그래프 문제입니다.각 이메일을 노드로 보고, 같은 사람의 이메일끼리 연결(merge) 해주는 방식입니다.✅ 문제 핵심 정리accounts[i][0]: 이름 (예: "John")accounts[i][1:]: 이메일 주소들공통 이메일이 있으면 같은 사람 → 이메일들을 하나의 집합으로 merge결과는 [이름, 정렬된 이메일 목록] 형식으로 반환✅ 전략Union-Find 구조 생성이메일 간 연결을 Union-Find로 묶기각 이메일의 루트를 기준으로 그룹핑이름을 이메일과 매핑해 최종 결과 구성✅ 전체 코드 (풀 구현 + 설명 주석)class Solution: def accountsMerge(se..

✅ Union-Find (Disjoint Set Union, DSU)란?📌 무엇인가요?여러 개의 서로소 집합(disjoint sets) 을 관리하는 자료구조입니다.주로 그래프에서 사이클을 판별하거나, 네트워크 연결 여부, 클러스터 관리 등에 사용됩니다.✅ 주요 연산 두 가지연산설명find(x)원소 x가 속한 집합의 대표(루트 노드) 를 찾음union(x, y)x와 y가 속한 두 집합을 하나로 합침✅ 최적화 기법Path Compression (경로 압축)find(x) 호출 시, 경로에 있는 노드들을 직접 루트에 연결해서 다음 검색을 빠르게 함Union by Rank / Height집합을 합칠 때, 작은 트리를 큰 트리에 붙임 → 트리 깊이를 줄여 성능 개선✅ 시간복잡도거의 O(1) 에 가깝습니다 (아커만..

684. Redundant Connection https://youtu.be/1lNK80tOTfc  https://youtu.be/FXWRE67PLL0?si=09q1EDMfBhbMNpJk class Solution: def findRedundantConnection(self, edges: List[List[int]]) -> List[int]: # Union-Find 알고리즘으로 사이클을 형성하는 간선을 찾는 함수 # Use Union-Find algorithm to find the edge that creates a cycle. n = len(edges) # 간선의 개수 (Number of edges) # 부모 노드를 저장하는 배열 ..

128. Longest Consecutive Sequence https://youtu.be/8sF5-yK2jsk?si=azgL_NMsGEf7q6pV 기본적으로 정렬을 하면, => 시간 복잡도 O(n log n) 그러나, 문제에서 요구하는 것은, 시간 복잡도 O(n) 임 !! Set 을 사용하여. 속도 개선! class Solution: def longestConsecutive(self, nums: List[int]) -> int: """ time: O(n^3): for + [while + while 안에 in 조건문] O(2n) => O(n) - O(n^2) 으로 보이지만, 자세히 살펴보면, 그렇지 않음!! ..

547. Number of Provinces class Solution: def findCircleNum(self, isConnected: List[List[int]]) -> int: # dfs 로.. # init n = len(isConnected) province = 0 visited = [False]*n def dfs(cur_node_number: int): visited[cur_node_number] = True for neighbor in range(n): if isConnected[cur_node_number][neighbor] == 1 and vi..