Computer Science/Data Structures11 🥪Array 1. Fundamentals★ Stores items(C/C++) or their references(Python) at contiguous locations / a linear data structure that stores similar elements in contiguous memory locations. ★(1) Random Access: i-th item can be accessed in O(1) Time as we have the base address and every item or reference is of same size(2) Cache Friendliness: since items/references are stored at contiguous locations, we get th.. Computer Science/Data Structures 2025. 1. 17. ➡️ Linked List intro➡️ Linked List(연결 리스트)는 배열이라는 자료구조와 비교하며 이해하면 쉽다. 연결 리스트는 배열과 달리 연속된 메모리 공간에 데이터를 저장하지 않고, 각 데이터가 다음 데이터의 위치를 가리키는 방식으로 저장한다. (선형 자료 구조). 이 때의 각 데이터 단위를 node라고 하고, node는 데이터를 저장하고, 다음 노드를 가리키는 참조(주소)를 포함한다. ➡️ 연결 리스트는 아래와 같은 3가지 특징이 존재한다.① 동적 크기: 배열과 달리 연결 리스트는 크기가 고정 x. 따라서 노드를 언제나 추가 / 삭제를 쉽게 할 수 있어 크기가 가변적.② 삽입 / 삭제 쉬움: 배열의 경우 삽입 / 삭제 연산을 진행할 때 해당 위치 이후의 모든 요소를 이동시켜야 하는 번거로움이 있으나, 연결 리스트.. Computer Science/Data Structures 2024. 9. 26. 🌉 Monotonic Stack intro🌉 stack의 (파이썬 코드 기준 append()와 pop()) 연산이 O(1)임을 감안해 한 곳에서 넣고 빼고를 반복하는 과정에서 stack의 원소가 오름차순 또는 내림차순을 유지하게끔 하는 stack을 만드는 유형을 'monotonic stack' 유형이라고 한다. 🌉 아래 예시와 같이 내림차순으로 이루어진 stack을 유지하면서, 새로운 원소 6이 들어올 때 pop() 연산 4번 진행 후 빠르게 append() 진행🌉 오름차순 또는 내림차순 순서 stack으로 업데이트 되는 과정에서 현재 원소보다 오른쪽 또는 왼쪽 원소 중 가장 가까이 있는 원소 최대/최솟값 구하기 또는 현재 원소보다 오른쪽 또는 왼쪽 원소 중 가장 가까이 있는 원소의 위치 구하기가 대표 유형으로 많이 나온다. 🌉.. Computer Science/Data Structures 2024. 9. 23. 🎊Binary Heap 🎊 intro🎊 Priority Queue와 연결지어 설명할 수 있는 Binary Heap data structure에 대해 자세히 알아보자. 앞서 학습한 Priority Queue는 일종의 Abstract Data Structure(ADT)로, binary heap을 추상화한 개념이라 볼 수 있다. 즉, 실제 priority queue는 binary heap이라 생각하면 된다. priority queue의 우선순위가 최대 먼저, 또는 최소 먼저라면 binary heap으로 tree structure를 만들어 tree structure에서 우선순위에 맞게 꺼내준다. 최대 먼저라면 max-heap, 최소 먼저라면 min-heap이라 부른다. (여기서 priority queue는 무조건 binary he.. Computer Science/Data Structures 2024. 7. 17. 🥪Array & Linked List Intro 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. 📚 Map Mapfundamentals → dictionaries are indexed by keys, which can be any immutable type; strings and numbers can always be keys. / map data structure is defined as a data structure that stores a collection of key-value pairs, where each key is associated with a single value / maps provide an efficient way to store and retrieve data based on a unique identifier(the key) → Tuples can be used as keys .. Computer Science/Data Structures 2023. 8. 3. 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(feat. Binary Heap) intro👯 우선순위 큐 = '우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조' 👯 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다. 예를 들어 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야 하는 경우, 즉 가치라는 우선순위에 따라 처리할 때 우선순위 큐라는 자료구조 사용. 앞서 배운 스택의 경우 가장 나중에 삽입된 데이터가 먼저 추출되고, 큐의 경우 가장 먼저 삽입된 데이터가 먼저 추출된다. 하지만 우선순위 큐는 직접 정한 우선순위에 따라 추출되는, 즉, 큐라는 자료구조에서 우선순위라는 어떤 기준을 정해 이에 의해 데이터를 추출하는 방식이라 생각하면 된다. 👯 우선순위 큐는 크게 두 가지 방법으로 구현 가능하다. ① 단순히 list로 구현하는 방법과 ② .. 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 structure1. stack🧜♀️ 스택이란, 한 쪽으로만 데이터를 빼고 넣을 수 있는 자료구조로, 한 쪽만 구멍이 뚫려 있는 프링글스 통을 생각하면 된다. 먼저 들어온 데이터가 나중에 나가는 형식 - 즉 나중에 들어온 데이터가 먼저 나가는 형식(선입후출 FILO)의 자료구조. 입구와 출구가 동일한 형태로 매우 간단한 두 연산(원소 추가 O(1), 원소 제거 O(1))이 제공된다. 제일 상단의 원소 확인은 O(1), 제일 상단이 아닌 나머지 원소들의 확인/변경은 원칙적으로 불가능하다. 항상 스택 상단에만 초점이 되어 있음. 따라서 삽입할 때에도 가장 최근에 삽입한 원소 바로 위에 삽입.. Computer Science/Data Structures 2022. 9. 23. 이전 1 다음
