본문 바로가기
728x90
반응형

Computer Science/Data Structure

[Data Structure] Hash Table
Computer Science/Data Structure 2022. 1. 21. [Data Structure] Hash Table Hash Table 해쉬는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 소도를 갖는다. 특정한 값을 검색하는데 데이터 고유의 index에 접근하므로 O(1)이 걸린다. 단 인덱스로 저장되는 key값이 불규칙적이다. 그래서 특별한 알고리즘을 이용하여 저장할 데이터와 연관된 고유한 숫자를 만들어 낸 뒤 이를 인덱스로 사용한다. 특정 데이터가 저장되는 인덱스는 그 데이터만의 고유한 위치이므로 다른 데이터의 인덱스와 중복되지 않는다. 따라서 삽입, 삭제 시에서도 추가적인 비용이 들지 않는다. Hash Function 특별한 알고리즘을 hash method 또는 hash function라고 하며 이 메소드에 의해 반환된 데이터의 고유 숫자 값을 hash code라고 한다. 저장되는 값들의 key..
[Data Structure] Red Black Tree
Computer Science/Data Structure 2022. 1. 21. [Data Structure] Red Black Tree Red Black Tree RBT는 이진 탐색 트리를 기반으로 하는 트리 형식의 자료구조이다. 시간복잡도 Search : O(log n) Insert : O(log n) Delete : O(log n) 동일한 노드의 개수일 때 depth를 최소화하여 시간 복잡도를 줄인다. 동일한 노드의 개수일 때 depth가 최소가 되는 경우는 tree가 완전 이진 트리인 경우이다. 정의 Red-Black Tree는 다음의 성질을 만족하는 이진 탐색 트리이다. 각 노드는 Red 또는 Black이라는 색을 가진다. Root는 Black이다. 각 leaf는 Black이다. 어떤 노드가 red라면 두 개의 자식은 모두 black이다. 각 노드에 대해서 해당 노드를 루트로 보는 서브 트리가 있을 때, 서브트리의 루트에서 각 리..
Computer Science/Data Structure 2021. 11. 9. [Data Structure] 해시 해시란 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것을 말한다. 데이터를 효율적으로 관리한다. 해시 함수를 통해 데이터 값을 해시 값으로 매핑한다. 해시 테이블을 사용하면 적은 자원으로 많은 데이터를 효율적으로 관리할 수 있다. 빠른 데이터 검색이 가능하다. 해시테이블의 시간 복잡도 : O(1) 해시의 특징 무결성 보안성 : 해시는 복호화가 불가능하다. Collision 현상 데이터가 많아지면서 다른 데이터가 같은 해시 값으로 충돌나는 현상이다. 충돌 문제 해결 체이닝 : 연결리스트로 노드를 계속 추가해나가는 방식 Open Addressing : 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용 선형 탐사 : 정해진 고정 폭으로 옮겨 해기값의 중복을 피함 제곱 탐사 :..
Computer Science/Data Structure 2021. 11. 9. [Data Structure] 이진탐색트리 이진탐색트리란 이진탐색과 연결리스트를 결합한 자료구조이다. 이진탐색의 효율적인 탐색 능력과 삽입, 삭제에 효과적이다. 이진탐색 : 탐색에 소요되는 시간 복잡도는 O(log N), 삽입/삭제 불가능 연결리스트 : 삽입, 삭제의 시간 복잡도는 O(1), 탐색하는 시간 복잡도 O(N) 즉 이진탐색과 연결리스트의 장점만을 살려 고안해낸 자료구조가 이진탐색트리이다. 이진탐색트리의 특징 각 노드의 자식은 2개 이하 각 노드의 왼쪽 자식은 부모보다 작고 오른쪽 자식은 부모보다 크다. 중복되는 노드가 없어야 한다. 중위순회 방식 시간복잡도 균등 트리일 때 : O(logN) 편향 트리일 때 : O(N) 편향 트리일 때 시간복잡도가 O(N)이므로 편향 트리가 되지 않도록 개선할 필요가 있다.
[Data Structure] 트리
Computer Science/Data Structure 2021. 11. 9. [Data Structure] 트리 트리란 노드와 노드들을 이어주는 엣지로 이루어진 자료구조이다. 그래프의 일종이다. 트리의 특징 하나의 루트 노드를 가지며 부모 노드는 0개 이상의 자식 노드를 갖는다. 트리에는 사이클이 존재할 수 없다. 만약 사이클이 존재한다면 이는 트리가 아니라 그래프이다. 루트에서 어떤 노드로 가는 경우는 오직 하나이다. 트리 순회 방식 전위 순회 각 루트를 순차적으로 먼저 방문하는 방식이다. 루트 → 왼쪽 자식 → 오른쪽 자식 1 2 4 8 9 5 10 11 3 6 13 7 14 중위 순회 왼쪽 하위 트리를 방문 후 루트를 방문하는 방식이다. 왼쪽 자식 → 루트 → 오른쪽 자식 8 9 4 10 11 5 2 13 6 14 7 3 1 후위 순회 왼쪽 하위 트리와 오른쪽 하위 트리를 방문 후 루트를 방문하는 방식이다. ..
Computer Science/Data Structure 2021. 11. 9. [Data Structure] 힙 힙이란 힙은 우선순위 큐를 위해 만들어진 자료구조이다. 우선순위 큐란 큐에 우선순위 개념을 도입한 것으로 큐에 들어온 데이터들이 나갈 때는 우선순위에 따르는 것을 말한다. 힙은 완전 이진 트리의 일종으로 여러 값 중 최대값 또는 최소값을 빠르게 찾아내도록 만들어진 자료구조이다. 반정렬 상태이며 이진 탐색 트리와 다르게 중복된 값을 허용한다. 종료 최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 최소 힙 : 보모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 구현 힙은 배열로 구현한다. 배열의 인덱스 0은 사용하지 않는다. 왼쪽 자식 index = 부모 index * 2 오른쪽 자식 index = 부모 index * 2 +1 부모 index = 자..
Computer Science/Data Structure 2021. 11. 9. [Data Structure] 스택 & 큐 스택 입력과 출력이 한 곳으로 제한되는 자료구조이다. LIFO 후입선출이다. 가장 나중에 들어온 것이 가장 먼저 나온다. 주요 함수 push : 스택에 데이터를 넣는다. pop : 스택에서 데이터를 뺀다. isEmpty : 스택이 비어 있는 지 확인한다. top : 스택의 입구와 가장 가까운 요소이다. 큐 입력과 출력이 양 쪽 끝의 각각으로 제한되는 자료구조이다. FIFO 선입선출이다. 가장 먼저 들어온 것이 가장 먼저 나온다. 큐의 가장 첫 원소를 front, 가장 끝 원소를 rear라고 부른다. 큐는 rear로 들어와서 front부터 나간다. 주요 함수 enQueue : 큐에 데이터를 넣는다. deQueue : 큐에서 데이터를 뺀다. isEmpty : 큐가 비어 있는 지 확인한다. front : 큐의..
Computer Science/Data Structure 2021. 11. 9. [Data Structure] 연결 리스트 연결 리스트란 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 저장하는 자료구조이다. 데이터를 담고 있는 노드들이 연결되어 있는데 노드의 포인터가 다음이나 이전의 노드와 연결된다. 단일 연결리스트, 이중 연결 리스트 등이 있다. 연결 리스트의 특징 빈틈없는 데이터의 적재 불연속적으로 메모리 공간을 차지 포인터를 통합 전급 연결 리스트의 장단점 장점 연결리스트는 동적 크기를 가진다. 따라서 메모리 크기가 충분하다면 필요한만큼 데이터를 삽입, 삭제할 수 있다. 따라서 연결리스트는 삽입, 삭제가 용이하다. 메모리 공간을 불연속적으로 차지하기 때문에 메모리 관리가 편리하다. 배열의 경우 연속적인 메모리 공간이 필요하지만 연결리스트는 그렇지 않다. 단점 임의로 인덱스에 접근할 수 없다. 0번 ..
728x90
반응형

티스토리툴바