개발하는 동글 :]

해시 함수 임의의 길이를 갖는 메시지를 입력받아서 고정된 길이의 해시값을 출력하는 함수 함수를 수행하기 전의 원래의 데이터를 키 [key], 해시 함수를 수행한 결과값을 해시 값 [hash value]라고 합니다. 키를 해시 값으로 매핑하는 전체적인 과정을 해싱 [Hashing]이라고 합니다. 만약 다른 키에 대해 해시값이 중복된다면, 이를 해시 충돌[Collision]이라고 합니다. 해시 테이블 해시 테이블이란 해시함수를 사용하여 변환한 값을 색인(index)으로 삼아 키(key)와 데이터(value)를 저장하는 자료구조를 말한다. 기본연산으로는 탐색(Search), 삽입(Insert), 삭제(Delete)가 있고 시간복잡도는 평균적으로 O(1)이다. 충돌 해결 방법 1. Open Addressing[..

그래프 용어 정리 정점(Vertex) 노드(node) 라고도 하며 정점에는 데이터가 저장된다. (0, 1, 2, 3) 간선(Edge) 정점(노드)를 연결하는 선으로 link, branch 라고도 부른다. 인접 정점(adjacent Vertex) 간선에 의해 직접 연결된 정점(0과 2은 인접정점) 단순 경로(simple path) 경로 중에서 반복되는 정점이 없는 경우. 한붓그리기와 같이 같은 간선을 지나가지 않는 경로 ( 0->3->2->1 은 단순경로 ) 차수(degree) 무방향 그래프에서 하나의 정점에 인접한 정점의 수 (0의 차수는 3) 진출 차수(in-degree) 방향 그래프에서 외부로 향하는 간선의 수 진입 차수(out-degree) 방향 그래프에서 외부에서 들어오는 간선의 수 경로 길이(p..

힙 완전 이진 트리 기반의 자료 구조이며, 최소힙과 최대힙 두 가지가 있고 해당 힙에 따라 특정한 특징을 지킨 트리 어떠한 값이 들어와도 특정 힙의 규칙을 지키게 만들어져 있다. 최대힙과 최소힙 최대힙 : 투트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야 합니다. 또한, 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 한다. 최소힙 : 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값이어야 합니다. 또한, 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 한다. 최대힙의 삽입 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입 이 새로운 노드를 부모 노드들과 크기를 비교하며 교환해서 힙의 성질을 만족시킨다. ..