자바스크립트120 [Javascript] 해시 충돌의 해결 지난번에 해시 테이블을 구현했지만, 해시 충돌을 해결할 수는 없었습니다. 그래서 이번에는 해시 충돌의 해결 방법을 알아보겠습니다. 1. 첫번째 방법, 선형 탐사법 Linear Probing 여태까지 많은 자료구조와 알고리즘을 하면서 선형이라는 이름이 붙으면 어떻게 하는지 기억하시나요? 바로 하나씩 일일히 순서대로 확인했습니다. 바로 선형 탐사법이 이 방식을 이용해서 빈 테이블의 위치를 찾습니다. 선형 방식의 문제들이 그렇듯이 테이블의 크기가 늘어나면 해시의 빠른 연산속도가 느려진다는 단점을 수반합니다. insertLinearProbing(key, value) { const id = this.hash(key); if(this.table[id]) { let flag = true; for (let i = id.. 2021. 11. 22. [Javascript] 해시테이블 이번에 소개드릴 자료구조는 해시테이블입니다. 그동안 배운 자료구조들에서 탐색이 유용하게 쓰였었는데, 이 해시테이블은 탐색을 잘 할 수 있는 자료구조입니다. 1. 테이블과 해시함수 그리고 해시테이블 우선 테이블(Table)은 key와 value가 한 쌍을 갖고 표에 저장된 자료구조입니다. 단순히 표에 저장했다고 해서 테이블 자료구조가 아니라, key와 value가 쌍을 이루고 저장되어야합니다. 근데 key와 value라고하니 자바스크립트에서 떠오르는 한 가지 구조가 있습니다. 바로 key와 value 쌍을 이룬 연관(혹은 연상) 배열 map이었습니다. 그리고 우리는 이 연관 배열을 해시라고도 한다고 했었습니다. 혹은 집합과 유사한 Set도 해시테이블의 일종이라고 할 수 있습니다. 2021.03.15 - [.. 2021. 11. 22. [Javascript] 그래프 이번에 구현할 자료구조는 그래프입니다. 그래프는 트리와 비슷하면서도 다른 성질의 자료구조 입니다. 2021.10.04 - [Programming/자료구조] - 그래프 Graph 그래프 Graph 리스트와 스택, 큐는 1:1 구조의 자료구조, 트리는 1:다의 자료구조였습니다. 그렇다면 다:다 관계를 가진 자료구조도 존재할 것 같다는 생각이 듭니다. 그래프는 이처럼 다:다의 관계를 가진 자 bamtory29.tistory.com 2021.10.05 - [Programming/자료구조] - 그래프 구현2 - 인접 리스트로 그래프 구현하기 그래프 구현2 - 인접 리스트로 그래프 구현하기 지난번엔 순차 자료구조인 2차원 배열을 이용한 인접 행렬 기반 그래프를 구현했습니다. 이번에는 연결 자료구조를 이용해서 그래프.. 2021. 11. 22. [Javascript] 이진 탐색 트리 가장 활용도가 높은 이진 탐색트리를 자바스크립트로 구현해보겠습니다. 2021.09.30 - [Programming/자료구조] - 이진 탐색 트리 이진 탐색 트리 처음에 트리를 소개하며 조직도이야기를 했듯이, 트리라는 자료구조는 어떤 자료를 찾는데 이점을 갖는 구조입니다. 하지만 트리의 높이가 높아지면 탐색하는데 오래걸리거나, 위치를 안다고 bamtory29.tistory.com 중복 코드와 로직부분은 private 멤버 함수로 선언했습니다. 코드가 좀 많이 길지만 내용은 간단합니다. 재귀를 통해 삽입, 삭제, 검색에서 연산을 진행하도록 설계했습니다. class Tree { constructor() { this.root;//루트 노드 this.size = 0;//트리 크기 } _insertNode(root.. 2021. 11. 18. [Javascript] 큐 이번에 볼 자료구조는 스택과 비슷한 큐 입니다. 2021.09.16 - [Programming/자료구조] - 큐 Queue 큐 Queue 이번에는 스택과 비슷한 자료구조인 큐를 알아보겠습니다. 1. 큐 큐는 스택처럼 특정한 위치에서 넣고 뺄 수 있는 자료구조입니다. 스택은 입구와 출구가 같아서 나중에 들어간 자료가 먼저 나 bamtory29.tistory.com class Queue { constructor() { this.front = null; this.rear = null; this.size = 0; } enQueue(data) { const newNode = new Node(data); if(!this.front) { this.front = newNode; } else { this.rear.nex.. 2021. 11. 18. [Javascript] 연결 리스트 자료구조를 다시 복습할 겸, 알고리즘 포스팅에 활용도 하기 위해 자바스크립트로 다시 자료구조를 써보려고 합니다. 자료구조의 설명 자체는 기존 링크를 달기로 하고, 구현 방식은 조금 다르게 만들어 보기로 했습니다. 2021.09.03 - [Programming/자료구조] - 연결 리스트 Linked List 연결 리스트 Linked List 선형 리스트는 일반적인 배열과 다를바 없으므로 다시 작성하는 자료구조에서는 넘어가고 바로 연결 리스트부터 공부를 시작하겠습니다. 0. 연결 리스트 연결 리스트는 선형 리스트와는(순차 bamtory29.tistory.com class Node { constructor(data, nextNode = null) { this.data = data; this.nextNode =.. 2021. 11. 17. 이전 1 2 3 4 5 6 7 8 ··· 20 다음 300x250