CS 썸네일형 리스트형 [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의 .. 더보기 [Data Structure] Tree(트리) 자료구조 | 트리의 특징 | 트리의 구성요소 | 트리의 종류 | 트리의 활용 | 트리의 장점 Tree Data Structure - 4번째 스터디 : Tree Tree의 기본 개념과 특징 노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조 하나의 루트 노드와 0개 이상의 하위 트리로 구성 데이터를 순차적으로 저장하지 않기 때문에 비선형 자료구조 트리 내에 또 다른 트리가 있는 재귀적 자료구조 Loop를 갖지 않고 연결된 무방향 그래프 구조 계층형 자료구조 : 모든 노드는 단 하나의 부모 노드만을 가짐 (루트노드 제외) 노드가 n개인 트리는 항상 n-1개의 간선(edge)를 보유 Tree의 구성요소 Tree의 구성 요소 Node(노드): 트리를 구성하는 각각의 요소 Edge(간선): 트리를 구성하기 위해 노드와 노드를 연결하는 선 Root Node(루트노드): 트리 구조에서 최상위에 있는 노드 .. 더보기 [Data Structure] Array vs LinkedList | 배열과 연결리스트 Array vs Linked List Data Structure 첫 번째 스터디 : Array와 Linked List Array(배열) 기본 개념 인덱스를 사용하여 접근이 가능한 메모리 상에 데이터를 연속하게 배치한 자료구조 논리적 저장순서와 물리적 저장순서 일치 → 검색 시 용이 데이터 자료형들이 모두 동일 연속적인 메모리 공간 → 메모리 공간 활용에 제약 (초기에 할당 후에는 크기 불변) [종류] 다양한 차원의 배열을 가질 수 있음 (1차원, 2차원, 3차원 등) [특징 1] 검색 : 인덱스를 사용하여 빠르게 접근 가능! → O(1) [특징 2] 삽입/삭제 : 끝 부분을 제외한 임의의 원소에 접근하여 shift 한뒤 작업해야 하므로 → O(n) Linked List(링크드리스트) 기본 개념 노드(데이.. 더보기 이전 1 다음
