Computer Science/데이터 구조 (8) 썸네일형 리스트형 [Swift] Heap을 이용한 Priority Queue 구현 우선순위 큐(Priority Queue)는 이름에서 알 수 있듯이 큐(Queue)의 일종이다. 큐는 지난 포스팅에서 설명한 것과 같이, 먼저 입력된 데이터가 먼저 출력되는 자료구조이다. 이에 반해 우선순위 큐는 출력될 데이터가 입력된 순서에 따라 결정되는 것이 아니라, 우선순위에 따라 이루어진다는 차이가 있다. 우선순위 큐도 다양한 방법으로 구현할 수 있지만, 힙으로 구현하는 것이 적절해 보인다. 배열(Array)이나 연결 리스트(Linked List)로 구현할 경우, 삽입 또는 삭제 연산 시에 데이터의 정렬을 위해 모든 데이터를 순회해야 하기 때문에 시간 복잡도가 O(n)이 소요된다. 하지만 힙의 경우 삽입 또는 삭제 시에 반정렬 상태만 유지하면 되는 완전 이진 트리이기 때문에 시간 복잡도가 O(lb(.. [Swift] Array를 이용한 Heap 구현 3 - 함수형 프로그래밍 힙에 대한 배경 지식 및 구현은 아래 포스팅들을 참고하면 된다. https://taeminator1.tistory.com/43 https://taeminator1.tistory.com/44 길고 긴 여정이었지만, 이제 힙에 대한 구현은 마지막 포스팅이 될 것 같다. 이번 포스팅의 주제는 "다양한 힙 구현하기"이다. 지난 포스팅에서는 "최대 힙"을 구현했지만, 때로는 다른 종류의 힙을 원할 수도 있다. 먼저 최소 힙을 구현하는 방법에 대해 생각해 보자. 간단히 설명하자면, 최소 힙(Min Heap)은 자식 노드의 값이 부모 노드의 값 보다 작지 않은 힙을 말한다. 이러한 힙을 구현하기 위해서는 아래와 같이 이전에 구현한 Heap 클래스에서 몇 개의 부등호의 방향만 변경해 주면 된다. func insert(.. [Swift] Array를 이용한 Heap 구현 2 - 최대 힙 지난 포스팅(https://taeminator1.tistory.com/43)에 이어 이번 시간에는 Swift를 이용해 힙을 실제로 구현해 보겠다. 먼저 힙을 구성하는 노드(연결 리스트에서 사용한 노드와 구별하기 위해 Heap Node라고 이름을 지었다)를 구현해 주겠다. 연결 리스트에서 구현해 준 노드 클래스와 마찬가지로 제네릭을 이용해 다양한 타입에 대응되게 만들었다. 다만 연결 리스트의 노드와 달리 힙 노드는 노드 간에 값을 비교해야 하기 때문에 Comparable 프로토콜을 준수하여 구현하였다. class HeapNode: Comparable { var data: T init(_ data: T) { self.data = data } func getData() -> T { return data } f.. [Swift] Array를 이용한 Heap 구현 1 - 개요 해당 포스팅에 앞서 트리에 대한 전반적인 정리는 이전 포스팅(https://taeminator1.tistory.com/42)을 참고하면 된다. 힙은 단말 노드가 아닌 각각의 노드에 대해 노드의 값이 자식 노드의 값과 비교해 일정한 규칙을 갖는 완전 이진 트리이다. (노드의 값(키)은 중복이 가능하다) 힙은 대표적으로 최대 힙과 최소 힙이 있는데, 자식 노드의 값이 부모 노드의 값 보다 크지 않은 힙을 최대 힙(Max Heap), 자식 노드의 값이 부모 노드의 값 보다 작지 않은 힙을 최소 힙(Min Heap)이라고 한다. 이번 포스팅에서는 특별한 언급이 없다면 최대 힙(각각의 부모 노드의 값이 자식 노드의 값보다 크거나 같은 경우)으로 가정하고 힙에 대한 설명을 이어 나가겠다. 힙의 가장 큰 특징은 반정.. 트리 나무는 뿌리에서 시작하여 줄기를 타고 여러 개의 가지로 뻗는다. 각각의 가지는 다시 여러 개의 가지로 뻗고, 이 과정을 몇 번 반복한다. 그리고 가지의 끝에는 나뭇잎이나 열매가 맺히게 된다. 이러한 나무의 구조와 유사한 형태의 자료구조를 트리라고 한다. 트리도 앞서 설명한 나무의 구조와 마찬가지로 뿌리(root node)를 시작으로 여러 노드로 분기한다. 각각의 노드는 다시 여러 노드로 분기하며 이러한 과정을 반복하게 된다. 그리고 더 이상 노드로 분기하지 않는 노드를 단말 노드(terminal node 또는 leaf node)라고 한다. 앞서 가지에 끝에 달린 나뭇잎이나 열매와 같은 개념이다. 이러한 트리는 계층을 갖는데, 이는 큐나 리스트와 같은 선형 자료 구조와 구별되는 특징이다. 이러한 특징을 이.. [Swift] Linked List를 이용한 List 구현 Queue나 Stack과 같은 자료구조가 끝 단에서 원소를 입출력할 수 있는 것과 달리 List는 임의의 순서의 데이터를 삽입 또는 삭제할 수 있는 자료 구조이다. Queue와 마찬가지로 List도 다양한 방법으로 구현할 수 있지만, 이번 포스팅에서는 Linked List를 이용하여 List를 구현해 보려고 한다. Linked List에 관한 포스팅(https://taeminator1.tistory.com/36)에서 설명한 바와 같이 Linked List를 이용할 경우, 삽입/삭제 연산 시 자료의 이동이 없어 효율적이기 때문이다. Linked List를 이용하여 Queue를 구현했을 때와 마찬가지로 LinkedList의 기능을 포함하므로 상속을 통해 구현해 주었다. 클래스 다이어그램에서 알 수 있듯이, .. [Swift] Linked List를 이용한 Queue 구현 Queue는 먼저 입력된 데이터가 먼저 출력되는 자료구조이다. 이러한 특성을 선입선출(FIFO: First-In Frist-Out)이라고 한다. 이러한 개념은 일상생활에서 쉽게 찾아볼 수 있기 때문에 Queue는 많이 사용되는 자료구조 중 하나이다. Swift에서는 기본적으로 Queue를 제공해 주지는 않아서 별도로 구현해 주어야 한다. 다양한 방법으로 다양한 종류의 Queue를 구현할 수 있는데, Array를 이용한 Queue의 구조를 살펴보자. 먼저 Array를 이용하여 일렬로 쭉 늘어선 모양의 선형 Queue를 구현할 수 있다. Queue에서 가장 먼저 입력된 데이터를 출력하는 함수를 pop이라고 하겠다. pop을 하는 방법에는 크게 두 가지가 있다. 첫 번째로 pop 연산 시에 Array의 첫 번.. [Swift] Linked List 구현 Linked List는 Array와 자주 비교되는 대표적인 자료 구조 중 하나이다. 메모리에 각각의 원소를 순차적으로 저장하는 Array와 달리, Linked List는 데이터와 링크로 구성된 노드를 이용하여 메모리에 저장된 순서와 상관없이 연결된 데이터 구조를 말한다. 각각의 사각형은 Node를 의미한다. Node는 데이터(채색되어 있지 않은 부분)와 링크(채색되어 있는 부분)로 나뉘는데 데이터에는 저장하길 원하는 값을 넣고, 링크에는 다음 노드를 가리키도록 하여 Linked List를 구현할 수 있다. Array와 Linked List는 각각 대비되는 장점이 존재한다. 먼저 Array는 사용이 쉽다. Swift를 포함한 대부분의 언어에서 Array를 기본적으로 제공한다. 특히 Swift의 Array는.. 이전 1 다음
