Computer Science/DataStructure
-
Queue in SwiftComputer Science/DataStructure 2021. 2. 5. 14:45
- 선형 자료구조 - FIFO (선입선출) - 구현 - LinkedList - DoubleStack Swift에서는 Queue와 LinkedList를 기본 자료구조로 제공하지 않고 있는데요, array를 사용해 queue를 만들면 enqueue 작업이 O(n)이 걸려서 비효율적입니다. 특히 코딩테스트 문제를 풀다보면 queue가 필요한 상황이 많기 때문에 미리 알아두고 구현해둔다면 좋겠죠? 오늘은 간단하게 Queue 에 대해 알아보고 swift에서는 어떻게 구현할 수 있을지 알아보겠습니다. LinkedList를 사용한 구현과, stack 두 개를 사용한 doubleStack 구현을 알아볼텐데요, LinkedList는 제가 구현해서 그런지 doubleStack과 복잡도 차이가 꽤 나더라구요... 😢 코딩테..
-
TreeComputer Science/DataStructure 2021. 1. 14. 18:00
- 객체간의 계층적인 관계를 나타낸다 - 빠르고 효율적으로 탐색할 수 있다 - 데이터의 정렬된 형태를 보여준다 - 사이클이 없는 그래프 - 텍스트의 prefix 매칭을 빠르게 할 수 있다. ex) - 회사나 정부의 조직 구조 - 나라, 지방, 시•군별 등 계층적인 데이터 - 인덱스 오늘은 기본적이지만 아주 중요한 Tree에 대해 알아보겠습니다. Tree 자체보다도 여기서 파생된 트리들이 더 중요하지만 그래도 기본부터 정리해보려고 해요 :) 자료구조란 데이터들을 잘 관리하게 생겨났을텐데요, 트리는 왜, 언제 필요할까요? 트리는 계층적인 관계를 나타내기 위해 사용합니다. 계층 관계는 우리 일상 생활과 아주 많이 밀접해있습니다. 먼저 우리 가족의 관계도를 그려본다고 생각해봅시다. 부모님 형제 자매가 있고, 다..
-
StackComputer Science/DataStructure 2020. 3. 3. 14:54
- 선형 자료구조 - LIFO (후입선출) 선형 자료구조의 일종. Last In First Out (LIFO) 방식으로, 나중에 들어온(push) 원소가 먼저 나온다.(pop) 접시를 위로 쌓아놓은 형태를 떠올리면 쉽다. 따라서 스택의 앞에 원소를 넣는 것은 O(n)이고 스택의 뒤에 추가하는 것은 O(1)의 시간복잡도를 갖는다. 참고로 CPU는 function 이나 method의 return 주소를 스택에 넣는데, 재귀 함수 등과 같이 함수가 종료되기 전에 너무 많은 함수를 호출해 CPU의 스택이 부족해지면 "stack over flow"가 발생한다. Implement Swift는 사실상 내부적으로 Stack을 이미 지원하고 있다고 볼 수 있다. public struct Stack { fileprivat..
-
HeapComputer Science/DataStructure 2019. 12. 31. 20:32
Heap 이란? 힙은 루트에 가장 힙한 녀석을 두는 이진 트리이다. (응?) 루트에 항상 최대 또는 최소값을 두기 때문에 최대 최소값을 빠르게 얻을 수 있다. O(1) 힙은 완전 이진트리의 모습을 띄는데, 부모 노드가 자식 노드보다 크거나(최대힙) 작은지(최소힙) 만을 보장한다. 즉, 자식노드 끼리는 큰지 작은지를 비교할 수가 없다. 힙은 배열로 구현하면 공간, 시간 복잡도 측면에서 좋기 때문에 배열로 많이 구현한다. 배열로 구현했을 때 다음과 같이 인덱스를 구할 수 있다. parent: floor((i-1) / 2) left: 2i + 1 right: 2i + 2 인덱스를 1부터 시작하면 parent: i/2, left: 2i, right: 2i+1 로 구할 수도 있다. 잘 보면 오른쪽 노드 = 왼쪽노..
-
Array vs LinkedListComputer Science/DataStructure 2019. 12. 16. 15:53
둘다 선형 방식의 자료구조이다. 배열(Array): 인덱스를 가지고 있는 데이터의 모음. 리스트(List): 순서가 있는 데이터의 모음. 각 원소는 다음이 어떤 원소인지만 알고 있음. 배열은 인덱스를 가지고 있기 때문에 인덱스를 알고 있으면 원소에 직접 접근이 가능해 빠르게 조회할 수 있다.(O(1)) 대신 인덱스는 고정되어야 하고 만약 엘리먼트가 삭제되더라도 빈 공간으로 남겨둬야 한다. → 이는 메모리 낭비를 초래할 수 있고, 엘리먼트가 비었는지 확인하는 로직이 필요하다. 리스트는 인덱스가 없기 때문에 각각의 원소는 다음 원소만 알고 있기 때문에 순차적으로 접근해야 한다. (O(n)) 인덱스가 고정이 아니고 순서 정도의 의미만 지니기 때문에 추가, 삭제가 빠르다.(O(1)) → 하지만 추가 삭제를 위한..
-
Linked ListComputer Science/DataStructure 2019. 11. 19. 00:27
- 선형 자료구조 - 순차적 접근방식 ( O(n) ) - 삽입, 삭제가 빠르다 ( O(1) ) - 다음 노드를 가리키는 주소를 저장할 공간 필요 Linked List는 순차적으로 모인 데이터들의 모음이다. 흔히 각각의 데이터를 Node(노드), 각 노드는 다음 차례의 노드의 reference(주소)를 갖고 있다. 대표적으로 두 가지 유형이 있는데, Singly Linked List: 내 다음 노드(next node)의 주소만을 갖고 있다. Double Linked List: 내 이전(previous)과 다음의 주소를 갖고 있다. Linked List를 사용하기 위해서는 시작과 끝의 주소를 알아야 하는데 이를 head와 tail이라 부른다. Performance Linked List의 대부분의 연산은 O(..