CS 과목(CS科目）/자료 구조(Data Structure) 썸네일형 리스트형 트리(Tree)에서 자주 까먹는 용어 및 파생 개념 문서에 따라서의 경로의 길이가 [노드들의 수]가 아니라, [간선들의 수]일 때가 있다. lefth of path 라는 용어가 나오면 어느 맥락에서 사용되는 말인지를 먼저 파악을 해야 한다. 그러나, 관련 문서에 따라서는 [edge의 수]가 아니라, leaf까지의 가장 많은 [노드의 수]인 경우도 있다. 문서마다 서로 다르니, 트리의 height이라는 말을 보면, 어느 의미로 쓰인 지를 파악하는 것이 중요하다. 노드의 레벨도 어떤 문서에서는 레벌 0이 아니라, [레벨 1]부터 카운팅하는 경우도 있다. 트리의 특징 1. 노드는 단 하나의 부모 노드를 가진다. 형태에 따른 이진 트리(binary tree)의 종류 편향 이진 트리 = 왼쪽 편향 이진 트리 or 오른쪽 편향 이진 트리 더보기 [ADT Set] && [Set의 구현체인 HashSet] && [List와 Set의 차이] ADT Set(집합)의 특징 2가지 1. 순서를 보장하지 않음 2. 데이터 중복을 허용하지 않음 Set은 언제 사용하면 좋을까? 1.중복된 데이터를 제거해야 할 때! 중복된 단어들을 Set에 넣게 되면, 서로 다른 단어들만 남게 된다. 2. 데이터의 존재 여부를 확인해야 할 때(교집합) 용인시 사업 지원자의 주민번호와 경기도 사업 지원 수혜자의 주민번호의 교집합(Intersection) 원소들을 구하면 된다. Set(집합)의 구현체(in JAVA) 1. HashSet( 오늘 다룰 것 ) 2.LinkedHashSet 3.TreeSet HashSet -> Hash Table을 사용하여 Set을 구현 일반적으로, Hash Function 덕분에 Hash Table의 크기에 상관없이, key를 통하여 상수 시간.. 더보기 Tree Traversal - Pre-Order, In-Order, Post-Order(feat.이진 탐색 트리(binary search tree) 우선, binary search tree에 대해서 알아 보겠다. 우선 난 여태까지 대단한 착각을 하고 있었다. Binary Search(이진 탐색)과 Binary Search Tree(이진 탐색 트리)의 차이점에 대해서 별로 생각해 보지 않아서, 두 개 모두 같은 것이라고 보고,Binary Search Tree도 Binary Search(이진 탐색)과 같은 방식으로 동작하는 줄 알았다. 이진 탐색(Binary Search) vs 이진 탐색 트리(Binary Search Tree) 이진 탐색(Binary Search) 1. 중복된 값을 허용한다. (왼족 자식 노드는 부모 노드와 같거나 작고, 오른쪽 자식 노드는 부모 노드보다 크다 ) 2. 배열의 mid_index를 기점으로 탐색값과의 대소관계를 이용하여 .. 더보기 동적 배열(Dynamic Array) vs 연관 배열(Associative array) Array의 장점 [연속적인] 메모리 공간에 데이터들을 저장하기 때문에 CPU CACHE를 통해 같은 배열에 있는 데이터들에 접근하는 시간을 단축할 수가 있다. ( ex. cpp - vector, JAVA - ArrayList) (? list 구현체는 모두 동적인가?? ) 더보기 Array List vs Linked List List ADP의 사용 예시 문제1 ~100까지의 정답을 저장해야 한다고 해보자. 1. 정답들을 저장할 때, 문제의 [순서]대로 저장을 해야 하며, 2. 그 정답들 중, [중복]되는 정답들이 있을 것이다. 인기가 있는 프로그래밍 언어일수록 [순서] 상 되도록 앞에 저장을 해야 할 것이다. ( 이 예시에서는 중복이 없다 ) -> Set이나 Map을 사용하는 것이 더 적절한 상황이 아니라면 거의 대부분 List ADT를 사용한다고 보면 된다. (Set,Map은 추후에 다룸) List ADT의 구현체 1 - ArrayList 배열을 기반으로 구현되고, 구체적인 것은 너무 쉬우므로 넘어 간다. List ADT의 구현체 2 - LinkedList 노드를 연결(linked)시키는 형태로 구현 ArrayList와 L.. 더보기 ADT 관점에서의 Map 개념 && Map의 구현체인 HashTable의 동작 원리 key 중복 불가 위와 같이, 데이터의 연속이므로, 위와 같은 자료 구조를 연관 배열(Associative Array, Map, Dictionary)라 고부를 수가 있다.( 파이썬에서는 Dictionary라는 용어를 쓰는 것 같음) Map 구현체 1. Hash Table : [배열, 해쉬함수]를 사용하여 Map 구현! ( 일반적으로, 상수 시간으로 데이터에 접근하기에 데이터 접근 속도 빠름) 2. Tree - based : 트리 기반의 Map(대표적으로 [레드 블랙 트리].... 이번 시간에는 Hash Table에 대해 알아 보며, 트리 기반은 레드 블랙 트리 시간에 다시 살펴 볼 것이다) Map 구현체 - Hash Table 먼저 아래의 것을 까먹지 말고 숙지하고 가자! Hash Function은 In.. 더보기 Priority Queue와 Heap의 차이점 먼저 ADT(Abstract Data Type)에 대해서 모르고 있다면, ADT가 무엇인지를 먼저 공부하고 와야 한다. (급하신 분은, 걍 "ADT란 해당 자료 구조에서 구현되어야할 기능들의 모음"이라고 생각하면 된다. 실제로 구현돼 있는 것은 아니므로 오해 금지) Priory Queue는 ADT이다. JAVA로 치면, 인터페이스인 것이다. Heap(최대힙, 최소힙)는 Prioriry Queue ADT의 구현체이다. Prioriry Queue ADT의 구현체는 Heap 이외에도 여러 구현체가 있지만, Heap이 가장 성능이 좋기 때문에 Prioriry Queue == Heap 이라고 생각하기 쉽다. 그러나 엄밀히 말하면 Heap은 Priory Queue의 구현체 중 하나에 불과하다. 더보기 DB Index에서 사용되는 B-Tree (데이터 삭제) 데이터 삭제는 아래 2가지만을 신경쓰면 된다. 1. 항상 leaf 노드에서 삭제가 발생.( internal node의 삭제 시에도 항상 leaf 노드가 삭제된다. 한참 아래에 internal node 삭제에 대한 설명이 있음) 2. 삭제 후, 해당 노드의 key수가 최소 key 수 보다 적어졌으면 재조정한다. 2-a) 형제 노드들 중, key의 수가 최소 key 개수보다 많으면 그 key를 가져와서 재조정한다. 2-a-1) 왼쪽 형제가 더 여유가 있으면...(원래 일반적으로 왼쪽 형제의 지원을 우선적으로 받는다.) ->동생의 가장 큰 KEY를 부모 노드에게 올려 주고 -> 부모 노드에 있던 KEY를 나에게 내려 준다, 2-b) 형제 노드의 도움으로도 해결이 되지 않으면, 그 다음에는 부모 노드의 key값.. 더보기 이전 1 2 다음
