오고 말았다 자료 구조 구현하기 사실 진작부터 왔지만 이 악물고 모른 척 했다는 게 학계의 정설 JS를 쓰면서 굳이 자료 구조를 구현하지 않아도 됐는데 이번에 힙을 만나면서 아 역시 구현을 해보긴 해봐야겠구나 하고 필요성을 느꼈다. 사실 원리만 이해하면 그렇게 죽을 것처럼 어려운 건 아닌데, 클래스에 대해 잘 아는 게 아니다 보니 진입장벽이 있었다. 근데 어처피 해야 하니까 클래스에 대해서도 이해해볼 겸 슬금슬금 다른 분들의 코드를 참고해서 구현해보았다. 힙은 배열로 구현할 건데, 루트 노드부터 같은 레벨의 왼쪽 노드 -> 오른쪽 노드 순으로 push한다. 즉 [10, 9, 5, 8, 3, 2, 4, 6, 7, 1] 순으로 채워지며 부모 노드와 왼쪽 자식 노드, 오른쪽 자식 노드는 위 표와 같이 구할 수..
힙 (Heap) 가장 일반적인 우선 순위 큐의 구현 방법으로 완전 이진 트리를 기본으로 한다. 힙을 사용해 우선 순위 큐를 구현하면 요소의 삽입, 삭제를 O(log n) 시간 복잡도로 수행한다. 우선 순위 큐(Priority Queue)란? 여러 항목들 중 가장 중요한 항목을 먼저 꺼낼 수 있는 자료구조다. 각 요소에 우선 순위를 할당해 저장하고, 우선 순위가 가장 높은 요소에 대해 빠르게 접근 및 삭제할 수 있다. 힙은 바로 이런 우선 순위 큐의 구현 방법 중 하나인 것이다. 완전 이진 트리(full binary tree) 먼저 이진 트리(binary tree)란 모든 노드들이 둘 이하의 자식을 가진 트리를 말한다. 완전 이진 트리는 마지막 레벨(제일 아래쪽)을 제외하고 모든 레벨이 완전히 채워져 있는..
Hash Table이란? 데이터를 효율적으로 저장하고 검색하는 데이터 구조 키와 값의 쌍으로 이뤄진 데이터를 저장하며, 각 키는 고유한 해시 값으로 매핑된다. 해시 테이블은 배열을 기반으로 구현되며 해시 함수를 사용해 키를 배열의 인덱스로 변환한다. 해시 함수란 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수, 키의 고유한 해시 값을 계산하는 함수를 말한다. 해시 테이블에 저장하고자 하는 임의의 원소의 해시값을 해시 함수를 이용해 계산한다. 계산한 해시 값을 주소로 하는 위치에 원소를 저장하면, 검색을 할 때도 바로 이곳으로 이동할 수 있다. 해시 함수의 특징은 같은 입력값에 대해 같은 출력값을 보장한다(일관성)는 것이다. 그렇기에 서로 다른 입력값에 대해서는 동일한 출력값이 나올 확률이 희..
선형 검색 알고리즘 전 게시글의 Search에서 언급했었던 선형 검색 알고리즘은 배열의 처음부터 끝까지 순차적으로 탐색해 찾는 값을 찾을 때까지 반복한다. 따라서 배열의 맨 마지막에 있거나 아예 없는 경우, 또는 배열이 길다면 들여다 볼 것들이 그만큼 많아지므로 시간 복잡도가 같이 높아진다. 그래서 최악의 경우 배열 모두를 돌아야 하기 때문에 시간 복잡도는 O(n) 이 되며 배열의 크기에 비례해 시간이 증가한다. 이러한 이유로 선형 검색 알고리즘이 큰 배열에서는 효율적이지 않을 수 있다. 그래서 정렬된 배열이나 더 빠른 검색을 위해 이진 검색 알고리즘을 사용한다. 이진 검색 알고리즘 정렬된 배열에서 특정 값을 찾는데 사용되는 효율적인 검색 알고리즘이다. 명시한 것처럼 '정렬된 배열'에서만 사용이 가능하다..
시간 복잡도란? 데이터 구조의 작동 혹은 알고리즘의 속도를 측정하는 것 얼마나 많은 단계가 있는가로 측정된다. (초/분의 개념이 아니라 단계가 적을 수록 좋다.) 배열 이야기 전에 메모리에 대해 알아보자. 메모리는 비휘발성 메모리와 휘발성 메모리 2가지 종류가 있다. 휘발성 메모리 비휘발성 메모리 컴퓨터를 끄면 휘발된다 컴퓨터를 꺼도 휘발되지 않는다 RAM 하드 드라이브 두 메모리 중 어떤 것의 데이터를 읽을 때 속도가 더 빠를까? 휘발성 메모리에서 데이터를 읽을 때 속도가 더 빠르다. RAM, Random Access Memory는 데이터 접속을 랜덤으로 할 수 있다. RAM을 어떤 상자들의 그룹이라고 할 때, 각 상자별로 이름이 정해져 있다. 이 이름을 Memory Address라고 한다. 그래서 어..
Set이란? JS의 내장 객체 중 하나인 Set은 고유한 값을 저장하는데 사용되는 자료구조다. 그래서 중복된 값을 허용하지 않으며, 순서를 보장하지 않는다는 특징이 있다. 간단 설명 const set = new Set(); Set 클래스의 생성자 함수를 호출해 Set 인스턴스를 생성한다. 생성된 Set 인스턴스는 Set의 메서드와 프로퍼티를 사용해 여러 작업을 수행할 수 있다. ⭐️ 여기서 클래스, 생성자, 인스턴스가 무엇인지 간단하게 알아보겠다. 클래스: 객체 지향 프로그래밍에서 객체를 생성하기 위한 템플릿. (붕어빵 틀 같은 거임) 객체의 상태나 행동을 정의하는 설계도로 클래스는 속성(데이터)와 메서드(동작)을 포함하고 있다. 생성자: 클래스로부터 객체를 만들 때 호출하는 메서드로, 객체가 생성될 때..
Stack과 Queue란? 스택과 큐는 데이터를 집어 넣을 수 있는 선형 자료형인 동시에 추상적 자료 구조(ADT - Abstract Data Type)다. ADT란 자료 구조의 방법이 어떤 코드로 정의된 것이 아니라 그 구조의 행동 양식만 정의된 것을 말한다. 즉 기능의 구현 부분이 없어서 설명하는 규칙만 이해한다면 스택과 큐라는 자료 구조를 만들 수 있다. 스택과 큐는 배열의 형태로 쉽게 표현할 수 있다. (이번 글에서는 직접 구현해보진 않지만 앞으로는 구현을 해보겠다. 진짜.) 1. Stack 📌 스택은 '팬케이크' 같은 모습이다. 팬케이크를 만들면 한 장 두 장 아래에서 위로 쌓아 올리고, 먹을 때는 가장 위부터 아래로 내려간다. 이런 것처럼 데이터도 아래에서 위로 쌓아 올리고, 데이터를 사용할 ..
