Computer Science/Data Structures8 🥪Array & Linked List 1. Array 🥪 Array(배열)는 메모리 상에 원소를 연속하게 배치한 자료구조를 뜻한다. O(1)에 k번째 원소를 확인/변경 가능하다. 또한 다른 자료구조와 다르게 추가적으로 소모되는 메모리의 양(overhead)가 거의 없으며, 메모리 상에 데이터들이 붙어 있어서 cache hit rate가 높다. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸린다. ※ array에서의 cache hit rate가 높은 이유? : 데이터가 연속해서 배치되어 있으므로 cache 입장에서 array 내의 인근 데이터까지 cache block에 load 하므로 임의의 array 내의 원소 접근 시 인근 원소 역시 cache에 있을 확률이 높다. 그리고 반복적으로 동일한 array 내의 원소를 접근한다면 cac.. Computer Science/Data Structures 2024. 1. 8. 🌳 Binary Tree 🌳 theory 🌳 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조 : Binary Tree is defined as a tree data structure where each node has at most 2 children. Since each element in a binary tree can have only 2 children, we typically name them the left and right child. 🌳 트리 관련 용어 ① root node: 부모가 없는 최상위 노드 ② leaf node: 자식이 없는 노드 ③ size: 트리에 포함된 모든 노드의 개수 ④ depth: 특정 노드에서 루트 노드부터의 거리(즉 위 1번 노드의 깊이는 0, 2번 노드의 깊이는 1) ⑤ h.. Computer Science/Data Structures 2023. 12. 19. set() & dict() - 집합과 맵 🏄🏽♂️ 대표 자료구조 '집합'과 '맵'이 있다. 두 개의 자료구조는 매우 효율적인 자료구조로 특별히 python에서 어떻게 코드로 구현하고, 관련 여러 연산 기능 및 time complexity까지 자세히 알아보자! 🏄🏽♂️ 시간복잡도 계산 상 효율적인 코드를 작성하기 위해 집합과 맵이라는 자료구조를 활용하는 경우가 많다(특히 어려운 PS 문제!) 각 자료구조의 특징을 정확히 알아보자 Sets overview "unordered collection of data types that is iterable, mutable and has no duplicate elements. The order of elements in a set is undefined though it may consist of va.. Computer Science/Data Structures 2023. 8. 3. Binary heap 👨🏫 우선순위 큐는 max-heap 또는 min-heap을 사용해 우선순위에 맞는 데이터를 뽑을 수 있는 자료구조임을 공부했다. (아래 포스팅 참조) priority queue - (binary) heap tree 1. concepts> ☝️ 우선순위 큐 = '우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조' ☝️ 데이터를 우선순위에 따라 처리하고 싶을 때 사용 ex) 물건 데이터를 자료구조에 넣었다가 가 sh-avid-learner.tistory.com ☝️ priority queue는 일종의 Abstract Data Structure(ADT)로, 추상화된 개념을 heap이라는 자료구조로 implement할 수 있다. (우선순위가 최대 먼저, 또는 최소 먼저일 경우 heap은 트리 구조를 .. Computer Science/Data Structures 2023. 2. 6. Types of Binary Tree🌲 🌲priority queue 자료구조 포스팅에서 heap은 일종의 CBT(Complete Binary Tree) 형태로 구현된다고 언급한 적이 있다. priority queue - heap 1. concepts> ☝️ 우선순위 큐 = '우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조' ☝️ 데이터를 우선순위에 따라 처리하고 싶을 때 사용 ex) 물건 데이터를 자료구조에 넣었다가 가 sh-avid-learner.tistory.com 🌲 여기서 다양한 종류의 Binary Tree에 대해 간단하게 알아보자. 🌲 Binary Tree란 tree 자료구조의 일종으로, 각 node의 자식 node는 최대 2개 존재하며, 이를 left & right child라고 부른다. ① representation) .. Computer Science/Data Structures 2023. 1. 10. priority queue(binary heap) 1. concepts> ☝️ 우선순위 큐 = '우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조' ☝️ 데이터를 우선순위에 따라 처리하고 싶을 때 사용 ex) 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야 하는 경우 자료구조 추출되는 데이터 stack 가장 나중에 삽입된 데이터 queue 가장 먼저 삽입된 데이터 priority queue 가장 우선순위가 높은 데이터 ☝️ 우선순위 큐는 크게 두 가지 방법으로 구현 가능 ① 단순히 list로 구현 ② heap을 이용하여 구현 ※ heap을 사용해서, 단순히 먼저 들어오거나 나중에 들어온 순서가 아닌, 우선순위가 높은, 즉 최댓값 먼저, 아니면 최솟값 먼저 뽑을 수 있는 자료구조를 이용해 효율적인 시간 효율 내로 연산 진행.. Computer Science/Data Structures 2023. 1. 9. hash table / hashing * hash table 🤗 반드시 알아야 할 자료구조 - 해시(Hash)에 대해서 알아보자! 🤗 파이썬에서 해시 테이블은 dictionary라는 자료구조를 통해 구현할 수 있다. dict() 클래스에 구현되어 있음. ① list의 경우 숫자로만 indexing - 즉 자료 접근이 가능하지만, dictionary의 경우 key라는 특수한 index를 통해 접근 가능 ② dictionary 함수 time complexity는 대부분 O(1) 매우 빠름 ★ list vs. dictionary time complexity ★ operation dictionary list get item O(1) O(1) insert item O(1) O(1) ~ O(N) update item O(1) O(1) delete it.. Computer Science/Data Structures 2022. 11. 6. 🍔stack & queue & deque 🧜♀️stack / queue / deque 모두 특정 위치에서만 원소를 넣거나 뺄 수 있는 restricted structure 1. stack 🧜♀️ 스택이란, 한 쪽으로만 데이터를 빼고 넣을 수 있는 자료구조로, 한 쪽만 구멍이 뚫려 있는 프링글스 통을 생각하면 된다. 먼저 들어온 데이터가 나중에 나가는 형식 - 즉 나중에 들어온 데이터가 먼저 나가는 형식(선입후출 FILO)의 자료구조. 입구와 출구가 동일한 형태로 매우 간단한 두 연산(원소 추가 O(1), 원소 제거 O(1))이 제공된다. 제일 상단의 원소 확인은 O(1), 제일 상단이 아닌 나머지 원소들의 확인/변경은 원칙적으로 불가능하다. 항상 스택 상단에만 초점이 되어 있음. 따라서 삽입할 때에도 가장 최근에 삽입한 원소 바로 위에 삽입.. Computer Science/Data Structures 2022. 9. 23. 이전 1 다음
