<Udemy 이진 힙/해시 테이블> TIL-66

  오늘 공부한 내요은 이진 힙과 해시 테이블이다. 이진 힙은 트리의 한 유형인 힙의 한 유형이다. 이진 힙도 트리의 규칙을 가지고 추가적인 규칙을 갖는다. 이진 힙의 규칙은 간단하다. 부모 노드는 자식 노드 보다 항상 큰 값을 갖거나(최대 이진 힙) 반대로 항상 작은 값을 갖는다.(최소 이진 힙) 또한 자식 노드는 최대 2개를 가질 수 있는데 자식 노드들 사이의 위치는 우선순위가 없이 항상 왼쪽 부터 저장이 된다. 그렇기 때문에 이진 힙은 배열로 표현이 되며, 간단한 수학적 규칙을 활용해서 자료를 저장하게 된다. 그렇기 때문에 이진 힙의 루트 노드에는 항상 가작 큰 값이 오거나 가장 작은 값이 오게 된다. 이러한 점을 활용해서 우선 순위 큐를 만드는데 활용할 수 있다. 우선 순위 큐는 노드에 우선 순위를 설정하여 해당 우선 순위를 가지고 이진 힙을 구성하게 된다. 그렇게 루트 노드를 빼내면 항상 우선 순위가 설정된 대로 루트 노드가 제거된다. 이러한 특징은 아직까지 실생활에서 어떤 경우에 활용되는지 정확하게 알지는 못하나, 언뜻 보기에도 매우 유용할 것 같다.

 

  해시 테이블은 해시 맵이라고도 불리는데 키와 값을 쌍으로 저장하는 자료 구조를 일컫는 말이다. 자바스크립트를 공부하면서 계속해서 들었던 자바스크립트의 객체가 바로 해시 테이블 형태의 자료 구조였던 것이었다. 파이썬에서는 딕셔너리로 표현을 했었다. 그리고 배열을 통해서도 해시 테이블로 저장을 할 수가 있다. 바로 해시 함수를 이용하는 방법이다. 해시 함수를 통해 임의의 데이터를 넣으면 일정 기준을 통해서 숫자 값을 반환해 주고 그 숫자 값을 기준으로 배열의 해당 숫자 인덱스에 값을 저장해 주는 방식으로도 해시 테이블을 만들 수 있다. 다만 주의해야 할 점은 항상 동일한 데이터를 전달하면 동일한 값이 반환되어야 하고, 최대한 충돌이 일어나지 않게 값을 반환해 주어야 한다. 이점에서 해시 함수를 만들때 분류 기준을 만들어 내는 것은 매우 어려운 일이라는 생각이 들었다. 해시 함수를 연구하는 많은 연구진들이 있다고 들었는데, 그 이유를 이제야 알겠다. 

 

2022.08.16 - [언어 공부 및 정리/자바스크립트 알고리즘 & 자료구조[Udemy강의]] - 19 해시 테이블

19 해시 테이블

2022.08.16 - [언어 공부 및 정리/자바스크립트 알고리즘 & 자료구조[Udemy강의]] - 18 이진 힙

18 이진 힙