Algorithm/Union Find (7) 썸네일형 리스트형 (C++) - 백준(BOJ) 14621번 : 나만 안되는 연애 https://www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net kruskal 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 학교 번호를 1번부터 부여, 성별을 함께 저장하기 위해 map을 사용합니다. 만든 연결 그래프(트리)의 정보를 저장하기 위한 인접리스트 graph도 필요합니다. 그 외에 간선이 저장된 edges, bfs탐색을 위한 ck배열, parent배열 등이 필요합니다. 📔 풀이과정 거리의 총합의 최소이므로 .. (C++) - 백준(BOJ) 17471번 : 게리멘더링 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 조합 + union find로 푼 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 n입력 후 일차원 배열 popular에 각 구역의 인구를 입력받습니다. vector 변수 graph로 간선을 입력받고 인접리스트를 형성합니다. 📔 풀이과정 1. 구역을 2곳로 나누기 : 임의로 나눕니다. 한 쪽의 선거구가 정해진다면 자동으로 나머지 구역들로 선거구가 구성됩니다. 따라서 nCi (i = 1 ~ n / 2) 만큼 한 쪽 선거구.. (C++) - 백준(BOJ) 1774번 : 우주신과의 교감 https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 크루스칼 문제였습니다. 📕 풀이방법 1. 입력, 초기화 1-1. n만큼 좌표를 입력받습니다. 1-2. m만큼 이미 연결된 통로를 입력 받습니다. 이미 연결되어 있는 간선들은 트리형태로 구성되어 있습니다. 따라서 parent 배열을 이용해 union를 한다면 독립된 트리들이 한 개 혹은 여러개로 구성됩니다. 2. 서로 연결이 될 수 있는 후보간선들을 edges라는 변수에 .. (C++) - 2019 카카오 개발자 겨울 인턴십 : 호텔 방 배정 https://programmers.co.kr/learn/courses/30/lessons/64063 코딩테스트 연습 - 호텔 방 배정 programmers.co.kr union find 문제였습니다. 풀이방법 이분탐색으로 시행하는 것을 생각할 수 있으나 요청한 방이 이미 있는 방에 경우 배정할 방을 정하기 어렵습니다. 2번방부터 10번방까지 다차있는 경우 2번방에 대한 요청이 들어왔을 때 11번방을 바로주지 못한다면 O(n)의 시간이 걸려 순차적으로 탐색해야하기 때문입니다. 또한 10^12로 k가 매우 크므로 배열로 방 번호를 잡을 수 없습니다. 따라서 map으로 해당방을 이미 이용하는지 아닌지를 알아보는 방법을 선택했습니다. 또한 대체로 줄 수 있는 방번호를 찾을 수 있는알고리즘으로 union - f.. (C++) - 백준(BOJ) 9372번 : 상근이의 여행 www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net unoin find를 이용해 푼 문제였습니다. 풀이방법 1. 생각하기 : 국가의 개수가 n이라면 1 ~ n까지의 국가를 여행해야하기 때문에 국가를 노드로 생각하고 여행하는 경로를 간선이라고 생각해 모든 노드가 연결된, 사이클이 없는 양방향 그래프를 만드는 문제라고 생각할 수 있습니다. 2. union find : parent를 처음에는 다르게 둡니다. find를 이용해 두 .. (C++) - 백준(BOJ) 1922번 : 네트워크 연결 답 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 전체 네트워크 연결비용을 출력하는 문제이므로 크루스칼로 풀었습니다. 풀이방법 1. 간선을 입력받습니다. 2. 간선을 비용 오름차순으로 정렬합니다. 3. 두 정점의 parent가 다르다면 다른 집합이므로 적은 비용의 간선을 추가하고 union(merge)를 해줍니다. 4. 정답(MST 비용)을 출력합니다. Code #include using namespace std; int n, m, ans; int parent[1001]; struct Edge { int u, v, w; }; vecto.. (C++) - 백준(BOJ) 1717번 : 집합의 표현 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net union-find로 풀었습니다. 📕 풀이방법 📔 입력 및 초기화 1. 입출력이 많으니 c와의 동기화를 풀어줍니다. 2. n, m을 입력해줍니다. 3. parent배열을 선언해줍니다. 처음에 i번 원소의 부모는 자기 자신입니다. 이때 번호가 1번부터 시작하므로 n번째까지 loop를 돌며 초기화해줘야 합니다. 3. m번동안 op, a, b를 입력해주며 실행합.. 이전 1 다음