전체 글115 [Data Structure] 문자열과 해시: String, Hash, Trie, KMP String string : 문자들로 구성된 배열. s[0], s[1], ..., s[n-1], [\n0] Substring(부분문자열): S의 i번~j번의 연속된 글자로 구성된 문자열: s[i...j] cf)Subsequence(부분 수열): 문자열의 일부 글자가 원래 순서 유지하며 나열된 형태. 연속적이진 않지만 중간중간 뽑아내서 나열. prefix(접두사): S의 0번 글자부터 a번 글자까지 구성된 부분 문자열 suffix(접미사): S의 a번 글자부터 끝까지로 구성된 부분 문자열 Hash 임의 길이의 데이터(ex. 문자열)를 고정된 길이의 데이터(ex. 정수)로 매핑하는 함수 해싱(hashing): 키(key, 매핑 전 데이터)를 값(hash value, 매핑 후 데이터)으로 매핑 해시테이블이라는.. 2022. 7. 6. [Data Structure] B Tree, B+ Tree B Tree 이진트리의 확장 버전 더 많은 수의 자식을 가질 수 있게 일반화시킨 트리구조 모든 leaf노드들이 같은 레벨을 가질 수 있도록 자동으로 균형을 맞춤 정렬된 순서 보장, 멀티레벨 인덱싱을 통한 빠른 검색 → 데이터베이스와 파일 시스템에서 널리 사용 규칙 노드는 최대 M개 부터 M/2개 까지의 자식을 가질 수 있다. 노드에는 최대 M-1 개부터 [M/2]-1 개의 키가 포함될 수 있다. 노드의 키가 x개라면 자식의 수는 x+1개다. 최소차수: 자식 수의 하한값. 최소차수가 t라면 M = 2t-1을 만족 EX. 최소차수 t가 2라면, 3차 B트리이며, key의 하한은 1개이다. 탐색 루트 노드부터 하향식으로 검색 찾고자하는 값 k가 key들 사이에 있다면 거기의 자식 노드로 내려감 리프노드까지 갔.. 2022. 7. 5. [Data Structure] Binary Search Tree 이진 탐색 트리 (Binary Search Tree) 트리 자료구조 중 가장 간단한 형태. 이진 탐색이 동작할 수 있도록 고안된, 효율적 탐색이 가능한 자료구조 탐색, 삽입, 삭제가 모두 가능 이진트리(탐색 $O(logN)$) + 연결리스트(삽입, 삭제 $O(1)$) 중복된 노드 없음 이진 탐색 트리 핵심 연산 검색 트리의 높이가 h일 때 O(h) 삽입 삽입 위치까지 찾아가는 연산 O(h)+ 삽입 연산 O(1) -> O(h) 삭제 자식이 없는 노드인 경우 그냥 삭제 자식이 1개인 노드인 경우 자식 노드의 값으로 대체 자식이 2개인 노드인 경우 왼쪽 서브 트리의 최대값 or 오른쪽 서브 트리의 최소값 중 하나로 대체 이진 탐색 트리의 특징 부모 노드보다 왼쪽 자식 노드가 작음 부모 노드보다 오른쪽 자식 노.. 2022. 7. 3. [Data Structure] Tree, Binary Tree (+heap) 트리 노드(정보의 단위. 어떤 정보를 가지고 있는 개체)와 노드의 연결(간선, edge)로 표현. 그래프 자료구조의 일종. DB 시스템이나 파일 시스템 같은 곳에서 많은 양의 데이터 관리 위한 목적으로 사용 연결된 정보 저장하는 인접리스트로 구현 비선형 자료구조, 계층적 자료구조 Connected acyclic (undirected) graph 방향성이 존재하지 않고 사이클이 없는 연결 그래프 트리 자료구조의 특징 부모 노드와 자식 노드의 관계로 표현 형제: 부모 노드가 같은 두 노드의 관계 조상/자손: 부모/자식 노드들의 집합 루트 노드: 최상단 노드 단말 노드: 최하단 노드. 리프 노드. 서브 트리: 트리에서 일부를 떼어낸 것. 일부 떼도 트리 구조. 포레스트: 트리가 여러 개! 포레스트는 트리가 아.. 2022. 7. 2. [Data Structure] 선형 자료구조: Stack, Queue, Priority Queue, Deque 자료구조 추출되는 데이터 스택 가장 나중에 삽입된 데이터 큐 가장 먼저 삽입된 데이터 우선순위 큐 가장 우선순위가 높은 데이터 스택 LIFO 방식 (Last In First Out, 나중에 들어온게 먼저 나감, 후입선출), 선입후출 박스 쌓기에 비유. 아래(왼쪽)부터 위(오른쪽)로 점점 올리고 맨 위부터 뺌 원소의 삽입/삭제가 한쪽 끝(top)에서만 이루어짐 유한 순서 리스트 append(): 리스트 가장 뒤쪽(오른쪽)에 데이터 삽입 pop(): 리스트 가장 뒤쪽(오른쪽)에서 데이터 꺼냄 큐 FIFO 방식 (First In First Out, 먼저 들어온게 먼저 나감) 줄서기에 비유. 먼저 온 사람이 먼저 들어감. 원소의 삽입 및 삭제가 양쪽 끝에서 일어남 (front, rear) rear에는 삽입(en.. 2022. 7. 1. [Data Structure] ArrayList vs LinkedList Array는 index로 빠르게 값을 찾는 것이 가능함 ArrayList는 데이터를 찾는데 빠르지만, 삽입 및 삭제가 느림 LinkedList는 데이터의 삽입 및 삭제가 빠름 Array(배열) 원소의 주소 연속적으로 할당 (index) 메모리 공간에 할당할 사이즈를 미리 정해놓고 사용 → 크기 제한 O 선언 시 크기와 데이터 타입 지정 int arr[10]; String arr[5]; index로 위치 검색에 편함. $O(1)$ → random access 가능 데이터 삽입, 삭제가 비효율적 $O(N)$ 해당 원소에 접근한 후, shift하는(+덮어씌우는) 비용 발생 계속 데이터가 늘어날 때, 최대 사이즈를 알 수 없을 때는 사용에 부적합 List 노드들의 연결로 이뤄짐. 원소들을 일렬로 정렬해 놓은 것.. 2022. 6. 30. 이전 1 ··· 9 10 11 12 13 14 15 ··· 20 다음
