자료구조

Heaps Heap은 트리를 기반으로 한 자료구조로써, 우선 순위 큐를 위하여 만들어진 자료구조입니다. 이번 장에서는 힙을 만들고 조작하는 법에 대해 배울 것입니다. What is heap? Heap은 이진 힙(binary heap)이라고도 알려져 있는 완전 이진 트리(complete binary tree)로써, 배열을 통해 생성할 수 있습니다. *Heap과 memory heap은 다른 것이니 주의하십시오. Heap에는 두 가지의 특징이 있습니다. Max heap : 더 높은 값을 가진 요소가 더 높은 우선순위를 가지는 힙입니다. Min heap : 더 낮은 값을 가진 요소가 더 높은 우선순위를 가지는 힙입니다. The heap property Heap에는 항상 만족해야 하는 중요한 특징이 있습니다. 이..

Trie Trie는 영어 단어와 같이 컬렉션으로 나타낼 수 있는 데이터를 저장하는 데 특화된 트리입니다. 각 문자열 문자는 마지막 노드(점으로 표시됨)가 끝나는 노드에 매핑됩니다. trie의 이점은 접두사가 일치한다는 맥락에 있습니다. Example class EnglishDictionary { private var words: [String] func words(matching prefix: String) -> [String] { words.filter { $0.hasPrefix(prefix) } } } words(matching:)은 문자열의 컬렉션을 탐색하여 접두사가 일치하는 문자열을 반환할 것입니다. 이 알고리즘은 단어 배열이 적을 때 합리적입니다. 하지만 만약 몇 천 단어를 다룰 때는 비합리적이..

AVL Trees 지난 챕터에서 O(log n)의 시간 복잡도를 가진 BST에 대해 배웠습니다. 하지만 O(n)의 성능까지 내려가는 불균형한 트리에 대해서도 배웠습니다. 1962년에 Georgy Adelson-Velsky와 Evgenii Landis는 AVL Tree라는 스스로 균형을 잡는 BST를 고안해내었습니다. Understanding balance 균형잡힌 트리(balanced tree)는 BST의 성능에서 매우 중요한 요소입니다. 이번 섹션에서 균형의 주요 특징에 대해 배워볼 예정입니다. Perfect balance BST의 가장 이상적인 형태는 “완전히 균형잡힌(perfectly balanced)” 상태입니다. 기술적인 관점에서, 모든 층의 트리가 노드로 차있는 것을 의미합니다. 트리가 완벽하..

[Silver II] 앵무새 - 14713 문제 링크 성능 요약 메모리: 72104 KB, 시간: 64 ms 분류 자료 구조, 구현, 큐, 문자열 제출 일자 2024년 1월 1일 11:10:47 문제 설명 자가용 비행기를 타고 세계 일주를 하던 pps789와 cseteram은 어느 날 엔진 고장으로 인해 이름 모를 섬에 불시착하게 된다. 그들은 이 섬을 탐험하는 도중 아주 신기한 사실을 알게 되었는데, 바로 이 섬에 사는 앵무새들은 놀라울 정도로 인간의 말을 흉내 내는 데 뛰어나다는 것이다. 그들은 서로 떨어져 섬을 탐험하기로 하였으며, 필요하다면 앵무새를 이용해 서로에게 연락하기로 약속하였다. 1개월 후, pps789는 섬의 비밀을 밝힐 결정적인 증거를 찾게 된다. 그는 이 세기의 대발견을 cseter..

[Silver IV] 큐 - 10845 문제 링크 성능 요약 메모리: 69376 KB, 시간: 28 ms 분류 자료 구조, 큐 제출 일자 2023년 12월 31일 16:50:53 문제 설명 정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 여섯 가지이다. push X: 정수 X를 큐에 넣는 연산이다. pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 큐에 들어있는 정수의 개수를 출력한다. empty: 큐가 비어있으면 1, 아니면 0을 출력한다. front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. back: 큐..

Binary Search Trees Binary search tree(BST)는 빠른 탐색, 삽입,제거 연산을 용이하게 해주는 자료 구조입니다. 한 쪽을 선택하면 다른 쪽의 가능성을 완전히 배제하여 문제를 반으로 줄여주는 것이 대표적인 특징입니다. 결정을 내리고 분기(브랜치)를 선택하였으면, 뒤로 돌아갈 수 없습니다. leaf node로 갈 때까지(마지막 선택을 할 때까지) 계속 진행됩니다. BST는 binary tree에서 2가지의 규칙을 추가합니다. 왼쪽 자식은 부모보다 값이 작아야합니다. 오른쪽 자식은 부모와 값이 같거나, 더 커야합니다. BST는 위의 특징을 통해 불필요한 확인을 하지 않아 성능을 높여줍니다. 탐색, 삽입, 제거는 평균 O(logn)의 시간 복잡도를 가지는데, 이는 배열과 링크드 ..

Binary Trees 이진 트리(Binary tree)는 각각의 노드가 최대 2명의 자식을 가질 수 있는 트리이며 이들을 왼쪽, 오른쪽 자식이라고 부르는 부르는 특징이 있습니다. Binary tree는 많은 트리 구조와 알고리즘의 근간이 되기 때문에 이번 장에서는 가장 중요한 트리 선회 알고리즘에 대해 배울 것입니다. Implementation public class BinaryNode { public var value: Element public var leftChild: BinaryNode? public var rightChild: BinaryNode? public init(value: Element) { self.value = value } } 위 식을 실행한 예시는 다음과 같습니다. var tr..

Tree Tree(트리)는 매우 중요한 자료구조로 계층적 관계, 정렬된 데이터 관리, 빠른 검색 연산 등 소프트웨어 개발에서 많이 사용됩니다. 크기와 모양에 따라 다양한 타입의 트리가 존재합니다. 용어 Node 연결 리스트와 같이 트리는 노드로 구성되어 있습니다. 각각의 노드는 데이터를 포함하고 있으며, 자식 노드에 대해 알고 있습니다. Parent and child 트리는 위에서 아래 방향으로 뻗어나갑니다. 모든 노드들은 (가장 상단의 노드를 제외하고) 바로 위에는 정확히 하나의 노드와 이어져있습니다. 이 노드를 부모 노드라고 하고, 바로 밑에 연결되어 있는 노드는 자식 노드라고 합니다. 트리에서는 모든 자식은 하나의 부모를 가집니다. Root 가장 상단의 노드를 root라고 부릅니다. 유일하게 부모가..