Programming/자료구조32 [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.14 - [Programming/자료구조] - 스택 Stack 스택 Stack 이번에 소개할 자료구조는 스택과 큐인데 스택 따로 큐 따로 2개에 나눠서 소개하겠습니다. 그리고 그중에서 스택 부터 보도록 하겠습니다. 1. 스택 소개 스택(Stack)은 데이터를 쌓아올린듯한 자 bamtory29.tistory.com 스택의 원리나 구조에 대해서는 위의 포스트를 참조해주세요. class Node { constructor(data, nextNode = null) { this.data = data; this.nextNode = nextNode; } } class Stack { constructor() { this.top = null; this.size = 0; } push(data) { const .. 2021. 11. 17. 이전 1 2 3 4 ··· 6 다음 300x250