서로소 집합(분리 집합) 자료 구조4 [Programmers] 섬 연결하기 https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 문제에서 요구하는 결과값이 최소 신장 트리(minimum spanning tree)의 간선의 가중치의 총합이므로, 최소 신장 트리 알고리즘을 활용하여 문제를 해결하고자 하였다. 구현 간선 데이터가 주어지므로, 유니온-파인드(union-find) 연산을 구현한 다음 크루스칼 알고리즘(Kruskal's algorithm)을 통해 최소 신장 트리를 만들어 가중치의 총합을 구하였다... 2023. 12. 11. [Baekjoon] 1197번: 최소 스패닝 트리 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 문제 해결 과정 착안 최소 (비용) 신장 트리(minimum spanning tree, MST)를 구하는 문제이므로, 이를 구하는 대표적인 알고리즘을 이용하여 문제를 해결하고자 하였다. 문제에서 한 줄씩 간선 데이터를 입력으로 제공하기 때문에, 간선 데이터를 하나씩 저장하면서 정렬하는 것이 문제 해결에 편리할 것 같아서 크루스칼 알고리즘(Kruskal.. 2023. 5. 31. [Baekjoon] 1976번: 여행 가자 https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 문제 해결 과정 착안 도시들이 각각 서로 다른 번호로 구분되고(정수형 데이터), 도시들 사이의 연결 여부가 문제에서 주어지고 있으며 여행 경로에 해당하는 도시를 방문하기 위해 다른 도시를 중복으로 방문이 가능하다. 여행 경로가 주어졌을 때 시작 도시에서 경로 내에 있는 도시들을 방문이 가능한지의 여부만 확인하면 되는 문제이므로, 트리 또는 그래프의 구조를 활용해 탐색을 빠르게 수행하는 것을 목표로.. 2023. 5. 26. [Baekjoon] 1717번: 집합의 표현 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 문제 해결 과정 착안 서로소 집합(분리 집합, disjoint set)을 사용하여, 유니온-파인드(union-find) 연산에 의해 포함 관계를 따지는 문제이므로 해당 자료 구조를 구현하여 문제를 해결하고자 하였다. 구현 이 문제에서는 데이터를 정수형의 기본 자료형이기 때문에 인덱스로 간주하여, 유니온-파인드 연산에서 사용할 부모를 나타내는 정보를 배열에 저장.. 2023. 5. 24. 이전 1 다음
