각 노드의 자식노드는 문자열의 최대 경우의수(소문자 26개, 대문자 26개)를 저장하기위해 메모리를 할당해야하므로
메모리가 추가적으로 많이필요하다.
트라이를 코드로 구현하면 다음과 같다.
import Foundation
// 트라이 자료구조
class Trie {
// 트라이의 자식노드 메모리 할당(여기서는 소문자만 취급한다.)
// 소문자의 아스키코드로 접근하기위해서 소문자의 갯수만큼 할당
var child: [Trie?] = Array(repeating: nil, count: 26)
// 해당 노드가 문자열의 마지막인지?
var end = false
// 트라이에 문자열을 넣는다. 외부에서 문자열String을 받음
// 받은 문자열을 한개의 문자들로 나누고 insertCharater함수에 넘겨준다.
// index는 0: 최상단노드부터 추가해주기 위해서
func insert(_ s: String) {
let arr: [Character] = Array(s)
insertCharacter(arr, 0)
}
// 문자 배열과 인덱스를 넘겨받고 실행
func insertCharacter(_ arr: [Character],_ index: Int) {
// 해당 문자열을 모두 입력했다면 현재 노드가 마지막임을 설정하고 종료
if arr.count == index {
self.end = true
return
}
// 아스키코드로 변환 범위: 0...25 (자식노드배열에 넣기위해)
let num = toNumber(arr[index])
// 현재 문자열의 아스키코드로 자식노드를 생성해준다.
// apple을 입력해놓고 avocado를 입력할때, a는 이전에 생성해두었지만, v는 생성해두지 않았기에 생성
if child[num] == nil {
child[num] = Trie()
}
//남은 문자도 트리에 연결하기 위해 재귀호출
child[num]?.insertCharacter(arr, index+1)
}
// 해당 문자를 아스키코드로 변환하지만 0~25 범위에 존재하게끔 소문자의 첫번째 문자 a의 아스키코드를 뺌
func toNumber(_ c: Character) -> Int{
return Int(c.asciiValue! - Character("a").asciiValue!)
}
// 문자열String을 받으면 해당 문자가 존재하는지 bool값 리턴
// 문자열String을 역시 문자배열로 변환하여 내부함수 findCharacter를 실행
func find(_ s: String) -> Bool{
let arr: [Character] = Array(s)
return findCharacter(arr,0)
}
// 문자열이 존재하는지 파악하기위해 재귀호출
func findCharacter(_ arr: [Character],_ index: Int) -> Bool {
// 문자열이 모두 존재하고, 마지막 문자가 끝나는노드라면 true
// 문자열이 모두 존재했지만, 마지막 문자가 끝나지않는 노드라면 false
if arr.count == index {
if self.end { return true }
return false
}
// 해당 문자를 아스키코드로 변환
let num = toNumber(arr[index])
// 해당문자의 자식노드가 존재하지않다면 더 찾을 수 없으므로 false
if child[num] == nil { return false }
// 그다음 문자도 확인
return child[num]!.findCharacter(arr, index+1)
}
}
예시의 deph는 2단계라 바로 루트노드를 출력하지만, 더 깊다면 재귀호출을 통해 해당 집합의 루트노드를 반환한다.
두개의 분리집합을 합치는연산 Union을 사용하면 다음 그림과 같다.
parent
1
1
1
1
1
1
index
1
2
3
4
5
6
Union(1,2): 원소 1이 속한 집합과 원소2가 속한집합을 합친다.
합치는과정은 해당 루트노드가 합치려는 집합의 루트노드로 연결만 해주면된다.
합쳐졌다면 원소2,4,6 또한 루트노드 1을 가리키게 된다.
Union-Find의 시간복잡도는 Union연산은 연결만 해주므로 O(1)이 들지만, Find연산은 트리의 depth 만큼 재귀호출을 하므로
최소 O(1)에서 최대 O(depth)가 걸리게 된다.
이를 코드로 구현해보자.
import Foundation
// Union-Find
// 분리집합을 저장할 배열 parent
// parent[i] = a : i의 부모노드는 a다.
var parent = Array(repeating: 0, count: 7)
// 처음 초기화할땐 자기 자신을 루트노드로 갖는다.
for i in 1...6 {
parent[i] = i
}
// 원소 x가 포함된 집합과 y가 포함된 집합을 합친다.
// 이때 합쳐진 집합의 루트노드는 x의 루트노드가 된다.
func union(_ x: Int, _ y: Int) {
var rootX = find(x)
var rootY = find(y)
parent[rootY] = rootX
}
// 원소 x의 루트노드를 반환한다. (재귀호출)
// 재귀호출은 트리의 depth만큼 실행된다.
func find(_ x: Int) -> Int {
if parent[x] == x { return x}
parent[x] = find(parent[x])
return parent[x]
}
struct Heap<T: Comparable> {
// 힙의 원소를 넣을 배열 선언
// 최대힙,최소힙 정렬함수 선언
private var elements: [T] = []
private let sortFunction: (T,T) -> Bool
// 힙의 인덱스 0 은 사용하지 않는다
// 인덱스 0의 값만 있으면 비어있다고 판단
var isEmpty: Bool {
return elements.isEmpty || elements.count == 1
}
// 루트노드의 원소 출력
var peek: T? {
if self.elements.isEmpty { return nil}
return self.elements[1]
}
// elements[0]을 제외한 원소갯수
var count: Int {
if elements.isEmpty {
return 0
} else {
return elements.count - 1
}
}
// buildHeap() 함수는 힙의 재구성 함수
// 인덱스0은 사용하지 않으므로 임의의 값 넣어서 칸 차지하기
init(elements: [T] = [], sortFunction: @escaping (T,T) -> Bool) {
if !elements.isEmpty {
self.elements = [elements.first!] + elements
} else {
self.elements = elements
}
self.sortFunction = sortFunction
if elements.count > 1 {
self.buildHeap()
}
}
}
// 처음 힙이 선언되었을때 정렬함수를 통해 힙을 구성하는 함수이다.
// diveDown 함수는 입력된 index의 자식노드들과 정렬함수를 통해 값 비교 후 교환하는 함수이다.
// self.element.count / 2 는 노드중 자식노드를 가진 노드들을 전부 탐색한다.
mutating func buildHeap() {
for index in (1...(self.elements.count / 2)).reversed() {
self.diveDown(from: index)
}
}
왼쪽 자식 index = (부모 index) * 2
오른쪽 자식 index = (부모 index) * 2 + 1
부모 index = (자식 index) / 2
// 왼쪽자식노드의 인덱스
func leftChild(of index: Int) -> Int {
return index * 2
}
// 오른쪽자식노드의 인덱스
func rightChild(of index: Int) -> Int {
return index * 2 + 1
}
// 부모노드의 인덱스
func parent(of index: Int) -> Int {
return index / 2
}
힙의 삽입
1. 새로운 노드를 넣을 때, 배열의 마지막에 넣는다.
2. 새로운 노드를 부모노드와 비교하여 교환한다.
3. 부모노드는 새로운 노드의 index / 2 이므로 서로 swap 한다.
// 힙이 비어있다면, 노드 추가 2번 (첫번째 인덱스를 1로 갖기 위해)
// 힙이 비어있지 않다면 배열의 마지막에 노드 추가
// 최대힙, 최소힙 정렬기준에따라 추가된 노드와 부모노드 비교 및 교환
mutating func insert(element: T) {
if self.elements.isEmpty {
self.elements.append(element)
self.elements.append(element)
return
}
self.elements.append(element)
self.swimUp(from: self.elements.endIndex - 1)
}
// 힙의 정렬기준 sortFuction에 따라 부모노드와 자식노드 교환
mutating func swimUp(from index: Int) {
var index = index
while index != 1 && self.sortFunction(self.elements[index], self.elements[self.parent(of: index)]) {
self.elements.swapAt(index, self.parent(of: index))
index = self.parent(of: index)
}
}
힙의 삭제
1. 힙의 루트노드를 마지막 원소와 바꾼다. swap
2. 마지막원소를 꺼내고 루트노드부터 자식노드와 교환한다.
3. 힙을 재구성한다.
// 삭제할 루트노드 출력
// 루트노드와 마지막노드를 바꾼후, 마지막 노드를 꺼낸다.
// 루트노드를 자식노드들과 정렬기준으로 교환
mutating func remove() -> T? {
if self.elements.isEmpty { return nil}
self.elements.swapAt(1, self.elements.endIndex - 1)
let deleted = self.elements.removeLast()
self.diveDown(from: 1)
return deleted
}
// 자식노드들의 인덱스를 가져와 부모노드와 정렬함수를 통해 값 비교후 교환한다.
// 부모노드가 정렬기준으로 자리를 찾을 때 까지 계속 자식노드들과 비교후 교환한다.
mutating func diveDown(from index: Int) {
var higherPriority = index
let leftIndex = self.leftChild(of: index)
let rightIndex = self.rightChild(of: index)
if leftIndex < self.elements.endIndex && self.sortFunction(self.elements[leftIndex], self.elements[higherPriority]) {
higherPriority = leftIndex
}
if rightIndex < self.elements.endIndex && self.sortFunction(self.elements[rightIndex], self.elements[higherPriority]) {
higherPriority = rightIndex
}
if higherPriority != index {
self.elements.swapAt(index, higherPriority)
self.diveDown(from: higherPriority)
}
}
힙의 시간복잡도 ( O(logn) )
- 배열의 최대 최소를 구하면 O(n)이 걸렸지만, 힙에 넣고 정렬한다면 더 빠르게 찾을 수 있다.
Heap 구현 코드
+ index 계산을 위해 첫 원소의 인덱스값을 1로 설정하므로 이에 IsEmpty와 insert부분 수정
import Foundation
struct Heap<T: Comparable> {
var elements: [T] = []
var sortFunction: (T,T) -> Bool
var isEmpty: Bool {
return elements.isEmpty || elements.count == 1
}
var peek: T? {
if elements.isEmpty {
return nil
} else {
return elements[1]
}
}
var count: Int {
if elements.isEmpty {
return 0
} else {
return elements.count - 1
}
}
init(elements: [T] = [], sortFunction: @escaping (T,T) -> Bool) {
if !elements.isEmpty {
self.elements = [elements.first!] + elements
} else {
self.elements = elements
}
self.sortFunction = sortFunction
if elements.count > 1 {
self.buildHeap()
}
}
func leftChild(of index: Int) -> Int {
return index * 2
}
func rightChild(of index: Int) -> Int {
return index * 2 + 1
}
func parent(of index: Int) -> Int {
return index / 2
}
mutating func swimUp(from index: Int) {
var idx = index
while idx != 1 && self.sortFunction(self.elements[idx], self.elements[parent(of: idx)]) {
self.elements.swapAt(idx, self.parent(of: idx))
idx = self.parent(of: idx)
}
}
mutating func insert(element: T) {
if self.elements.isEmpty {
self.elements.append(element)
self.elements.append(element)
return
}
self.elements.append(element)
self.swimUp(from: self.elements.endIndex - 1)
}
mutating func diveDown(from index: Int) {
var higherPriority = index
let leftIndex = self.leftChild(of: index)
let rightIndex = self.rightChild(of: index)
if leftIndex < self.elements.endIndex && self.sortFunction(self.elements[leftIndex], self.elements[higherPriority]) {
higherPriority = leftIndex
}
if rightIndex < self.elements.endIndex && self.sortFunction(self.elements[rightIndex], self.elements[higherPriority]) {
higherPriority = rightIndex
}
if higherPriority != index {
self.elements.swapAt(index, higherPriority)
self.diveDown(from: higherPriority)
}
}
mutating func buildHeap() {
for i in (1...(self.elements.count / 2)).reversed() {
self.diveDown(from: i)
}
}
mutating func remove() -> T? {
if self.isEmpty {
return nil
}
self.elements.swapAt(1, self.elements.endIndex - 1)
var returnValue = self.elements.removeLast()
self.diveDown(from: 1)
return returnValue
}
}
