computer science 썸네일형 리스트형 [Data Structure] 맵(Map) | 맵이란? | HashMap | TreeMap | LinkedHashMap Map Data Structure 다섯 번째 스터디 : 맵 (Map) Map Key와 Value를 가진 집합 중복을 허용하지 않음 (1개의 key - 1개의 value) Map 컬렉션에 여러 종류의 클래스가 있는데, 그중 가장 많이 사용되는 것이** HashMap, TreeMap, LinkedHashMap** 1. HashMap HashMap → 내부적으로 array 형태로 저장 → 검색속도 매우 빠름 맵의 순서를 보증하지 않음 (내부 Hash 값에 따라 키순서가 정해져서, 규칙 X) 비동기 클래스 NULL값을 허용 비교사항 Hash Table Hash Map 병렬처리 권장 비권장 동기화 지원 미지원 속도 비교적 느림 비교적 빠름 Null 비허용 허용 2. TreeMap TreeMap → 내부적으로 이진.. 더보기 [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의 .. 더보기 이전 1 다음
