# Union Find

32개의 포스트

2019 카카오 인턴십 Q4

정확도 통과 코드정확도 + 효율성 통과 코드사실 문제에서 하라는 대로만 구현해도 정확도 테스트는 쉽게 통과할 수 있다. Level4 문제임에도 구현이 술술 되서 제출 누르는 순간 정확도 100점, 효율성 0점.역시 괜히 레벨4가 아니겠구나 싶어서 어떻게 효율성을 올릴수

2021년 5월 2일
·
0개의 댓글

프로그래머스 네트워크

풀이 코드 - union_find풀이 코드 - DFS프로그래머스 DFS 탭에 있었지만 문제와 그림을 읽자마자 union_find 자료구조가 제일 먼저 떠오르는 문제였다. 그래서 DFS로도 풀어보고 union_find 자료구조로도 풀어 보았다.일단 A에서 B로 연결되어

2021년 4월 22일
·
0개의 댓글

[Leetcode] 200. Number of Islands

문제 바로가기Time Complexity: $$O(n_r n_c)$$Space Complexity: $$O(n_r n_c)$$Time Complexity: $$O(n_r n_c)$$Space Complexity: $$O(n_r n_c)$$

2021년 4월 19일
·
0개의 댓글
post-thumbnail

[Algorithm] Union Find 알고리즘 (1) (Disjoint Set)

Union Find 알고리즘임의의 두 Node가 동일한 '상호배타적인 집합(Disjoint Set)'에 속하는 지 판별하는 알고리즘 결론부터 말하자면, 그래프 내에 Cycle이 존재하는 지 여부를 판별하고, Cycle이 존재하면 비효율적인 것으로 판단하여, 최소 연결로

2021년 4월 18일
·
0개의 댓글
post-thumbnail

[알고리즘] Union-Find 알고리즘 (서로소 집합=Disjoint-Set)

Disjoint-Set을 구현할 때 사용하는 알고리즘.집합을 구현하는데 비트 벡터, 배열, 연결리스트를 사용할 수 있으나, 가장 효율적인 트리 구조를 이용하여 구현함.크루스칼 알고리즘에서 그래프의 최소 신장 트리(MST)를 찾는데 활용된다. (정점 연결 및 사이클 형성

2021년 4월 11일
·
0개의 댓글
post-thumbnail

[BOJ 10775] 공항 (Python)

링크처음에는 비행기를 중심으로 1번 ~ 입력받는 gi번 사이의 모든 게이트를 탐색하여 그중 비어있는 게이트에 비행기를 도킹시키려고 하였다. 시간복잡도는 O(GP)로 100,000 x 100,000 = 10,000,000,000 시간초과를 예상하였고, 다른 방법으로 풀려

2021년 4월 11일
·
0개의 댓글
post-thumbnail

[프로그래머스] LV.3 섬 연결하기 (JS)

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를

2021년 4월 10일
·
0개의 댓글

[BOJ 10775] 공항 (Python)

공항처음에 문제가 잘 이해되지 않아 시간이 걸렸는데, 비행기가 주어지면 1~i번 게이트까지는 자유롭게 도킹할 수 있는데, 비행기가 p만큼 들어오면 비행기를 최대한 많이 도킹시키는 것이 목표입니다.비행기가 들어오면 도킹할 수 있는 게이트의 가장 높은 번호로 도킹을 시도합

2021년 4월 9일
·
0개의 댓글

[백준] 4195.친구 네트워크(c++)

4195.친구 네트워크문제 유형 union-find 입력값에 대해 부모에 대한 정보를 찾고 부모가 다르면 합쳐주고 하나의 부모를 보도록 수정.시행 착오! 런타임 에러 (OutOfBounds) : 정보 담는 갯수 2\*n 시간초과 : ios::sync_with_stdio

2021년 4월 6일
·
0개의 댓글

"네트워크" 문제 풀이

서문 이 문제는 프로그래머스에는 DFS, BFS 문제로 분류가 되어있다. 하지만 나는 이 문제를 읽자마자 Union-Find가 떠올랐고 실제로 많은 사람들이 이를 활용하여 문제를 해결했다. 그래서 해당 문제는 유니온 파인드를 활용해서 풀이를 해보았다. 간만에 써보는

2021년 4월 3일
·
0개의 댓글
post-thumbnail

[Algorithm] BaekJoon : 20040. 사이클 게임 by Python

문제 바로가기 https://www.acmicpc.net/problem/20040사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n −

2021년 3월 9일
·
0개의 댓글
post-thumbnail

BOJ :: 여행 가자 (no.1976)

동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를

2021년 2월 25일
·
0개의 댓글
post-thumbnail

BOJ :: 집합의 표현 (no.1717)

초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.집합을 표현하는 프로그램을 작성하시오.첫째 줄에 n(1 ≤ n ≤ 1,000,000

2021년 2월 25일
·
0개의 댓글

[프로그래머스#JS] 섬 연결하기

https://programmers.co.kr/learn/courses/30/lessons/42861

2021년 2월 14일
·
0개의 댓글
post-thumbnail

[백준] 10775번: 공항

union-find

2021년 2월 6일
·
0개의 댓글
post-thumbnail

Kakao - 호텔 방 배정

본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.스노우타운에서 호텔을 운영하고 있는 스카피는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 k개 있으며, 각각의 방은 1번부터 k번까지 번호로 구분하고 있습니다. 처음에는 모든 방이

2021년 1월 30일
·
0개의 댓글

[알고리즘] 서로소 집합(Disjoint Sets)

서로소 집합이란 공통 원소가 없는 두 집합을 의미한다. 그리고 이 개념은 서로소 집합 자료구조로 몇몇 그래프 알고리즘에서 중요하게 사용된다. 서로소 집합 자료구조는 union, find 두가지 연산으로 이루어진다.

2021년 1월 30일
·
0개의 댓글

우주신과의 교감_1774번

황선자씨는 우주신과 교감을 할수 있는 채널러 이다. 하지만 우주신은 하나만 있는 것이 아니기때문에 황선자 씨는 매번 여럿의 우주신과 교감하느라 힘이 든다. 이러던 와중에 새로운 우주신들이 황선자씨를 이용하게 되었다.하지만 위대한 우주신들은 바로 황선자씨와 연결될 필요가

2021년 1월 25일
·
0개의 댓글

[BOJ] 1647번 도시 분할 계획

1647번 도시 분할 계획

2021년 1월 22일
·
0개의 댓글

[BOJ] 1922번 네트워크 연결

1922번 네트워크 연결

2021년 1월 22일
·
0개의 댓글