처음부터 차근차근

TypeScript를 통해 완전 이진트리를 구현하였습니다. 기본적으로 Tree에 들어가는 Node부터 구현하였습니다. /** Tree에 들어가는 Node 구현 @param {T} data Node에 들어갈 data @returns {TreeNode} */ export class TreeNode { public data: T; public left: TreeNode | null = null; public right: TreeNode | null = null; constructor(data: T) { this.data = data; } } 완전 이진트리 구현 배열을 받아 완전 이진트리를 구현하였습니다. 이진트리 구현 시 조건 없이 완전히 채우는 트리입니다. import { TreeNode } from "./..

Binary Tree(이진 트리) 부모 노드의 자식 노드 수가 2개 이하로 구성되어 있는 Tree를 의미한다. 이진 트리는 다음과 같이 분류 할 수 있다. 정이진 트리(full binary tree): 자식 노드가 0 또는 2개인 이진 트리를 의미합니다. 완전 이진 트리(complete binary tree): 왼쪽에서부터 채워져 있는 이진 트리를 의미합니다. 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며 마지막 레벨의 경우 왼쪽부터 채워져 있습니다. 변질 이진 트리(degenerate binary tree): 자식 노드가 하나밖에 없는 이진 트리를 의미합니다. 포화 이진 트리(perfect binary tree): 모든 노드가 꽉 차 있는 이진 트리를 의미합니다. 균형 이진 트리(balan..

Tree란? 트리는 자식노드와 부모 노드로 이루어진 계층적인 구조를 가지며, 무방향 그래프의 일종이자 사이클이 없는(순환 구조를 갖지 않는) 자료구조를 의미한다. 비선형 자료구조로 계층적 관계를 표현한다. Tree로 이루어진 집합을 숲(forest)이라고 한다. Tree의 특징 그래프의 한 종류이며, '최소 연결 트리'라고도 불린다. 계층 모델이다. 트리는 DAG(Directed Acyclic Graphs, 방향성이 있는 비순환 그래프)의 한 종류이다. Loop나 circuit이 없다. 당연히 self-loop도 없다. 즉, 사이클이 없다. 노드가 N개인 Tree는 항상 N-1개의 간선(edge)을 가진다. 임의의 두 노드 사이의 경로는 유일무이하게 존재한다. 즉, 트리 내의 어떤 노드와 어떤 노드까지의..

인접 행렬 구현 방법 자바스크립트는 다른 언어와는 다르게 2차원 배열을 구현하는 방법이 없다. (예시로 a[i][j] 이런식으로 구현할 수 없다) 따라서 Array.from 메서드를 사용하여 구현해줘야 한다. function Matrix(v) { // 자바스크립트에는 2차원 배열을 만들 때 a[0][0] 이런식으로는 만들 수 없다. // 따라서 2차원 배열을 만들 경우 이렇게 만들어야 한다. const a = Array.from(Array(10), () => new Array(10).fill(0)); const visited = Array.from(Array(10).fill(0)); a[1][2] = 1; a[1][3] = 1; a[3][4] = 1; a[2][1] = 1; a[3][1] = 1; a[4..

Graph 관련 문제를 해결하기 위해 모델링할 경우에는, 두 가지 방법이 존재합니다. 인접 행렬 인접 리스트 인접 행렬 그래프에서 정점과 간선의 관계를 나타내는 bool 타입의 정사각형 행렬을 의미한다. 정사각형 행렬의 각 요소가 0 또는 1이라는 값으로 가짐을 의미하며, 0은 두 정점 사이의 경로가 없음을 의미하며, 1은 두 정점 사이의 경로가 있음을 의미한다. 간단히 요약하자면 다음과 같다. adj[i][j] = 노드 i에서 노드 j로 가는 간선이 있으면 1, 아니면 0 다음 그래프를 한번 살펴보자 1 - 1, 2 - 2를 보면 0으로 되어있는 것을 볼 수 있는데 자기자신을 나타내는 것이며 해당 정점의 사이클이 없을 때는 0, 사이클이 있을 때는 1로 표기를 합니다. 0 - 1 이 연결되어있기 때문에..

Graph란?? 그래프(graph)는 vertex와 edge로 구성된 한정된 자료구조를 의미한다. vertex는 정점, edge는 정점과 정점을 연결하는 간선이다. -wikipedia 그래프는 트리와 비슷하게 정점과 간선으로 구성되어 있다. 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조 그래프는 여러 개의 고립된 부분 그래프로 구성될 수 있다. 그래프는 노다 간에 여러 개의 간선이 존재할 수 있다. 간선의 방향 유무에 따라 단방향 그래프와 무방향 그래프( = 양방향 그래프)로 나눌 수 있다. Vertex & Edge Vertex(정점) 노드라고 불리며, 그래프를 형성하는 기본 단위이다. 정점은 분할할 수 없는 객체이자 "점"으로 표현되는 위치, 사람, 물건 등이 될 수 있다. Edge(간선) ..

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이라는 자료구조에 사용되며, 매우 빠른 데이터 검색을 위한 컴퓨터 소프트..