Data Structure
-
SegmentTreeAlgorithm/Theory 2021. 4. 8. 13:47
구간별로 특정한 결과 값을 관리할 때 사용하는 자료구조. 이진트리로 재귀적 구현이 특징. - query (특정 구간의 결과) O(logN) - replace (특정 인덱스 교체) O(logN) 안녕하세요 :) 오늘은 SegementTree에 대해 알아보려고 합니다. 먼저 SegemetTree 는 언제, 왜 사용할까요? SegemtTree 라는 이름이 나타내듯이 구간별로 특정한 결과값을 관리하고 싶을 때 사용하는 자료구조 입니다. 주로 구간 합을 구할 때 많이 사용하죠! 세그먼트 트리는 이진트리로 leaf 노드가 해당 인덱스의 값을 가지고 있습니다. 아래 그림처럼 전체 구간부터 반씩 잘라서 구간을 나눠 놓은 자료구조에요! 세그먼트 트리의 핵심은 재귀적 반복에 있습니다. 생각보다 어렵지 않아요 :) Sege..
-
RingBufferAlgorithm/Theory 2021. 4. 7. 10:48
안녕하세요! deque 관련된 문제를 풀다가 간만에 자료구조를 하나 정리해볼까 합니다. 아시다시피 array에서는 뒤에 추가하거나 빼는 작업은 O(1) 이지만, 앞 또는 중간에 추가하거나 빼는 작업은 O(n)의 시간 복잡도가 소요됩니다. 배열의 크기는 고정되어 있기 때문에 앞이나 중간에 작업을 하려면 그 뒤의 나머지 원소들을 모두 옮겨주는 작업이 필요하기 때문이에요. 그럼 원소들을 옮기지 않고 인덱스만 조절하면 되지 않을까? 하는 데서 시작된 아이디어가 RingBuffer가 아닐까 싶어요. RingBuffer는 read / write 포인터를 둬서 배열의 원소들을 움직이지 않고 인덱스만 조절해 덮어쓰는 방식을 사용합니다. 예시를 보면서 살펴볼게요. 처음엔 Read, Write 모두 0번째 인덱스에서 출발..
-
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 로 구할 수도 있다. 잘 보면 오른쪽 노드 = 왼쪽노..