자료구조 알고리즘/이론

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(데이터) 가 저장되는 곳 사용 적은 자원으로 많은 데이터를 효율적으로 쓰기 위해 시간복잡도 삽입, 삭제, 검색 시 모두..

이진 탐색 트리 = 이진탐색 + 연결리스트 두 가지의 장점을 합쳐서 만든 것 이진탐색 시 O(logN), 삽입/삭제 불가능 연결리스트 삽입/삭제 시 O(1), 탐색 시 O(N) 각 노드의 자식이 2개 이하 왼쪽은 부모보다 작고, 오른쪽은 부모보다 큼 중복된 노드 X (검색 목적이므로 중복 존재로 느리게 만들 필요 X, 트리 삽입보다 노드가 count를 가지게 하는 것이 효율적) 순회 in-order 중위순회 방식으로 읽을 때 정렬된 순서대로 읽을 수 있음 연산 검색, 삽입, 삭제, 트리 생성, 트리 삭제 시간복잡도 균등 트리 : 노드 개수 N, O(logN) 편향 트리 : 노드 개수 N, O(N) (편향 트리를 바로잡도록 도와주는 개선된 tree가 AVL, RedBlack Tree) 삽입 Root 에서 ..

Node(노드), Edge(간선) 으로 구성 최상단은 Root 특징 사이클 존재X (사이클이 있으면 그래프) 모든 노드는 자료형으로 표현 가능 루트에서 한 노드로 가는 경로는 유일 노드 개수 N, 간선 개수 N-1 순회 Pre-order 전위순회 : Root -> Left -> Right In-order 중위 순회 : Left -> Root -> Right Post-order 후위 순회 : Left -> Right -> Root Level-order 레벨 순회 : Root -> 계층별로 방문(BFS 처럼)

stack : LIFO queue : FIFO priority queue : 가장 우선순위가 높은 데이터부터 출력 네트워크 트래픽 제어, os에서 작업 스케줄링 배열, 연결리스트, 힙으로 구현가능하나 힙이 제일 효율적 특징 우선순위 큐를 위해 만들어진 자료구조 최댓값, 최솟값을 빠르게 찾아내도록 만들어진 자료구조 중복값 허용 종류 max heap: 부모 >= 자식, 완전 이진 트리(왼쪽부터 차례대로 채워져있는 트리) min heap: 부모

Array 메모리 공간에 할당할 사이즈를 미리 정해놓음 index로 빠르게 찾을 수 있음 (random access) 삽입, 삭제 시 번거로움 (Array)List 사이즈 상관없으나 순서는 중요 index 검색 가능 (random access) 삽입, 삭제 시 번거로움 LinkedList data, pointer로 구성된 노드 단일: 뒤 노드만, 다중: 앞, 뒤 노드를 가리킴 index 검색 X, 순차검색 시 시간 걸림 (sequential access만 가능) 삽입, 삭제 시 용이 저장공간에 불연속 단위로 저장됨. 연속적인 기억장소 할당이 필요없지만 노드 접근 시 arraylist 보다는 소요됨 참조자를 위한 추가적인 메모리 할당 필요 References https://github.com/gyoogle..