본문 바로가기

분류 전체보기

 (77)
[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]Random Surfer Trick 동작 확인 이전 포스팅에서 Random Surfer Trick을 직접 구현해 보았다(https://taeminator1.tistory.com/39). 이번 포스팅에서는 실제 출력된 결과를 바탕으로 분석을 해보려고 한다. 이후 등장하는 표의 예제 결과는 repeatNumber를 10만으로 하고(실제 예제에서는 100만으로 하였지만 백분율이어서 10을 나눠 10만으로 표기하였다), surfPossiblity를 15로 설정한 결과이다. 먼저 실행 횟수에 따라 결과에 차이가 있었다. 1000번을 반복할 경우, 실행할 때마다 변화율의 차이가 심했지만, 실행 횟수가 증가할수록 변화율에 큰 변화가 없었다. 변화율의 관점에서 봤을 때, 100000번 정도가 적당한 것으로 판단되어 이후 실행부터 repeatNumber를 10000..
[Swift]Random Surfer Trick 구현 구글의 검색엔진이 어떻게 세계 최강의 자리에 단시간에 오를 수 있었을까?? 존 매코믹은 "미래를 바꾼 아홉 가지 알고리즘"에서 그 이유 중 하나로 "Page Rank" 알고리즘을 꼽는다. 초창기 구글은 검색엔진을 사용하는 사용자에게 유용한 정보를 제공하기 위해, 두 가지 큰 절차를 따랐다. 첫 번째로 인덱싱이고 두 번째가 페이지 랭크이다. 인덱싱은 페이지에 포함되어 있는 단어들(HTML을 구성하는 텍스트들)의 페이지별 위치를 구성하는 기술이고, 페이지 랭크는 사용자가 입력한 내용이 포함된 페이지들 중에 어떤 페이지를 우선적으로 보여줄 것인지(높은 순위로 매길지)에 대한 기술이다. 이번 포스팅에서는 Page Rank의 다양한 알고리즘 중에서 Random Surfer Trick을 구현해 보려고 한다. Ran..

티스토리툴바