union-find8 [leetcode] 1632. Rank Transform of a Matrix 문제 : https://leetcode.com/problems/rank-transform-of-a-matrix/ m x n 크기의 배열이 있을 때, 이들의 랭크를 매긴 배열을 반환하라. 순위는 1부터 시작하며 두 개의 요소 p, q가 같은 행 혹은 같은 열에 있으면 아래와 같은 규칙에 따라 순위를 매긴다. 1. p q : rank(p) > rank(q) 랭크는 가능한한 작게 매겨져야 한다. 예시 4를 보자. 7 3 6 1 4 5 9 8 2 만약 배열의 모든 수가 유니크한 수를 가진다면 정답을 구하기는 생각보다 간단하다. 요소 값을 기준으로 오름차순 정렬한다. 요소값(x, y) 1 (1,0) -> 2.. 2021. 8. 12. [leetcode] 684. Redundant Connection 문제 : https://leetcode.com/problems/redundant-connection/ n개의 노드와 n개의 간선으로 이루어진 무방향 그래프가 주어질 때, n개의 노드로 이루어진 트리가 될 수 있도록 제거해야 하는 간선을 구하여라. 조건에 그래프들은 연결되어 있고 노드가 n개인데 간선도 n개라고 하니, 트리의 특징 중 하나인 간선의 개수는 정점 개수 - 1 이다.를 생각하면 정답이 되는 간선은 1개가 나올 수 있고. 이 간선은 사이클을 만듬을 알아낼 수 있다. 크루스칼 알고리즘 구현에서 사이클이 생성됨을 알아내기 위해 유니온 파인드를 사용했었다. 이를 응용하여, 입력으로 주어지는 간선들을 Union-Find 의 Union 연산으로 하나의 집합으로 합치면서 이미 같은 집합인데 Union 연산.. 2021. 6. 26. 유니온 파인드(Union-Find) 유니온 파인드(Union-Find)는 집합을 표현하기 위한 자료구조입니다. 이를 표현하기 위해 트리에서 부모노드를 저장하는 배열을 만듭니다. 부모노드가 없는 루트노드인 경우는 자기자신을 저장합니다. 이때 최상위 부모노드가 같은 값들이 같은 집합에 속하게 됩니다. [그림 1]에서는 1, 2, 3이 같은 집합. 4, 5가 같은 집합입니다. 주의할 점은, 부모노드가 아닌 최상위 부모노드가 같은 노드들이 같은 집합에 속합니다. [그림 2]에서 노드 4와 노드 2는 모두 같은 집합에 속하지만 부모노드 배열만 봐서는 같은 집합에 속하는지 알 수 없습니다. 같은 집합에 속하는지 알기 위해서는 각 노드들의 최상위 부모노드 배열을 알아야 합니다. 노드 4의 부모노드는 3이지만 최상위부모노드는 1이 됩니다. 다른 노드들의.. 2021. 6. 26. [Programmers] 섬 연결하기 문제 : https://programmers.co.kr/learn/courses/30/lessons/42861 오랜만에 푸는 최소신장트리문제~ 크루스칼 알고리즘으로 풀었다. 먼저 cost 오름차순으로 costs 배열을 정렬한다. costs 배열을 탐색하면서 Union-Find로 해당 간선을 연결하면 사이클이 생기는지 확인한다. 만일 두 정점의 부모노드가 같다면 연결하면 사이클이 생기기 때문에 해당 간선을 선택하지 않는다. 두 정점의 부모노드가 다르면 해당 간선을 연결해도 사이클이 생기지 않기 때문에 해당 간선을 선택하고 해당 간선의 비용을 정답에 더해준다. 시간복잡도는 간선들을 오름차순 정렬하는데 드는 시간인 O(ElogE) 소스코드 : https://github.com/fpdjsns/Algorithm/.. 2021. 6. 14. [Leetcode][128] Longest Consecutive Sequence 문제 : leetcode.com/problems/longest-consecutive-sequence/ 정렬되지 않은 nums 배열이 주어질 때 요소들 중 가장 긴 연속 요소들(ex, 1 2 3 4)의 길이를 구하라. Union find 로 풀었다. nums 배열을 앞에서부터 탐색하면서 탐색중인 숫자를 num이라 할 때, num-1, num+1이 나타난적 있는지 확인한다. 만일 num-1이 이전에 나왔던 숫자라면 num-1와 num의 연속적인 수 중 가장 작은 수들을 가져온다. 이는 부모배열에 저장되어야 한다.(find로 찾는다.) 찾은 부모노드가 다르다면 뒤에 있는 부모노드(num의 부모)를 앞에 있는 부모노드(num-1의 부모)로 갱신하고 연속적인 수들의 최대 길이를 갱신한다.. (union 함수) 다.. 2021. 1. 6. [leetcode][1319] Number of Operations to Make Network Connected 문제 : https://leetcode.com/problems/number-of-operations-to-make-network-connected/ 컴퓨터의 총 개수와 네트워크 연결 여부를 저장한 배열이 주어졌을 때, 모든 컴퓨터들이 네트워크에 연결하기 위해 이동이 필요한 네트워크 연결 수 를 반환하는 문제. (불가능하다면 -1) 최소 신장 트리의 간선 수는 N-1개이다. 비슷하게 이 문제에서 불가능한 네트워크 개수는 컴퓨터의 총 개수 - 1 보다 작은 경우들이다. 이 경우를 만족한다면 모든 컴퓨터들이 네트워크에 연결이 가능하다. Union-Find를 이용해서 네트워크 번호를 하나의 배열에 저장한다. 즉, a, b 컴퓨터가 같은 네트워크에 있다면 배열[a], 배열[b]는 같은 값을 가진다. 네트워크 배열.. 2020. 3. 7. 이전 1 2 다음
