처음부터 차근차근

Typescript를 통해 Heap 중 최대 힙을 구현하였다. 사용하면서 느낀 점은 타입 스크립트 사용 시 타입 단언을 잘 해줘야 한다. 항상 생각하고 주석을 달면서 코드를 작성하자. class MaxHeap { private heap: number[]; constructor() { this.heap = []; } push(value: number) { this.heap.push(value); this.heapifyUp(); } pop() { if (this.heap.length === 0) return null; const root = this.heap[0]; // 마지막 노드를 pop 한 것을 root로 올리기 위해 저장. // 타입 단언 사용 const lastNode: number = this.h..

Heap Heap tree or Heap이라고 불린다. 여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 완전 이진트리를 말한다. 우선순위 Queue를 위하여 만들어진 자료구조이다. 힙은 일종의 반 정렬 상태(느슨한 정렬 상태)를 유지한다. 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다. 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다) 힙은 계산 편의를 위해 인덱스를 1부터 사용한다 (parent: x, left: 2x, right: 2x+1) 힙의 데이터 삽입 여기서 규칙이란 최소힙, 최대힙의 규칙을 의미한다. 리프 노드에 삽입할 노..

자료구조의 HashTable을 한번 구현해봤다. Python에는 딕셔너리 자료구조가 Hash로 되어있기 때문에 직접 구현할 필요는 없지만, Javascript는 Hash 자료구조가 없기 때문에 직접 구현해줘야 한다. (비슷한 구조로 object가 있지만, 탐색 시 O(N)이 걸린다는 단점이 존재) HashTable 구현 class MyHashTable { // 길이를 명시하는 이유는 나중에 특정 상황에서 길이를 늘리고자 함 // 해시 충돌에 대응하기 위함 table = new Array(71); numItems = 0; // load factor 설정을 위해 아이템의 개수를 측정할 수 있는 변수 생성 resize() { // 새로운 배열 생성 const newTable = new Array(this.ta..

Hash란? 해시 함수(hash function) 또는 해시 알고리즘(hash algorithm) 또는 해시함수알고리즘(hash函數algorithm)은 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값은 해시 값, 해시 코드, 해시 체크섬 또는 간단하게 해시라고 한다. - wikipidia 해시 테이블 토는 해시 맵은 키를 값에 매핑할 수 있는 구조인, 연관 배열 추상 자료형(ADT)를 구현하는 자료구조이다. - 팀스파르타 알고리즘 강의 해시 테이블의 가장 큰 특징은 대부분의 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1)이라는 점이다. Hash의 용도 중 하나는 Hash table이라는 자료구조에 사용되며, 매우 빠른 데이터 검색을 위한 컴퓨터 소프트..

Queue 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다. - wikipidia 먼저 들어간 것이 먼저 나가는 "선입선출"로, FIFO 구조를 가지고 있다. 삭제 연산이 수행되는 곳을 Front, 삽입 연산이 이루어지는 곳을 Rear로 FIFO 구조를 위해서 스텍과 다르게 큐의 한쪽 끝에는 삽입 작업이, 다른 한쪽 끝에서는 삭제 작업이 나뉘어서 이루어지고 있다. 큐는 Rear에서 이루어지는 삽입 연산을 Enqueue라고 부르며, Front에서 이루어지는 삭제 ..

이번에는 이중 연결 리스트를 구현했다. Doublylinkedlist 구현 // 이중 연결 리스트 Class Node class Node { constructor(data) { this.data = data; this.next = null; // 이중 연결 리스트이기 때문에 이전 값도 추가되어야 한다. this.prev = null; } } class DoublyLinkedList { constructor() { // 처음 만들었을 경우, head는 null을 넣어야 한다. this.head = null; // 마지막도 null을 해준다. this.tail = null; // 연결 리스트의 크기를 보기 위해 삽입 this.length = 0; } pushFirst(data) { let newNode = ..

C++이나 Java의 경우 Linkedlist 자료구조를 지원하지만, Javascript는 그렇지 않다. (브라우저 언어라 그런지 이런게 없다니..) Node.js Backend로써 한번 자료 구조를 직접 제작해봤다. Node Class 만들기 단일 연결 리스트를 구현하기 위해서는 먼저 노드를 만들어주는 Class를 생성해야 한다. // 단일 연결 리스트 Node 제작 class class Node { constructor(data) { this.data = data; this.next = null; } } data를 입력하고 반환하는 Node 클래스를 하나 생성하였다. Linkedlist Class 만들기 class LinkedList { constructor() { // 처음 만들었을 경우, head..

Linkedlist란? 연결 리스트(Linkedlist)는 각 노드가 데이터와 포인터를 가지고 한줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다. 데이터를 담고있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전 노드와의 연결을 담당하게 된다 - wikipidea 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료구조이다. 삽입과 삭제 : O(1) (삭제의 경우 특정 노드를 아는 경우에는 1이지만, 모르는 경우에는 n만큼의 시간이 소요된다.) 탐색 : O(n) 연결 리스트의 가장 첫 번째 지점을 Head라고 부른다. 마지막 노드는 Null을 가리킨다. 장단점 장점 연결 리스트는 데이터 구조의 큰 틀을 바꾸지 않고 노드를 추가하거나 삭제하기 쉽다. 연결 리스트는 배..

네트워크에서 출발지부터 목적지로 데이터를 전송할 때 사용하는 통신 방식의 종류는 다음과 같다. 유니캐스트 출발지와 목적지가 정확히 하나로 정해져 있는 1:1 통식 방식이다. 실제로 사용하는 대부분의 통신(Ex : HTTP)은 유니캐스트 방식이며, 가장 일반적인 네트워크 전송 형태이다. 브로드캐스트 1:N (전체 통신) 동일 네트워크에 존재하는 모든 호스트가 목적지이다. 목적지 주소가 모든으로 표기되어 있는 통신 방식으로, 유니캐스트로 통신하기 전, 주로 상대방의 정확한 위치를 알기 위해 사용된다. 예시르논 ARP가 있다. 주소 체계에 따라 브로드캐스트를 다양하게 분류할 수 있지만 기본 동작은 로컬 네트워크 내에서 모든 호스트에 패킷을 전달해야 할 때 사용합니다. 멀티캐스트 1:그룹(멀티캐스트 구독 호스트..

Network Topology란? 토폴로지는 컴퓨터 네트워크의 요소들(링크, 노드 등)을 물리적으로 연결해 놓은 것, 또는 그 연결 방식을 말한다. LAN은 물리적 토폴로지와 논리적 토폴로지 둘 다 보여 줄 수 있는 네트워크의 한 예이다. LAN상의 어떠한 노드도 네트워크 상에서 하나 이상의 다른 노드에 하나 이상의 링크를 갖고 있으며 그래프 상의 이러한 링크와 노드들은 네트워크의 물리적 토폴로지를 잘 설명해 주고 있다. 이와 비슷하게 네트워크 상에서 노드끼리의 데이터 흐름은 네트워크의 논리적 토폴로지를 결정한다. 물리적 토폴로지와 논리적 토폴로지는 특정 네트워크에서 아주 동일할 수도 있고 그렇지 않을 수도 있다. -Wikipedia 즉, 네트워크 토폴로지란 노드와 링크가 어떻게 구성되어 있는지 말하는 ..