일단 하자

https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/ 해싱, 해시함수, 해시테이블 · ratsgo's blog 이번 글에서는 해싱(hashing)에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님 강의와 위키피디아, 그리고 스택오버플로우와 고니 님의 블로그를 참고해 정리하였음을 먼저 밝힙니다. 그럼 시작하겠습니다. concepts 해시함수(hash function)란 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다. 이 때 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(hash ratsgo.github.io https://velog.io/@cyran..

기존에 내가 블로그에 적었던 힙정렬은 데이터의 개수가 만개가 넘어가니깐 예외가 발생해서 다시 적는다. heapify를 하는 과정에서 엑세스 위반이 발생했다. https://ko.wikipedia.org/wiki/%ED%9E%99_%EC%A0%95%EB%A0%AC 힙 정렬 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 힙 정렬(Heapsort)이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다. 최대 힙을 구성하여 정렬하는 방법은 아래 예와 같다. 알고리즘[편집] n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부모노드, 왼쪽 자식노드, 오른쪽 자식노드..

https://yabmoons.tistory.com/248 [ 정렬 ] 기수 정렬 (Radix Sort) (C++) 이번 글에서는 기수정렬(Radix Sort)에 대해서 다뤄보겠다. 기수정렬은 정말 신기하게도 비교를 하지 않고 정렬을 하는 방법이다. 버블, 선택, 퀵, 힙, 병합, 삽입, 셸 정렬은 아무리 빨라봤자 NlogN 의 시간복잡.. yabmoons.tistory.com 참고하여 작성한다. 기수정렬은 비교를 하지않고 정렬을 하는 방법이다. 비슷한 정렬로 계수정렬이 존재한다. 기수정렬은 O(n)이라는 말도 안되는 시간복잡도를 가진다. 그럼 바로 알아보도록 한다. 1. 정렬 방식 먼저 기수는 자릿수를 의미한다. 1. 1의 자릿수를 기준으로 버킷에 담는다. 그리고 버킷에서 순차적으로 빼면 1의 자릿수에..

1. 크루스칼 알고리즘(Kruskal Algorithm) 크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다. 다시 말해 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘이라고 할 수 있다. 흔히 여러개의 도시가 있을 때 각 도시를 도로를 이용해 연결하고자 비용을 최소한으로 하고자 할 때 실제로 적용되는 알고리즘이다. 먼저 용어부터 정리하면, ▶ 노드 = 정점 = 도시 : 그래프에서 동그라미에 해당하는 부분이다. ▶ 간선 = 거리 = 비용 : 그래프에서 선에 해당하는 부분이다. 즉 아래의 그래프를 살펴보았을 때 노드의 개수는 7개이고, 간선의 개수는 11개이다. 크루스칼 알고리즘의 핵심 개념은 무엇일까? 바로 다음과 같다. 간선을 거리가 짧은 순서대로 그래프에 포함..