전체 글

같은 레벨의 모든 키값들이 정렬됨 같은 레벨의 sibling node는 연결리스트 형태로 연결되어있음 모든 leaf node는 연결리스트로 연결되어 있음 키값 중복 X, 탐색 유리 블럭 사이즈를 더 많이 이동할 수 있음(key 값에 대한 하드디스크 주소 X) 그러나 무조건 leaf node 까지 내려가야함 삽입, 삭제 모두 leaf node에서 이루어짐 모든 leaf node는 같은 레벨 leaf node가 아닌 node의 키 값의 수는 그 노드의 서브트리수-1 단말 노드 비단말 노드 인덱스 노드 : leaf node가 아닌 자료, value값에 다음 노드를 가리키는 포인터 주소 존재 데이터 노드 : lead node 자료, value값에 데이터가 존재 References https://ssocoit.t..

정렬된 균형이진트리 하나의 노드에 많은 정보를 가지거나, 두 개 이상의 자식을 가질 수 있음 중복없음 모든 leaf node는 같은 레벨에 있음 root node는 자신이 leaf node가 아닌 이상 최소 2개 이상의 자식을 가짐 내부 노드(root, leaf node 이외) M/2 ~ M개의 자식을 가짐 노드는 M/2 - 1 ~ M - 1 개의 데이터(키)가 포함될 수 있음 자식 수의 하한값이 t, M = 2t - 1 데이터가 k, 자식 노드의 수는 k+1 검색은 O(logn) 구조 유지를 위해 추가적인 연산이 수행되거나 새로운 노드를 생성함 -> 최소화를 위해 B*Tree 등장 탐색을 위해서 노드를 찾아서 이동해야함 -> 해소를 위해 B+Tree 등장 아래의 조건 위반 시 재구조화 내부노드는 M/2..

모든 노드는 RED or BLACK root 와 leaf(NIL)은 BLACK 노드가 RED이면 자식은 모두 BLACK (No Double Red) 각 노드로부터 그 노드의 자손인 리프로 가는 경로들은 모두 같은 수의 BLACK 노드를 포함 NIL을 하나의 객체로 고나리하면 하나의 노드로 관리하기에 메모리 절야 까능 삽입 시 연속된 RED 해결 Recoloring: 삽입된 노드의 부모의 형제 색깔이 RED Restructing : 삽입된 노드의 부모의 형제 색깔이 BLACK인 경우, NULL인 경우 삭제 시 RED는 그냥 삭제 BLACK의 경우 삭제 연산으로 트리 속성을 깨지 않도록 복잡도 Space : O(n) 삽입, 삭제, 검색 : O(logn) AVL vs RB 검색 : AVL > RB (AVL가 ..

Binary Search Tree의 속성을 가짐 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1 삽입, 삭제, 검색 시 시간복잡도는 O(logN), N은 노드의 개수 Node는 key, left node pointer, right node pointer, height 로 구성 Balance Factor 균형을 파악할 때 활용 BF(k) = k의 왼쪽 서브트리의 높이 - k의 오른쪽 서브트리의 높이 (-1, 0, 1 중 하나) Rotation RR, Right Rotation : 회전의 기준이 되는 노드가 오른쪽으로 감. LR, Left Rotation : 회전의 기준이 되는 노드가 왼쪽으로 감. Case LL(Left Left) Case : 중심 노드를 기준으로 왼쪽에 노드가 깊이 있는 경우 -> RR을..

full binary tree 정이진트리 : 트리의 모든 node가 0 or 2개의 자식을 가지는 경우 perfect binary tree 포화이진트리 : leaf node 가 끝까지 꽉 찬 트리 complete binary tree 완전이진트리 : 마지막 레벨을 제외한 모든 레벨에 순서대로 node가 꽉 채워진 트리 balanced binary tree 균형이진트리 : lead node들의 레벨 차이가 최대 1레벨까지만 나는 트리 -> AVL, RedBlack, B-+*Tree

문자열에서 검색을 빠르게 도와주는 자료구조 정수형 이진탐색트리는 O(logN), 문자열에서는 최대길이 M일 때 O(M*logN). 트라이 활용 시, O(M) 가능 자동완성기능, 사전 검색 등 문자열 탐색에 특화됨 trie == radix tree = prefix tree == retrieval tree 각 노드에서 자식들에 대한 포인터들을 배열로 저장하고 있어서 저장공간이 크다. Node = key + data + child L : 총 문자열의 수, M : 제일 긴 문자열의 길이일 때, 생성 : O(L*M) 탐색 : O(M) References https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Dat..

hash 함수를 사용해서 변환한 값을 index로 삼아 key, value를 저장하는 자료구조 key, value 로 이루어진 자료구조 데이터가 저장되기 전에 미리 공간을 만들어놔야 하므로 공간 효율성은 낮다. Hash Function key를 고정된 길이의 hash로 변경해줌 : hashing key를 hash로 만들어내는 함수 Hash Table hash function을 사용하여 key를 hash 값으로 매핑. 이 hash 값을 주소, 또는 색인 삼아 value를 key와 함께 저장하는 자료구조 hash를 주소로 삼아 value를 저장하는 자료구조 bucket, slot value(데이터) 가 저장되는 곳 사용 적은 자원으로 많은 데이터를 효율적으로 쓰기 위해 시간복잡도 삽입, 삭제, 검색 시 모두..

들어가기 전에. 1강에는 딥러닝 관련된 부분이 나오고 2강에는 코드 리뷰를 합니다. 아래 정리한 부분은 1강의 앞부분입니다. 1강 후반부의 딥러닝 부분은 생략하였습니다. 2강 코드의 경우 눈으로 보면 될 것 같아서 혼자 훑고 끝났습니다. 용어 Amplitude : 진폭(intensity) Frequency : 주파수, the number of compressed period 파동이 한 번 진동 시 걸리는 시간 frequency 1초 동안 진동 횟수 Phase : 위상(Degree of displacement) 물리 음향 intensity : 소리 진폭의 세기 frequency : 소리 떨림의 빠르기 tone-color : 소리 파동의 모양 소리 음향 loudness : 소리 크기 pitch : 음정, 소..