Poetic Code＃시적인코드

해시 테이블(Hash Table)에 대해 알아볼겠습니다. 해시 테이블(Hash Table)이란? 검색하고자 하는 키 값을 입력받은 해시 코드를 배열의 인덱스로 환산을해서 데이터에 접근하는 자료구조 F(key) => Hash Code => Index => Value key값은 문자, 숫자, 파일 등이 될 수 있다. 입력받은 key의 사이즈와 상관없이 동일한 사이즈의 Hash Code를 반환한다. 블록체인에서도 이 기술이 적용된다. 10분 간격으로 성사된 기록을 블록체인 창고에 저장 지금까지 일어난 모든 기록을 모든 사용자들의 전자 지갑에 갖고있게한다. 모든 기록들을 가지고 서로 비교하면 시간이 너무 오래걸린다. 따라서, 저장된 해시 코드들끼리 비교한다. 코드 한자리만 다르더라도 다른 값을 반환하기 때문에 ..

Array List에 대해 알아볼겠습니다. Array List란? 크기가 고정되지 않은 배열 언어별 Array Size PHP - Dynamic Java - Fixed Java에서 제공해주는 ArrayList는 데이터를 넣어주는만큼 사이즈가 늘어남. Array List의 입력 및 검색 시간 ArrayList는 배열이 다 차면 배열을 두배로 늘려준다. 그래서 검색시 고정된 배열에서 검색을 하게 된다. (검색 시간 O(1)) Doubling - 기존 배열에서 2배로 늘려준 배열에 데이터를 복사(O(n)) ArrayList에서 Doubling을 할때 기존 데이터를 복사해오는 작업은 n/2가 소요된다. 이전에는 n/4가 소요됐을 것이고 그 이전에는 n/8이 소요됐을 것이다. n/2 + n/4 + n/8 + ....

그래프(Graph)를 탐색하는 방법인 DFS(Depth First Search)와 BFS(Breadth First Search) 대해 알아볼겠습니다. Graph Search 종류 그래프를 탐색하는 방법 깊이 우선 탐색(Depth First Search) 너비 우선 탐색(Breadth First Search) Depth First Search(DFS) Binary Tree를 검색할때 사용했던 아래 3개가 DFS에 속한다. Inorder Preorder Postorder 자식의 자식의 자식...을 계속해서 방문 잎 노드를 만나면 다시 올라온다. Breadth First Search(BFS) 순서대로 레벨별로 자식들을 탐색 DFS, BSF 순서 비교 탐색하는 과정을 순서대로 비교해보며 이해해보겠습니다. DFS..

그래프(Graph)에 대해 알아볼겠습니다. 그래프(Graph)란? 강의 영상에서의 설명 트리는 노드가 있고 노드를 연결하는 엣지가 있다. 엣지의 방향은 위에서 아래로 간다. 만약, 엣지의 방향이 위아래로 있고 방향을 안 갖고 있을수 있고 ... 자기 자신을 가리키기도 하면... !@#$% 그것이 그래프입니다. 위키백과 설명 그래프는 vertex와 edge로 구성된 한정된 자료구조를 의미한다. vertex는 정점, edge는 정점과 정점을 연결하는 간선이다. 위키백과 - 그래프 나의 설명 간선을 통해 연결된 정점들이 모인 자료구조... 그냥 그림을 보고 이해하자! 참조 - 트리도 그래프의 한 종류이다. 모든 트리는 방향이 아래로 가기 때문에 화살표를 생략 가능. Directed VS Undirected D..

트라이 트리(Trie Tree)에 대해 알아볼겠습니다. 트라이 트리(Trie Tree) 란? 특히 문자열에서 빠르게 검색을 해주는 트리 구조 Binary Tree의 경우 노드의 배열에서 검색을 하기 O(long n) 시간복잡도를 갖아 비효율적이다. Trie Tree의 경우 사전을 만든다고 가정 단어의 한글자씩 노드에 저장시켜 다음 글자를 Child Node에서 찾는다. 트리에 문자열이 세로로 저장되어 있다. Root Node는 비운다 시간 복잡도는 O(M) 링크 아래 강의를 참고하여 작성하였습니다. 엔지니어대한민국 - Trie(트라이) Tree에 대해서

이진 힙(Binary Heaps)에 대해 알아볼겠습니다. 힙(Heap) 이란? 최대값이나 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리를 기본으로한 자료구조 최소힙(Min Heap) 항상 부모 노드에 작은 값을 위치 루트에는 가장 작은 값이 위치 최대힙(Max Heap) 항상 부모 노드에 큰 값을 위치 루트에는 가장 작은 값이 위치 최소힙에 노드 삽입하기 새로운 노드를 마지막 레벨의 왼쪽부터 채운다. 자신(새로운 노드)과 부모랑 비교하여 자신이 작으면 부모랑 자리를 바꾼다. 루트에 도달하거나 부모가 자신 보다 클때까지 2번을 반복한다. 시간 복잡도는 O(logN) 최소힙에서 노드 꺼내오기 루트에서 최소값을 꺼낸다. 맨마지막 노드의 값을 루트에 채운다. 자신과 자식 노드들과 값을 비교하여 자기보다 더 ..

Binary Tree 순회 방법에 대해 알아볼겠습니다. Binary Tree Traversal 이진 트리를 횡단하면서 트리의 모든 데이터를 가져오는 방법 Inorder Left - Root - Right Preorder Root - Left - Right Postorder Left - Right - Root Exemple 예제를 통한 순서 알아보기 Inorder 4 - 2 - 5 - 1 - 3 Preorder 1 - 2 - 4 - 5 - 3 Postorder 4 - 5 - 2 - 3 - 1 Binary Tree 구현 코드 in Java class Node { int data; Node left; Node right; } class Tree { public Node root; public void setR..

트리(Tree)에 대해 알아볼겠습니다. 트리(Tree)란? 부모 자식관계를 가지는 자료 구조 계층, 그룹이 있다. 부모 노드(Parent Node)는 하나 이상의 자식(Child Node)을 갖고 있다.(Leaf Node 제외) 부모가 없는 맨 위의 노드 루트 노드(Root Node)라 부른다 트리의 맨 끝에 자식이 없는 노드를 잎 노드(Leaf Node)라 부른다. 루트 노드부터 잎 노드까지 Level이 0, 1, 2 ... 하나씩 증가한다. 이진 트리(Binary Tree) 자식 노드가 최대 2개까지면 이진트리(Binary Tree) 자식 노드가 최대 3개까지면 Ternary Tree 이진 탐색 트리(Binary Search Tree) 왼쪽 자식 노드들과 그 이하 노드들은 자신보다 작아야하고 오른쪽 ..

큐(Queue)에 대해 알아볼겠습니다. 큐(Queue)란? 먼저 저장한 데이터를 가장 먼저 꺼낼 수 있는 자료구조 FIFO(First In First Out) Queue의 주요 메소드 add - 새로운 데이터를 맨 끝에 넣음 remove - 맨 앞 데이터를 가져오면서 삭제 peek - 맨 앞 데이터를 가져옴 isEmpty - 큐에 데이터가 있는지 확인 Queue 구현 코드 in Java import java.util.NoSuchElementException; class Queue { class Node{ private T data; private Node next; public Node(T data) { this.data = data; } } private Node first; private Node l..

스택(Stack)에 대해 알아볼겠습니다. 스택(Stack)이란? 나중에 저장한 데이터를 가장 먼저 꺼낼 수 있는 자료구조 LIFO(Last In First Out) Stack의 주요 메소드 push - 새로운 데이터를 맨 위에 쌓아 올림 pop - 맨 마지막에 넣은 데이터를 가져오면서 삭제 peek - 마지막 데이터를 가져옴 isEmpty - 스택에 데이터가 있는지 확인 Stack 구현 코드 in Java import java.util.EmptyStackException; class Stack { class Node{ private T data; private Node next; public Node(T data) { this.data = data; } } private Node top; public T..

단방향 연결 리스트(Singly Linked List)와 양방향 연결 리스트(Doubly Linked List)에 대해 알아볼겠습니다. 단방향/양방향 연결 리스트란? 단방향 연결 리스트(Singly Linked List) 다음 노드의 주소만 가지고 있다. 양방향 연결 리스트에 비해 메모리 공간을 절약할 수 있다. 양방향 연결 리스트(Doubly Linked List) 이전 노드와 다음 노드의 주소를 가지고 있다. 리스트의 앞, 뒤에서 모두 접근 가능하다. 메모리 공간이 더 필요하게 된다. 양방향 연결 리스트 노드 추가 및 삭제 링크 아래 강의를 참고하여 작성하였습니다. 엔지니어대한민국 - 단방향/양방향 Linked List 개념

연결 리스트(Linked List)에 대해 알아볼겠습니다. Linked List 개념 자료구조의 하나로 현재 노드에 자신의 값과 다음 노드의 주소값을 가지고 있는다. 한번 선언한 배열은 사이즈를 변경할 수 없다. 반대로 링크드 리스트는 변경이 가능함. 두 노드 사이에 다른 노드를 삽입할 수 있다. 주소를 하나씩 찾아가야 하므로 배열보다는 속도가 느릴수 있다. ※ 위 그림의 주소는 다음 노드의 주소를 가리킨다. 길이가 정해지지 않은 데이터를 사용할때는 링크드리스트로 구현하자. Linked List 노드 추가/삭제 Linked List 노드 추가 삽입하고자 하는 두 노드의 연결을 끊는다. 이전 노드의 다음 주소를 새 노드로 연결한다. 새 노드의 주소를 다음 노드로 연결한다. Linked List 노드 삭제 ..