서론
현재 IT 업계에서는 알고리즘과 자료 구조에 대한 이해가 필수적입니다. 특히 취업을 준비하는 개발자라면 이러한 지식을 바탕으로한 문제 풀이 능력을 갖추어야 합니다. 이번 강좌에서는 ‘유니온 파인드’ 알고리즘에 대해 자세히 알아보고, 이를 활용한 문제 풀이 과정을 단계별로 설명하겠습니다.
유니온 파인드란?
유니온 파인드는 주로 집합의 연산을 처리하는 데 사용되는 데이터 구조로, 두 가지 주요 연산을 지원합니다:
- Union: 두 개의 집합을 합치는 연산
- Find: 특정 원소가 어떤 집합에 속해 있는지를 찾는 연산
이 데이터 구조는 서로소 집합(Disjoint Set) 문제를 해결하는 데 유용하게 사용됩니다. 유니온 파인드는 최적화 기법으로 ‘경로 압축(Path Compression)’과 ‘랭크(Rank)’를 사용하여 효율성을 높입니다.
문제 정의
문제를 정의하기 위해 가상의 상황을 설정해 보겠습니다.
문제: N개의 원소가 있을 때, 여러 쌍의 원소에 대해 같은 집합에 속하는지를 판단하는 프로그램을 작성하라.
원소의 수 N과 쌍의 수 M이 주어진다. 각 쌍에 대해 ‘같은 집합에 속한다’면 “YES”, ‘다른 집합에 속한다’면 “NO”를 출력해야 한다.
문제 예시
입력:
5 4
1 2
1 3
2 3
4 5
1 4
출력:
NO
YES
위 예시에서, 첫 번째 쌍(1, 4)는 서로 다른 집합에 속하므로 “NO”, 두 번째 쌍(1, 4)는 같은 집합에 속하므로 “YES”가 출력됩니다.
유니온 파인드 알고리즘 구현
이제 유니온 파인드 알고리즘을 스위프트로 구현해 보겠습니다. 기본적인 개념을 반영하여 코드를 작성해 보겠습니다.
class UnionFind {
private var parent: [Int]
private var rank: [Int]
init(size: Int) {
self.parent = Array(0.. Int {
if p != parent[p] {
parent[p] = find(parent[p]) // 경로 압축
}
return parent[p]
}
func union(_ p: Int, _ q: Int) {
let rootP = find(p)
let rootQ = find(q)
if rootP != rootQ {
if rank[rootP] > rank[rootQ] {
parent[rootQ] = rootP
} else if rank[rootP] < rank[rootQ] {
parent[rootP] = rootQ
} else {
parent[rootQ] = rootP
rank[rootP] += 1
}
}
}
}
문제 해결 과정
문제를 해결하기 위해 다음과 같은 단계를 따르겠습니다.
- 입력을 파싱하여 N개의 원소 수와 M개의 쌍 수를 얻습니다.
- UnionFind 클래스를 사용하여 원소들의 집합을 관리합니다.
- 각 쌍에 대해 union 연산을 수행하여 집합을 합칩니다.
- 각 쌍의 find 연산을 수행하여 결과를 출력합니다.
코드는 다음과 같습니다.
import Foundation
let input = readLine()!.split(separator: " ").map { Int($0)! }
let n = input[0]
let m = input[1]
let unionFind = UnionFind(size: n + 1)
for _ in 0..
결론
이번 강좌에서 유니온 파인드 알고리즘의 이론적 배경과 문제 해결 과정을 스위프트로 구현해 보았습니다. 유니온 파인드는 그래프 관련 문제에서 매우 유용한 자료 구조 중 하나입니다. 이러한 자료 구조를 활용하면 복잡한 문제를 효과적으로 해결할 수 있습니다.
계속해서 다양한 알고리즘을 탐구하며 여러분의 코딩 테스트 준비에 도움되기를 바라며, 다음 강좌에서 다른 알고리즘을 소개할 수 있도록 하겠습니다.