'컴퓨터공학 기초/자료구조' 카테고리의 글 목록

컴퓨터공학 기초/자료구조

더블에스 devlog

2019. 3. 6. 09:43

ch14-ternary-search-tree.md Ternary Search Tree 1. Trie와 TST(Ternary Search Tree) 비교 및 특징 Trie는 탐색, 정렬에 매우 효율적이지만 메모리를 많이 사용하는 문제가 있다. TST는 Trie에 비해 적은 reference와 null object를 가진다. Trie와 마찬가지로 TST도 노드에 문자열을 저장한다. TST는 각 노드마다 3개의 하위노드를 가진다. less : lower child equal : middle child greater : higher child 해시맵 만큼 효율적이다. 해싱은 전체 문자열의 키를 탐색해야하지만 TST는 그렇지 않다. TST도 정렬 연산을 수행할 수 있다. TST는 해시맵보다 빠르며 BST보다 유연..

LRU Cache

2019. 3. 5. 12:37

본 글은 Udemy의 자바 자료구조 강의를 듣고 개인적으로 학습한 내용 복습하기 위해 작성된 글로 내용상 오류가 있을 수 있습니다. 오류가 있다면 지적 부탁 드리겠습니다. Least Recently Used Cache 1. Cache 기본 개념 캐시는 데이터나 값을 미리 복사해 놓는 임시 장소를 가리킨다. 캐시는 접근 시간에 비해 원래 데이터를 접근하는 시간이 오래 걸리는 경우나 값을 다시 계산하는 시간을 절약하고 싶은 경우 사용한다. 캐시에 데이터를 미리 복사해 놓으면 계산이나 접근 시간 없이 더 빠른 속도로 데이터에 접근할 수 있다. 2. LRU Cache 기본 개념 LRU는 OS의 페이지 교체 알고리즘의 하나로 최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법이다. 캐시에 공간이 부족하면 ..

Trie

2019. 3. 4. 16:04

ch13-tries.md 본 글은 Udemy의 자바 자료구조 강의를 듣고 개인적으로 학습한 내용 복습하기 위해 작성된 글로 내용상 오류가 있을 수 있습니다. 오류가 있다면 지적 부탁 드리겠습니다. Trie 1. HashMap 장단점 1.1 장점 HashMap은 매우 효율적인 자료구조로 중요한 연산(삽입, 탐색)들에 O(1) 시간복잡도를 가진다. 1.2 단점 HashMap은 정렬을 지원하지 않는다. Hash함수는 왼벽하지 않기 때문에 충돌이 발생하게 된다. 위의 단점을 보완할 수 있는 자료구조는 Trie로 HashMap에서 발생하는 충돌을 제거하고, 정렬을 지원한다. 2. Trie 기본 개념 Tire / Radix Tree / Prefix Tree 라고 부른다. 배열을 통해 자료구조를 구현할 수 있다. k..

Hashtable

2018. 11. 7. 10:01

ch11-hashtables.md 본 글은 Udemy의 자바 자료구조 강의를 듣고 개인적으로 학습한 내용 복습하기 위해 작성된 글로 내용상 오류가 있을 수 있습니다. 오류가 있다면 지적 부탁 드리겠습니다. Hashtable 1. Hashtable이란? 1.1 Hashtable 기본개념 O(logN)보다 빠른 연산을 위해 키와 1차원 배열의 인덱스의 관계를 이용하여 키(항목)을 저장하는 자료구조를 해시테이블이라고 한다. 해시테이블은 키를 간단한 해시함수로 계산한 값을 배열의 인덱스로 이용하여 항목을 저장하고 탐색/삭제하는 연산을 평균 O(1) 시간복잡도로 지원하는 자료구조이다. 위의 그림과 같이 소설의 저자를 키로 제목을 값으로 또는 회원의 이메일을 키, 회원정보를 값으로 저장할 수도 있다. 이렇게 저장된..

Binary Heap

2018. 11. 7. 10:01

ch10-binary-heaps.md 본 글은 Udemy의 자바 자료구조 강의를 듣고 개인적으로 학습한 내용 복습하기 위해 작성된 글로 내용상 오류가 있을 수 있습니다. 오류가 있다면 지적 부탁 드리겠습니다. Binary Heaps(이진힙) 1. Priority Queue(우선순위큐)란? 이진힙을 알아보기에 앞서 우선순위큐에 대해 알아보자. 우선순위큐눈 가장 높은 우선순위를 가진 항목에 접근하거나 해당 항목을 삭제하는 연산과 임의의 우선순위를 가진 항목을 삽입하는 연산을 지원하는 자료구조이다. 스택, 큐는 일종의 우선순위큐이다. 우선순위큐의 특징은 아래와 같다. 모든 항목에는 추가 속성이 있는데 이것을 우선순위 값(priority value)라고 한다. 우선순위 큐에서는 우선순위가 높은 요소는 우선순위가..

AVL Tree

2018. 10. 26. 01:14

avl-tree.md 본 글은 Udemy의 자바 자료구조 강의를 듣고 개인적으로 학습한 내용 복습하기 위해 작성된 글로 내용상 오류가 있을 수 있습니다. 오류가 있다면 지적 부탁 드리겠습니다. AVL Tree 1. AVL Tree? AVL트리는 트리가 한쪽으로 치우쳐 자라나는 현상을 방지하여 트리 높이의 균형을 유지하는 이진탐색트리이다. Balanced 이진탐색트리를 만들면 N개의 노드를 가진 트리의 높이가 O(logN)이 되어 탐색, 삽입, 삭제 연산의 수행시간이 O(logN)이 보장된다. 1.1 Linked List, Binary Search Tree, Balanced Binary Tree 비교 AVL 트리에 대해 알아보기 전에 3가지 자료구조의 차이점에 대해 알아보자. Linked List 구현이 ..

Binary Search Tree

2018. 10. 17. 13:08

본 글은 Udemy의 자바 자료구조 강의를 듣고 개인적으로 학습한 내용 복습하기 위해 작성된 글로 내용상 오류가 있을 수 있습니다. 오류가 있다면 지적 부탁 드리겠습니다. Binary Search Tree(이진 탐색 트리) 1. Binary Search Tree? 이진 탐색 트리는 이진탐색의 개념을 트리 형태의 구조에 접목한 자료구조이다. 1.1 Binary Search? 이진 탐색은 정렬된 데이터의 중간에 위치한 항목을 기준으로 데이터를 두 부분으로 나누어 가며 특정 항목을 탐색하는 방법이다. 1.2 Tree? 배열이나 연결리스트는 데이터를 일렬로 저장하기 때문에 탐색 연산이 순차적으로 수행되어야 한다는 단점을 가진다. 배열은 미리 정렬해 놓으면 이진탐색을 통해 효율적인 탐색이 가능하지만 삽입이나 삭제..

Queue

2018. 10. 17. 01:41

queue.md 본 글은 Udemy의 자바 자료구조 강의를 듣고 개인적으로 학습한 내용 복습하기 위해 작성된 글로 내용상 오류가 있을 수 있습니다. 오류가 있다면 지적 부탁 드리겠습니다. Queue 1. Queue? 1.1 Queue의 특징 삽입과 삭제가 양끝에서 각각 수행되는 자료구조 기본 연산 : enqueue(), dequeue(), shock() FIFO(First In First Out) : 선입선출 구조 Dynamic array, Linked List로 구현이 가능 BFS 알고리즘 구현에 중요 1.2 Queue의 Enqueue 연산 Enqueue 연산은 새로운 항목을 Queue의 끝에 추가하면 된다. queue.enqueue(10); queue.enqueue(4); queue.enqueue(2..

Stack

2018. 10. 16. 08:44

stack.md 본 글은 Udemy의 자바 자료구조 강의를 듣고 개인적으로 학습한 내용 복습하기 위해 작성된 글로 내용상 오류가 있을 수 있습니다. 오류가 있다면 지적 부탁 드리겠습니다. Stack(스택) 1. Stack? 1.1 Stack의 특징 Stack은 한 쪽 끝에서만 항목을 삭제하거나 새로운 항목을 저장하는 자료구조이다. 스택에서 새로운 항목을 저장하는 연산을 push라고 하고, 항목을 삭제하는 연산을 pop이라고 한다. LIFO(Last In First Out) : 선입선출 대부분의 고수준의 언어(high level language)에서 스택은 Array나 Linked List로 쉽게 구현할 수 있다. 1.2 Stack의 Push 연산 주어진 항목을 스택의 맨 위에 놓는 연산으로 O(1)의 시..

Linked List

2018. 10. 16. 08:42

linked-list.md 본 글은 Udemy의 자바 자료구조 강의를 듣고 개인적으로 학습한 내용 복습하기 위해 작성된 글로 내용상 오류가 있을 수 있습니다. 오류가 있다면 지적 부탁 드리겠습니다. Linked List(연결 리스트) 1. Linked List란? Linked List는 동적 메모리 할당을 이용해 리스트를 구현하는 가장 간단한 형태의 자료구조이다. 동적 메모리를 할당 받아 노드를 저장하고 노드는 참조를 이용하여 다음 노드를 가리키도록 만들어 노드들을 한 줄로 연결한다. 하나의 노드는 integer, double, custom object와 같은 데이터를 포함하고 있으며 다음 노드를 가리키는 참조변수를 포함하고 있다. 1.1 Linked List의 구성 Linked List의 노드는 데이터..

Array

2018. 10. 16. 08:38

arrays.md 본 글은 Udemy의 자바 자료구조 강의를 듣고 개인적으로 학습한 내용 복습하기 위해 작성된 글로 내용상 오류가 있을 수 있습니다. 오류가 있다면 지적 부탁 드리겠습니다. Arrays(배열) 1. Arrays란? Array는 동일한 타입의 원소들이 연속적인 메모리 공간에 할당되어 각 항목이 하나의 원소에 저장되어 있는 기본적인 자료구조이다. 1.1 Array의 구성 배열의 인덱스 또는 키로 식별되는 요소 / 값의 컬렉션 인덱스는 0부터 시작 인덱스 때문에 랜덤 엑세스가 가능 1.2 Array의 특성 배열은 동일한 유형의 타입을 저장하기 위한 자료구조 배열은 인덱스를 키로 사용 배열은 원하는 만큼의 차원을 가질 수 있음, 1차원/2차원/3차원 배열 등 동적배열 : 배열의 크기가 동적으로 ..

더블에스 devlog

티스토리툴바