처음부터 차근차근

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) 힙의 데이터 삽입 여기서 규칙이란 최소힙, 최대힙의 규칙을 의미한다. 리프 노드에 삽입할 노..

Prototype의 사전적 의미 prototype : 무언가 제품을 만드는 과정에서 시험용으로 미리 만들어보는 물건을 의미. ※ 시제품이나, Test를 진행하기 위한 Prototype 제작 등 Javascript에서 Prototype 의미 자바스크립트는 프로토타입 기반 언어이다. 프로토타입 기반 언어에서는 어떤 객체를 원형으로 삼고 이를 복제(참조)함으로써 상속과 비슷한 효과를 얻는다. ES5까지 자바스크립트는 Class라는 개념이 없었다. 기본적으로 프로토타입 언어이기 때문에 어떠한 Object를 원형(시제품)으로 삼고 이를 복제함으로써 Class와 비슷한 효과를 얻었다. 먼저 예제와 도식을 보자. var instance = new Constructor(); 어떤 생성자 함수(Constructor)를 ..

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

오늘 한 일 코어 자바스크립트 this 이중 연결 리스트 구현 스택, 큐 공부 및 구현 프로젝트 기획 및 MVP 날짜 정립 코어 자바스크립트 this 코어 자바스크립트 this에 대해서 학습하였다. 상황에 따라 this가 무엇을 가리키는지 다시 한번 복습하였고, 명시적으로 this를 바인딩해주는 방법을 학습 call/apply/bind를 잘 활용하면 좋은 점을 확인하였다. 전역 공간에서 this는 전역 객체를 가리킵니다. 전역 컨텍스트를 생성하는 주체가 바로 전역 객체이기 때문입니다. 전역변수를 선언하면 자바스크립트 엔진은 이를 전역객체의 프로퍼티로 할당합니다. 사실 자바스크립트의 모든 변수는 실은 특정 객체의 프로퍼티로서 동작합니다. 특정 객체란 바로 실행 컨텍스트의 렉시컬 환경입니다. 실행컨텍스트..

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 = ..

오늘 한 일 코어 Javascript 실행 컨텍스트 공부 linkedlist, Array 공부 후 단일 연결 리스트 Javascript 구현 프로젝트 관련 회의 Git convention 코어 Javascript 실행 컨텍스트 공부 실행 컨텍스트에 대해 다시 공부하는 시간을 갖게 되었다. 호이스팅, 스코프, 스코프체인, 등 다양하게 다시 복습 실행 컨텍스트는 실행할 코드에 제공할 환경 정보를 모아놓은 객체입니다. 실행 컨텍스트 객체는 활성화되는 시점에 variableEnvironment, lexicalEnvironment, Thisbinding 세가지 정보를 수집합니다. VE에는 LE와 동일한 정보로 구성되지만, VE에는 선언 시점의 스냅샷이 있으며, 변경 사항이 저장되지 않고, LE는 스냅샷이 없는 ..

Convention이란? 번역하자면 협약, 관례라는 뜻이다. 쉽게 말하자면 개발자들간 약속이란 뜻으로 Code Convention은 코드에 관련한 약속이라는 뜻. naming convention을 대표적으로 들자면, 카멜 케이스(camelCase), 스네이크 케이스(snake_case), 파스칼 케이스(PascalCase) 등이 있다. Git Commit Convention이란? 쉽게 말해 commit message에 대한 약속이다. (그냥 나 혼자 개발할 때는 안써도 무방..) 그렇다면 왜 사용하는 걸까?? (면접 질문으로 물어볼 정도로) 현업 혹은 프로젝트 간 협업을 할 때, 또는 본인이 알아보기 쉽게 등 다양한 이유에서 커밋 컨벤션이 필요하다. Commit Convention 커밋 메세지에 대한 약..