본문 바로가기

Computer-Sience/Data-Structure4

[Data-Structure] 머클트리(Merkel Tree) 머클 트리 : 머클 트리는 1979년 랄프 머클(Ralph Merkle)에 의해 발명된 이진트리 구조로, 암호학적 해시 함수를 이용하여 대량의 데이터를 효율적으로 검증할 수 있도록 설계되었다. 블록체인과 분산 시스템에서 핵심적인 역할을 하며, 데이터 무결성을 보장하는 강력한 도구로 사용된다. 머클 트리 구조 :머클 트리는 다음과 같은 트리 구조를 가지고 있다. 머클 트리가 만들어지는 순서 : 1. 해시 계산: 말단의 각 데이터 블록에 대해 암호학적 해시 함수(SHA-256 등)를 적용하여 고정 길이의 해시값을 생성 - 위 사진 기준으로, 거래 (1)과 거래 (2)와 같은 Leaf Node의 해시 값을 생성 2. 페어링: 인접한 두 해시값을 이용하여 상위 노드를 생성 - 거래 (1)과 .. 2025. 5. 30.
[Data-Structure] Hash Table(해시 테이블) 1. Hash Table(해시 테이블) 해시 테이블은 (Key, Value) 쌍으로 데이터를 저장하는 자료구조이며, 일반적으로 O(1)의 시간복잡도로 빠른 속도로 데이터를 저장하고 조회할 수 있다.   - 기본 구조해시 테이블의 기본 구조는 아래와 같이 이루어져 있다. Key가 되는 데이터를 해시 함수에 입력하면 인덱스가 생성이 되고, 해당 인덱스가 가리키는 버킷에 데이터를 저장하는 것이다.   인덱스 사용하기 때문에, 평균적으로 O(1)의 시간을 가지게 된다는 특징이 있다. 버킷(Bucket): 실제 데이터가 저장되는 공간해시 함수(Hash Function): Key를 고정된 길이의 해시값으로 변환하는 함수인덱스(Index): 해시값을 기반으로 계산된 버킷의 주소    2. 해시 함수(Hash Func.. 2024. 11. 11.
[Data-Structure] Stack, Queue, Deque Stack과 Queue는 선형 자료구조의 특징을 공통적으로 가지고 있다. Stack : Last In First Out (LIFO) - 후입 선출 (후에 들어간 원소가 먼저 배출) First In Last Out (FILO) - 선입 후출 (먼저 들어간 원소가 나중에 배출) 이것은 Stack의 가장 큰 특징이며 차곡차곡 쌓이는 구조로 이해하면 된다. 그렇기에 늦게 들어간 녀석들은 점차 쌓이게 되고 호출 시 가장 위에 있는 원소가 나오는 구조이다. ex ) 바구니에 물건을 담았다가 위에서부터 꺼냄 Queue : First In First Out (FIFO). - 선입 선출 (먼저 들어간 원소가 먼저 배출) Stack과 다르게 들어간 원소가 쌓이는 것은 마찬가지이나 들어간 순으로 배출된다는 것이 특징이다. .. 2022. 12. 27.
[Data-Structure] Array, Linked-List Array : 배열이라는 뜻의 Array는 가장 기초적인 자료구조 형식으로, 논리적/물리적 저장 위치가 동일하다는 특징을 가지고 있다. 접근 (Access) : 위치 정보를 나타내는 인덱스(Index)를 이용하여 해당 원소에 바로 접근이 가능하다. 접근에 대한 시간 복잡도는 O(1)이라는 특성을 가지고 있는데 이는 삽입(Insert)/삭제(Delete)는 다른 결과를 보여준다. 삽입(Insert) / 삭제 (Delete) : [0,1,2,3,4,5,6,7,8,9] 이라는 Array에 '5' 라는 원소에 접근을 하여 삭제를 하게 된다면 [0,1,2,3,4, ,6,7,8,9] 이와 같이 바뀌게 되는데 '4'와 '6' 사이에 어떠한 값이 들어간 것이 아닌 빈 공간이 생겨버리게 된다. Array의 특성 상 빈 .. 2022. 12. 24.

티스토리툴바