[Algorithm] 자료구조 - Swift와 알아보는 자료구조의 종류

알고리즘을 공부하다 보니 자료구조에 대한 기본기를 다져야겠다고 생각했다. 앱을 개발하면서도 데이터를 구성할 때 막연하게 구성한 느낌이 난다. 항상 데이터를 구성하면서 느낀 점은 나중에 구조를 바꿀 때 정말 골치가 아프다는 점인데, 이렇게 하나하나 자료구조에 대한 공부를 통해 처음 앱을 구성할 때 이유 있는 데이터 구성을 하고자 자료구조에 대한 공부를 시작하게 되었다.

 

자료구조란?

자료구조(data structure)란 컴퓨터 과학에서 효율적인 접근 및 수정을 가능하게 하는 자료의 조직, 관리, 저장을 의미한다. 데이터 값의 모임, 관계, 데이터에 적용할 수 있는 함수나 명령을 의미한다. 실행시간, 메모리 용량을 최소화시켜 정확하게 원하는 데이터에 접근할 수 있게 적절한 자료구조의 선택을 해야 한다.

 

자료구조의 종류

배열, 리스트, 해시 테이블, 스택, 큐, 그래프, 트리 정도로 처음에 접근하면 좋을 것 같다고 생각했다. 각각 아주 간단하게 알아보자.

 

배열 (Array)

가장 기본적이고 자주 쓰는 구조라고 볼 수 있다. index 대응하는 데이터들로 연속된 메모리 공간에 이루어진 자료구조이다. 다소 생소하다고 느끼는 점은 프로그래밍 언어에서는 배열의 index는 1이아닌 0부터 시작한다. C언어에서 메모리 주소를 계산할 때, 연속된 메모리 공간의 시작주소를 계산하기 위해서 첫 번째 요소를 0으로 인덱싱하는 방식을 채택한 것이라고 한다. 그리고 이러한 관행이 현대 프로그래밍까지 이어지면서 index를 0으로 하게 되었다고 한다.

 

따라서 인덱스를 안다면 데이터 주소를 바로 알기 때문에 해당 데이터를 O(1)의 복잡도로 접근이 가능하다. 하지만 데이터들이 쌓여있기 때문에 데이터의 추가 삭제를 위해서는 연속된 메모리 공간에 넣기 위해서 다른 데이터들을 옮겨줘야 하는데 이때 시간복잡도는 O(N)이다. 추가의 경우 나머지들을 뒤로 미뤄야 하는 상황이기 때문에 시간복잡도는 O(N)이다.

 

Swift에서는 아래와 같은 방식으로 데이터를 추가 혹은 제거가 가능하다.

var array = [1, 2, 3, 4, 5]

array.append(6) // O(1)
array.remove(at: 2) // O(n)
array.insert(2, at: 2) // O(n)

 

리스트 (List)

리스트는 연결을 통해 순서가 있지만 연속적으로 저장되어 있지 않는 데이터 구조다.

 

리스트 데이터의 추가, 삭제는 앞 뒤 데이터의 연결성만 제거해 준다면 쉽게 추가나 삭제가 가능하지만, 원하는 데이터까지 접근하기 위해서는 연결된 이전의 데이터를 통해 접근해야 하기 때문에 시간복잡도가 O(N)이 된다. 이를 정확하게는 연결 리스트라고 한다. 만약 맨 마지막 데이터와 첫 데이터가 연결되었다면 원형 연결 리스트, 앞뒤가 서로 연결되어 있으면 이중 연결 리스트가 된다.

원형 연결 리스트

이중 연결 리스트

 

이것은 Swit에서는 따로 구현을 해야하는데 단순한 연결리스트를 구현하고자 한다면 아래와 같이 구현이 가능하다. 연결방법에 따라서 

class LinkedList<T> {
    var value: T
    var next: LinkedList?
    
    init(_ value: T) {
        self.value = value
    }
}

let list1 = LinkedList(1)
let list2 = LinkedList(2)
let list3 = LinkedList(3)

list1.next = list2
list2.next = list3

 

 

해시 테이블 (Hash table)

키와 데이터가 연결되어 있는 구조이다. 해싱이란 해시테이블 관점에서 보자면 키값을 가져와 고유한 숫자 및 문자 문자열을 생성하게 된다. 아래는 정말 예시이다.

 

이러한 해싱 구조로 데이터를 저장하게 된다면 해시 함수를 한번 수행하며 매우 빠르게 데이터를 저장, 삭제, 조회할 수 있기 때문에 이러한 과정에서 시간복잡도는 O(1)이다.

해시 테이블

 

Swift에서는 Dictionary를 통해 이러한 자료구조를 만들 수 있다. Swift에서는 만약 키값에 대응하는 값이 저장이 되어있지 않다면 nil, 값이 있다면 Optional(값) 형태로 값을 가져올 수 있다.

var dictionary = ["A": 1]
let a = dictionary["A"]
let b = dictionary["B"]

print(a) // Optional(1)
print(b) // nil

dictionary["B"] = 2
let c = dictionary["B"]
print(c) // Optional(2)

 

스택 (Stack)

스택은 기본적으로 데이터가 층층이 쌓인다고 생각하면 쉽다. 스택에서 가장 중요한 개념인 LIFO(Last-In-First-Out)이 핵심이다.

이를 스위프트에서는 아래와 같이 구현되어 있다. 순서대로 쌓이고 popLast()를 통해서 옵셔널 형태로 데이터를 추출할 수 있다. 맨 마지막에 들어온 3이 추출되게 된다.

// 스택 선언
var stack: [Int] = []

// 데이터 넣기
stack.append(1)
stack.append(2)
stack.append(3)

print(stack) // [1, 2, 3]

// 데이터 추출
let poped = stack.popLast()

print(stack) // [1, 2]
print(poped) // Optional(3)

 

큐 (Queue)

큐의 경우는 데이터가 줄을 서있다고 생각하면 쉽다. 맨 처음 서있는 사람이 우선순위이듯이 FIFO(First-In-First-Out)의 형태로 데이터를 꺼낼 수 있다.

이를 스위프트에서는 아래와 같이 구현되어 있다.

// 큐 선언
var queue: [Int] = []

// 데이터 넣기
queue.append(1)
queue.append(2)
queue.append(3)

print(queue) // [1, 2, 3]

// 데이터 추출
let dequeued = queue.removeFirst()

print(dequeued) // 1
print(queue) // [2, 3]

 

하지만 스택과 큐는 단순히 구현에 불과하고 언제든지 배열의 앞의 데이터나 뒤의 데이터를 추출할 수 있다.

 

그래프 (Graph)

그래프는 노드(node)와 노드를 연결하는 간선(edge)으로 이루어진 자료 구조이다.

아주 간단하게 위의 그림을 구현하자면 아래와 같다.

class Graph {
    var list: [Int: [Int]] = [:]
    
    func addEdge(from: Int, to: Int) {
        if list[from] == nil {
            list[from] = []
        }
        list[from]?.append(to)
    }
}

let graph = Graph()
graph.addEdge(from: 1, to: 1)
graph.addEdge(from: 1, to: 4)
graph.addEdge(from: 2, to: 4)
graph.addEdge(from: 3, to: 2)
graph.addEdge(from: 3, to: 4)

print(graph.list) // [1: [1, 4], 3: [2, 4], 2: [4]]

 

트리 (Tree)

트리는 그래프 자료구조의 한 형태이며, 한 노드에서 쭉 이어지면서 자기 자신에게 안 돌아오는 연결 그래프를 나타낸다. 최상위의 노드를 루트 노드(root node)라고 하고, 위는 부모 노드(parent node) 아래로는 자식 노드(child node)라고 한다. 자식 노드가 없는 노드를 잎 노드(leaf node)또는 말단 노드(terminal node)라고 한다. 물론 트리 자료 구조에는 많은 종류들이 있지만 이것은 좀 더 공부가 많이 필요한 부분인 것 같다.

 

정말 간단하게 구현해 본다면 아래와 같이 구현해 볼 수 있다.

class TreeNode<T> {
    var value: T
    var left: TreeNode?
    var right: TreeNode?
    
    init(_ value: T) {
        self.value = value
    }
}

let rootNode = TreeNode(1)
rootNode.left = TreeNode(2)
rootNode.right = TreeNode(3)

print(rootNode.value)

 

이렇게 간단하게 자료구조의 기본을 알아봤는데, 배열, 리스트, 해시 테이블의 기본적인 자료구조부터 시작해서 어떠한 방식으로 데이터를 추가, 삭제하느냐에 따라서 스택, 큐로 나뉘고 어떠한 방식으로 데이터가 연결되느냐에 따라서 그래프, 트리로 나눠진다는 것을 알았다. 데이터 구조에서 중요한 것은 원하는 데이터를 얼마나 빠르게 찾을 수 있느냐가 관건인 것 같다. 이를 위해서 좀 더 각 자료구조에 대한 깊은 공부가 필요하다고 생각했다.