Dev/CS 컴퓨터사이언스 썸네일형 리스트형 [Data Structure] 트라이(Trei) | 트라이란? | 트라이의 구조 | 트라이의 특징 트라이(Trie) Data Structure 다섯 번째 스터디 : 트라이 (Trie) 트라이(Trie)란? 문자열 집합을 효율적으로 저장하고 탐색하기 위해 특화된 트리 자료구조 Digital Tree, Radix Tree, Prefix Tree 라고도 부름 → 트라이는 retrieval tree에서 나온 단어 문자열 자동 완성 기능과 같이 문자열을 저장하고 탐색하는데 유용하게 사용 됨 트라이(Trie)의 구조 루트 노드는 특정 문자를 의미하지 않고 자식 노드만 가지고 있다 (= 루트 노드는 빈 문자와 연관) 이 때, 자식 노드를 Map 형태로 가지고 있다 루트 노드를 제외한 노드의 자손들은 해당 노드와 공통 접두어를 가지고 있다 정렬된 트리구조이다 트라이(Trie)의 특징 [장점] 문자열을 하나씩 전부 .. 더보기 [Data Structure] 해시(Hash) | 해시 테이블 | 해시 테이블의 충돌 해결 방법 | Hash Table vs Hash Map 해시 (Hash) Data Structure 네 번째 스터디 : 해시 (Hash) 해시(Hash)란? 해시 알고리즘을 사용하여 고유한 인덱스를 토대로 데이터를 저장하는 자료 구조 인덱스를 사용 → 빠른 검색 속도 내부적으로 배열을 사용 해시(Hash)를 이해하기 위한 용어 정리 해시(Hash, Hash Code) : 다양한 길이의 데이터를 고정된 길이의 데이터로 매핑한 값 해시 함수(Hash Function): 임의의 길이의 데이터를 고정된 길이의 데이터(해시, Hash)로 매핑하는 함수 가장 널리 사용되는 해시함수에는 MD5와 SHA-1 등이 있음 MD5: 무결성 검사 등에 사용되는 128비트 암호화 해시 함수 SHA-1: 미국 국가안보국이 설계한 160비트 해시값을 만드는 암호화 해시 함수로 미국의 .. 더보기 [Data Structure] 이진 탐색 트리 | BST | Binary Search Tree | 시간복잡도 | 전위/중위/후위 순회 이진 탐색 트리 BST(Binary Search Tree) Data Structure 네 번째 스터디 : BST (Binary Search Tree) 이진 탐색 트리의 목적 이진 탐색 연결 리스트 탐색 O(logN) 탐색 O(N) 삽입, 삭제 불가능 삽입, 삭제 O(1) → 위 두 가지를 합하여 장점을 모두 얻도록 고안된 것 → 효율적인 탐색 능력 + 자료의 삽입/삭제도 가능하도록 함 → 주요 연산: 노드 검색, 노드 삽입/삭제, 트리 생성/삭제 이진 탐색 트리의 특징 및 규칙 중복된 노드가 없이 노드에 저장된 키는 유일하다 중복이 많을 경우에는 검색을 목적으로 하는 이 자료구조에 적합하지 않음 중복이 생기는 경우에는 트리에 삽입 X → 노드에 카운팅하는것이 더 효율적 부모 노드의 키가 왼쪽 서브트리를 .. 더보기 [Data Structure] B Tree(Balanced Tree) | B Tree 규칙 | B+ Tree | B Tree와 B+ Tree 차이 B Tree & B+ Tree Data Structure 세 번째 스터디 : B Tree & B+ Tree B Tree란? Balanced Tree : 좌우 균형을 맞추어 트리의 검색, 삽입, 삭제 시 시간 복잡도를 개선한 자료구조 이진 트리를 확장하여서 더 많은 수의 자식 수를 가질 수 있도록 일반화 노드 내 데이터 수에 따라서 2차 B-Tree, 3차 B-Tree, ... M차 B-Tree) 이진 트리 구조의 간결함 + 균형 → 검색/삽입/삭제 모두 O(logN) B Tree 규칙 노드의 데이터 수가 N이면, 자식 수는 N+1 각 노드의 데이터는 정렬된 상태이어야 함 루트 노드는 적어도 2개 이상의 자식을 가져야 함 루트 노드를 제외한 모든 노드는 적어도 M/2개의 데이터를 가지고 있어야 함 (M=노.. 더보기 [Data Structure] Heap(힙) 자료구조 | 우선순위 큐(Priority Queue) | Heapify Heap Data Structure 세 번째 스터디 : Heap Heap이란? 완전 이진 트리(complete Binary Tree)의 일종, 우선순위 큐(데이터가 우선순위를 가지고 있으며, 우선순위가 높을수록 먼저 빠져나가는 큐)를 위해서 만들어진 자료 구조 우선순위 큐는 Array, Linked List, Heap으로 구현이 가능한데, 이중 힙(Heap)으로 구현하는 것이 가장 효율적 자료구조삭제되는 요소 스택(Stack) 가장 최근에 들어온 데이터(LIFO) 큐(Queue) 가장 먼저 들어온 데이터(FIFO) 우선순위큐(Priority Queue) 가장 우선순위가 높은 데이터 우선순위 큐의 이용 사례 시뮬레이션 시스템 네트워크 트래픽 제어 운영 체제에서 작업 스케쥴링 수치 해석적인 계산 Heap의 .. 더보기 [Data Structure] Stack & Queue | 스택과 큐 | 스택 파이썬으로 구현하기 | 큐 파이썬으로 구현하기 | 순환 큐 | 우선순위 큐 | 연산자 표기법 Stack vs Queue Data Structure - 3번째 스터디 : Stack과 Queue Stack이란? 후입 선출 FILO / LIFO의 자료구조 FILO: First In Last Out - 먼저 들어간 것이 나중에 나옴 LIFO: Last In First Out - 나중에 들어간 것이 먼저 나옴 시간/공간복잡도: O(n) / O(n) push(삽입): 스택에 삽입하는 연산 pop(삭제): 가장 위(top)에 있는 자료를 꺼내며 삭제하는 연산 peak(읽기): 가장 위(top)에 있는 데이터를 읽기 (삭제X) 활용 예시 안드로이드의 액티비티 관리 웹 브라우저의 방문기록 (뒤로가기) 역순 문자열 만들기 실행 취소(undo) 연산자 후위 표기법 Queue란? 선입 선출 FIFO / LILO의 자.. 더보기 [Data Structure] Tree(트리) 자료구조 | 트리의 특징 | 트리의 구성요소 | 트리의 종류 | 트리의 활용 | 트리의 장점 Tree Data Structure - 4번째 스터디 : Tree Tree의 기본 개념과 특징 노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조 하나의 루트 노드와 0개 이상의 하위 트리로 구성 데이터를 순차적으로 저장하지 않기 때문에 비선형 자료구조 트리 내에 또 다른 트리가 있는 재귀적 자료구조 Loop를 갖지 않고 연결된 무방향 그래프 구조 계층형 자료구조 : 모든 노드는 단 하나의 부모 노드만을 가짐 (루트노드 제외) 노드가 n개인 트리는 항상 n-1개의 간선(edge)를 보유 Tree의 구성요소 Tree의 구성 요소 Node(노드): 트리를 구성하는 각각의 요소 Edge(간선): 트리를 구성하기 위해 노드와 노드를 연결하는 선 Root Node(루트노드): 트리 구조에서 최상위에 있는 노드 .. 더보기 [Data Structure] Dynamic Array (Array List) vs Linked List | 동적 배열과 연결리스트 Dynamic Array (Array List) vs Linked List Data Structure - 두 번째 스터디 : Dynamic Array (Array List)와 Linked List Dynamic Array (Array List) 기본 개념 내부적으로 배열을 사용하지만 List 인터페이스를 상속받아 크기가 가변적으로 변할 수 있는 순차리스트 Java : ArrayList / C++ : Vector 배열의 크기를 변경하는(가변) resize() 연산 가능 동기화를 지원하지 않음 → Vector보다 속도가 빠름 [특징 1] 검색 : 배열처럼 인덱스를 가지고 있어서 데이터 검색에 적합하고 속도가 빠름 → O(1) [특징 2] 삽입/삭제 : 해당 데이터를 제외한 모든 데이터를 임시 배열을 생성해 .. 더보기 이전 1 2 3 다음 목록 더보기
