분류 전체보기
-
Graph공부/자료구조 2018. 9. 26. 15:49
Graph트리는 그래프의 특수한 케이스그래프는 다양한 문제를 모델링 하는 것과 문제를 해결하기 위해 알고리즘을 고안하는데 유용 용어vertex, vertices(vertex의 복수형): 트리의 Node와 동일개념root node와 leaf node가 아닌 모든 노드edge: 트리의 link와 동일개념undirected edge ( = undirected graph)directed edge ( = directed graph)단방향, 양방향in-degree (해당노드로 들어오는 방향성 있는 edge), out-degree (해당노드에서 나가는 방향성 있는 edge)weighted edge ( = (directed or undirected) weighted graph)서울 - 제주도 와 서울 - LA의 wei..
-
이더리움 블록과 블록체인블록체인 2018. 8. 17. 23:32
비트코인과 이더리움 블록 비교비트코인의 블록은 헤더와 바디로 나누어 볼 수 있습니다. 이더리움도 비트코인의 블록구조와 크게 다르진 않지만 블록의 헤더부분에 uncle_list와 stack_trace 라는 값이 추가되어 있는 형태입니다. uncle list: 비트코인의 이전블록을 이더리움에서 parent 블록이라고 말하기 때문에 생긴 용어. stale 블록을 uncle 블록이라 칭함 (자세한 설명은 아래에서) 비트코인과 이더리움 블록헤더 비교 비트코인이더리움블록해시hashstate_root이전 블록해시prev_lbockparent_hash거래관련된 루트해시mrkl_rootTRIEHASH(transaction_list)TRIEHASH(uncle_list)TRIEHASH(stack_trace)난이도bitsdi..
-
AVL Tree공부/자료구조 2018. 8. 17. 23:09
BST에서 위와 같은 Skewed Tree의 경우 복잡도가 O(n)이 나오는 한계점을 해결하기 위해 AVL Tree가 고안됨. AVL 은 해당 자료구조를 만든 사람의 앞글자를 하나씩 따서 만든 것(..)AVL Tree 예시AVL TreeNot AVL Tree용어노드의 height: hbalance factor: bf (왼쪽 서브트리의 height - 오른쪽 서브트리의 hegiht)empty height: -1특징AVL 트리는 BST이면서 동시에 균형을 유지하고 있음모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하 (왼쪽과 오른쪽 서브트리의 height 계산 결과가 1, 0, -1 이외라면 해당 트리는 AVL 트리가 아님 - 만약 height가 없는 경우는 -1) 즉, 모든 노드들은 balance..
-
Binary Search Tree공부/자료구조 2018. 8. 15. 18:04
Binary Search Tree(BST - 이진검색트리) 는 비어있거나 아래의 속성을 만족하는 binary tree 입니다. 자세하게 Binary Search (이진 검색)과 Linked List를 결합한 자료구조입니다. 이진 검색의 검색능력을 유지하면서 빈번한 값의 삽입, 삭제가 가능하도록 고안되었습니다. 이진검색의 경우 검색에 소요되는 시간복잡도는 O(log₂n)으로 빠르지만 자료 입력, 삭제가 불가능합니다. linked list의 경우 자료 입력, 삭제에 필요한 시간복잡도는 O(1)로 효율적이지만 탐색하는 데에는 O(n)의 복잡도가 발생합니다.정의각각의 모든 node 들의 key는 중복된 값이 아님 (unique)기존의 binary tree는 순서가 없지만 BST는 순서가 존재parent node..
-
Heap공부/자료구조 2018. 8. 13. 21:07
Heap은 Complete Binary Tree를 기본으로 가지는 자료구조일반적으로 array로 구현하는 것이 좋음Heap 은 최댓값 또는 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안됨시간복잡도: O(log₂N)Heap은 다음과 같은 속성(property)를 만족함A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대소관계가 성립종종 priority queue를 보충하는대에 사용종류max heap: root노드가 가장 큰 수min heap: root노드가 가장 작은 수Max Heap부모노드의 키가 자식노드의 키보다 항상 큼 Node Insertionmax heap에서 노드 추가는 말단의 맨 오른쪽의 leaf node에 자리를 하나 만들고 해당 노드에 값을 대입한 다음 parent node와 값을 ..
-
Binary Tree공부/자료구조 2018. 8. 1. 22:13
degree가 최대 2인 트리i번째 level에 나올 수 있는 노드의 최대 개수는 2^(i - 1)주의 할 것은 전체 tree의 노드 최대 개수 또는 i번째 level까지 전체 노드의 개수가 아닌 i번째 level만 단독으로 보고 있음.k가 tree의 depth일 때, 최대 노드의 개수는 : 2^k -1위 그림에서 2번째 level의 노드의 최대 개수는 2^(2-1) = 2개이고, depth는 2^2-1 = 3개, height는 2^3 - 1 = 7개임 binary tree에는 skewed tree, complete binary tree, full(perfect) binary tree가 있음Full (Perfect) Binary Tree마지막 레벨까지 노드가 꽉 차게 있는 트리 Complete Binar..
-
이더리움 - 상태변환단계 및 코드실행 설명블록체인 2018. 7. 31. 23:15
상태변환함수 이더리움을 송금했다고 했을 때 계정의 상태가 어떻게 변하는지 아래에서 설명합니다.상태변환 단계트랜잭션이 형식에 제대로 맞는지(즉, 올바른 개수의 값을 가지고 있는지) 체크하고, 서명이 유효한지, nonce가 발신처 계정의 nonce와 일치하는지를 체크. 그렇지 않다면 오류를 반환gaslimit * gasprice 로 트랜잭션 수수료를 계산하고, 서명으로부터 발신처 주소를 결정발신처 계정 잔고에서 위에서 구한 트랜잭션 수수료를 빼고 발신자 nonce를 증가. 발신처 잔고가 충분하지 않으면 오류를 반환GAS = gaslimit 으로 초기화 한 후, 트랜잭션에서 사용된 바이트에 대한 값을 지불하기 위해 바이트당 gas의 특정 양을 차감발신처 계정에서 수신처 계정으로 트랜잭션 값을 보냄. 수신처 계..
-
Tree공부/자료구조 2018. 7. 31. 22:04
Tree 구조 트리는 위와 같은 구조를 갖고 있습니다.용어node: 트리에서 데이터를 의미branch(link): 노드와 노드를 연결root node: 최상위 노드interior node: 자기자신 아래에 연결된 노드가 있는 형태leaf node: 자기자신 아래에 노드가 더이상 연결되어있지 않은 형태parent: child 노드들이 연결되어 있는 상위 노드child: 부모노드 아래에 연결되어 있는 노드sibling: 부모노드 아래에 존재하며 동일한 레벨에 있는 노드degree (노드의 degree): 자기자신 아래에 연결된 노드가 몇개가 있는지depth: 루트에서 어떤 노드에 도달하기까지 거쳐야 하는 branch(link)의 수level: 트리의 특정 depth를 가지는 노드의 집합height: 루트노드..
-
Stack, Queue, Circular Queue공부/자료구조 2018. 7. 30. 23:02
StackLIFO(Last-In-First-Out) - 가장 마지막에 들어온 데이터가 가장 먼저 나감 stack에서 데이터의 삽입, 삭제를 push와 pop으로 부름stack을 구현하기 위해선, 초기에 pop이 되지 않도록 array가 비어 있는지 확인하는 함수 (isEmpty)가 필요. 타입선언 언어라면 어레이의 사이즈를 정하기 때문에 어레이에 데이터가 가득 찼는지 확인하는 함수 (isFull)이 필요.QueueFIFO(First-In-First-Out) - 가장 먼저 들어온 데이터가 가장 먼저 나감 위 그림에서 f(front)는 데이터의 시작위치를 가리키고 r(rear)은 현재 입력된 데이터의 위치를 가리킴 stack과 유사하게 어레이가 비어있는지 확인하는 함수 (isEmpty)와 가득 찼는지 확인하..
-
ADT, 복잡도(시간복잡도, 공간복잡도), 빅오 분석법공부/자료구조 2018. 7. 29. 23:38
추상화(Abstraction) - 중요한 속성만 포함하는 개체.즉 가장 중요한 것에 초점을 두고 그 이외의 부가적인 것은 무시함.ADT - Abstract Data Type한 개의 특별한 데이터 타입의 데이터 표현과 그 타입의 연산을 제공하는 부 프로그램만을 포함하는 클로저이다. 한마디로 사용자에게는 연산에 대한 형식과 제약조건만 알려주고 실제로 어떻게 처리되는지는 표현하지 않는 기능타입 객체의 표현은 숨겨지고 타입의 정의에서 연산 제공타입 선언과 연산들은 단일 구문 단위에 포함자바의 클래스 타입이라 볼 수 있음 ADT에서 중요한 것은 어떻게 구현되는지는 몰라도 무엇을 하는지 알면 사용자는 만들 수 있다는 점.복잡도 (Complexity)프로그램의 실행이 얼마나 오래 걸리는가 (= time complex..