CS/자료구조(Data Structure)

[자료구조] 해시, 해시테이블

해시(Hash) 해시란? 해시(Hash) 함수, 또는 해시 알고리즘은 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑, 변환 해주는 함수이다. 해시 함수에 의해 얻어지는 값은 해시 값, 해시 코드 등인데 간단하게 해시라고한다. 즉 해시(hash)란 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑(mapping)한 값이다 해시 함수?(Hash Function) 데이터를 효율적으로 관리하기 위해, 임의의 길이의 데이터를 수학적 연산을 통해 고정된 길이의 데이터로 매핑하는 함수이다. 임의의 길이를 갖는 메시지를 입력받아 고정된 길이의 해시값을 출력하는 함수입니다. 암호 알고리즘에는 키가 사용되지만, 해시 함수는 키를 사용하지 않으므로 같은 입력에 대해서는 항상 같은 출력이 나오게 됩니다. 해..

[자료구조] 그래프와 DFS, BFS

그래프(Graph) 그래프란 정점(Vertex)과 간선(Edge)로 이루어진 자료구조이다. 트리 또한 그래프이며, 트리는 사이클이 허용되지 않고, 그래프는 사이클이 허용된다. 사이클 : 그래프의 특정 정점에서 출발하여 돌아다니다가 다시 처음 출발했던 곳으로 되돌아 갈 수 있으면 사이클이 있다고 한다. 그래프 용어 정점 (Vertext, V) : 노드 라고도 하며 데이터가 저장되는 그래프의 기본 원소 간선 (Edge, E) : 정점(V, Node)를 연결하는 선, link, brach 라고도 부름 인접 정점 (adjacenct vertex, adj) : 간선에 의해 연결된 정점(그림 0, 3 등 이어진 정점) 단순 경로 (simple path) : 경로 중에서 반복되는 정점이 없는 경우. 동일한 간선을 지..

[자료구조] Heap 힙, 우선순위 큐

힙(Heap) 힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조이다. 힙에는 두가지 종류가 있다. 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙 : 최대 힙(Max Heap) 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙 : 최소 힙(Min Heap) 우선 순위 큐(Priority queue)를 위해서 만들어졌다. - 힙 자체가 우선순위 큐이다. 큐는 FIFO(First In First Out, 선입선출) 자료구조인데, 우선순위큐는 들어간 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나온다. Queue의 시간 복잡도는 enqueue = O(1), dequeue O(1) 이고 Priority queue 의 시간 복잡도는 push(삽..

[자료구조] 트리, B Tree, B+Tree

B Tree & B+ Tree 검색을 위한 자료구조중에서 이진트리는 한 부모가 두 개의 자식밖에 가지질 못하고, 균형이 맞지 않으면 검색 효율이 선형(O(n)) 급으로 떨어지지만, 균형이 잘맞으면 성능이 O(log N) 수준으로 보이는 장점이 있어 이를 바탕으로 개선하고자 하는 자료구조들이 나왔습니다. B Tree는 이진트리를 확장해서 더 많은수의 자식을 가질 수 있고, 균형이 맞지 않는 편향트리가 되지 않도록 균형을 맞추는 구조를 갖고 있습니다. 데이터베이스, 파일 시스템에서 널리 사용되는 트리 자료구조의 일종입니다. 단순하고 효율적이며 레벨로만 따지면 완전히 균형을 맞춘 트리입니다. 대량의 데이터를 처리할 때 하나의 노드에 많은 데이터를 가질 수 있으므로 큰 장점을 갖고 있습니다. B Tree의 규칙..

[자료구조] 트리, AVL 트리

AVL Tree (AVL은 발명자 세명의 이름에서 따왔다) 자가 균형 이진 탐색 트리. 이진 탐색 트리에서, 노드들이 삽입시 한쪽으로 편향되면 결국 탐색에서 O(N)의 시간이 걸리게 된다. * 그림 : 편향트리. 이진 탐색 트리의 편향트리를 극복하기 위해 재구성(회전, Rotate)을 통해 트리를 균형있게 만든다. AVL 트리는 다음과 같은 특징을 가진다. 이진 탐색 트리(BST)의 속성을 가진다. 왼쪽, 오른쪽 서브 트리의 높이차이가 최대 1이다. 삽입, 삭제 등 어떤 시점에서 높이 차이가 1보다 커지면 회전(Ratation)을 통해 균형을 맞춰 높이를 1로 맞춘다. AVL 트리는 높이를 logN으로 유지하기 떄문에 삽입, 검색 ,삭제의 시간 복잡도는 O(log N) 이다. AVL 트리는 균형이 무너졌..

[자료구조] 트리, 레드블랙 트리 (Red-Black-Tree)

Red-Black Tree Binary Search Tree를 기반으로 하는 자료구조. 동일한 노드의 개수일 때, depth를 최소화하여 시간 복잡도를 줄이는 것이 핵심 아이디어. 연산 삽입 insert : O(lon N) 조회 search : O(log N) 삭제 delete : O(log N) 정의 레드 블랙 트리는 다음의 성질들을 만족하는 BST(이진 탐색 트리) 이다. 모든 노드는 Red(빨강) or Black(검정) 의 색을 갖는다. 루트 노드는 검정색이다. 모든 리프 노드들은 검정색이다. 레드 노드의 자식은 모두 검정색이다 모든 리프 노드에서 Black Depth는 같다. 리프노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다. 각 노드에 대해서 노드로부터 descendan..

[자료구조] 트리와 이진트리, 이진탐색트리(BST)

트리 그래프와 트리, 그리고 BST 87 균형잡힌 트리 : AVL 트리, 레드블랙트리 88 트리는 스택이나 큐, 어레이 같은 선형 자료구조가 아닌 비선형 자료구조. 계층적 관계(hierarchical RelationShip)을 표현하는 자료구조 트리는 표현에 집중한다 무엇인가를 저장하고 꺼내야한다는 사고에서 벗어나 트리라는 자료구조를 보자 트리를 구성하고 있는 요소들 Node (노드) : 트리를 구성하는 각각의 요소 Edge (간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선 Root Node(루트 노드) : 최상위에 있는 노드 Leaf Node(Terminal Node, 단말 노드) : 하위에 자식 노드가 연결되어 있지 않은 노드 내부 노드(Internal Node, 비단말 노드) : 단말 노..

[자료구조] Stack & Queue (스택과 큐)

스택(Stack) 선형 자료구조의 일종으로 LIFO(Last In First Out) 특징을 가지고 있다. -> 나중에 들어온것이 먼저 나오고, FILO(First In Last Out) 먼저 들어간 원소가 나중에 나온다. 차곡차곡 쌓이는 구조로 먼저 들어간 원소는 밑에 깔리게 된다. 재귀적인 특징이 있다. 언제 사용? 함수의 콜 스택, 깊이 우선 탐색(DFS), 문자열 역순 출력, 후위 표기법, 웹 브라우저 방문 기록 스택의 연산 삽입 : push() 데이터 최상위 값삭제 : pop() 비어있는지 확인 : isEmpty() 꽉차있는지 확인 : isFull() push pop할 때는 해당 위치를 알고 있어야 하므로 SP(Stack Pointer)가 필요하다. 기본값은 -1 스택 - 자료구조 - 접기/펼치..

[자료구조]Array & ArrayList &LInkedList

Array & ArrayList & LinkedList 빅오표기법, 시간복잡도와 공간복잡도 빅오 표기법 : ‘가장 영향을 많이 끼치는 높은 승수를 가진 항의 상수 인자를 빼고 나머지 항을 빼서 나타낸 복잡도표기법 공간 복잡도 : 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양 시간 복잡도 : ‘문제를 해결하는 데 걸리는 시간과 입력의 함수 관계 Array(배열) 같은 타입의 연관된 data를 메모리상에 연속적이며 순차적으로 미리 할당되어 정해진 크기만큼 저장하는 자료구조 논리적 저장 순서와 물리적 저장 순서가 일치하고 index로 해당 element(원소)에 접근할 수 있다. 인덱스를 알고있다면 O(1)의 시간 복잡도로 원소에 random access 접근이 가능하다 . 삽입 또는 삭제 과정에서 해..