해싱은 "탐색 알고리즘"에 대한 공부를 전제로 합니다. 선형 탐색, 이진 탐색 등 탐색 알고리즘에 대해서 잘 알지 못한다면 이번 포스팅의 이해가 쉽지 않을 것입니다. 그렇기에 해시 알고리즘을 공부하기 전 탐색 알고리즘을 먼저 공부하고 그 후에 이 포스팅을 읽으시는 것을 추천합니다. (탐색 알고리즘 공부하기)해싱 개요탐색 알고리즘을 공부하면 배우는 "선형 탐색"이나 "이진 탐색"과 같은 방법들은 어떤 데이터가 어떤 인덱스에 있는지에 대한 정보를 전혀 알지 못할 때 진행하는 방식이며, 키를 저장된 키값과 반복적으로 비교하는 방식으로 탐색합니다. 이러한 방식은 아주 빨라야 $O(\log n)$의 시간 복잡도를 가집니다. 이 정도 시간 복잡도만 가지더라도 괜찮지만 더욱 빠른 탐색을 필요로 하는 경우, 더욱 빠른..

탐색 알고리즘 개요여러 개의 자료 중 원하는 자료를 찾는 작업을 탐색이라고 합니다. 탐색은 컴퓨터 프로그램에서 가장 많이 사용하는 작업이며 또한 많은 시간이 요구되는 작업이기에 효율적으로 하는 것이 중요합니다. 탐색 알고리즘을 구현하기 위해 사용되는 자료구조는 매우 다양합니다. 그 중 배열을 사용하여 자료를 저장하고 찾는 방식이 가장 기초적이나, 탐색 성능을 높이기 위해서는 "이진 탐색 트리"와 같은 더 나은 방식을 사용하기도 합니다. 탐색 알고리즘의 기초 단위는 "항목"입니다. 이 항목은 간단한 숫자일 수도, 구조체가 될 수도 있습니다. 항목 안에는 항목과 항목을 구별하는 "키(Key)"가 존재하며 이를 "탐색 키(Search Key)"라고 합니다. 탐색은 바로 "탐색 키와 데이터로 이루어진 여러 항목..

정렬 알고리즘 개요 데이터를 특정한 조건에 따라 일정한 순서가 되도록 나열하는 것을 정렬이라고 합니다. 정렬 알고리즘은 프로그래밍에 있어 가장 기초적이며 또한 매우 중요한 알고리즘입니다. 정렬 알고리즘은 자료를 탐색함에 있어 필수적입니다. 정렬 알고리즘을 사용할 때, 정렬시켜야 하는 대상을 "레코드(Record)"라고 부르고 레코드는 "필드(Field)"라고 하는 단위로 나누어지니다. 이때 레코드와 레코드를 식별해주는 필드를 "키(Key)"라고 부릅니다. 정렬 알고리즘 종류 현재까지 개발된 정렬 알고리즘은 매우 많으나, 모든 경우에서 최적의 성능을 보이는 알고리즘은 존재하지 않습니다. 즉, 상황에 맞는 알고리즘을 택하여 사용해야 합니다. 이때 효율을 평가하는 기준은 정렬을 위해 필요한 "비교 연산의 횟수..

그래프 개요 오늘 다룰 그래프 자료구조의 대표적이 예시로는 지하철 노선도가 있습니다. 역들이 연결된 지하철 노선도를 그래프로 표현하면 특정 역에서 또 다른 역으로 가는 최단 경로를 계산할 수 있게 됩니다. 선형 리스트나 트리로는 표현하기 어려운 문제들을 그래프를 통하여 쉽게 해결할 수 있습니다. 지금부터 그래프 자료구조에 대해서 알아보도록 하겠습니다. 그래프의 정의와 용어 그래프는 객체 사이의 연결 관계를 표현할 수 있는 자료구조입니다. 그래프는 정점(Vertex)과 간선(Edge)의 집합입니다. 수학적으로는 $G = (V, E)$로 나타낼 수 있습니다. $V(G)$는 그래프 G의 정점들의 집합을 나타내며, $E(G)$는 그래프 G의 간선들의 집합을 나타냅니다. 지금부터 그래프 자료구조 를 이해하기 위하..

우선순위 큐의 정의 우선순위 큐는 "우선 순위" 개념을 큐에 적용한 자료구조입니다. 일반적인 큐는 선입선출의 원리에 따라 "가장 먼저 들어온 데이터가 가장 먼저 나가게 됩니다." 우선순위 큐는 일반적인 큐와 달리, 데이터들이 각각 우선 순위를 가지고 우선 순위가 높은 큐가 가장 먼저 나가게 됩니다. 이러한 우선순위 큐는 여러 방법으로 구현할 수 있는데, 배열, 연결 리스트, 히프 등을 사용하여 구현할 수 있습니다. 그 중, "히프"는 완전 이진 트리로서 우선순위 큐를 구현할 때 가장 많이 사용되는 자료구조입니다. 히프의 정의 히프는 우선순위 큐를 구현하기 위한 자료구조로서, 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내기 위해 만들어진 자료구조입니다. 다음과 같은 트리가 바로 히프..

이번 포스팅은 "트리와 이진 트리"에 대한 전반적인 이해도를 필요로 합니다. 트리와 이진 트리에 대해 잘 알지 못한다면 공부하고 그 후에 이 포스팅을 읽어주세요 여기에서 트리와 이진 트리에 대해서 공부할 수 있습니다. 이진 트리의 순회(Traversal) 이진 트리 또한 데이터를 저장하기 위한 자료구조입니다. 이진 트리를 순회한다는 것은 이진 트리에 있는 모든 노드를 방문하며 노드의 데이터를 목적에 맞게 처리하는 것을 의미합니다. 스택이나 큐, 연결 리스트 같은 선형 자료구조들은 데이터를 순차적으로 순회하는 방법은 하나뿐입니다. 그러나 계층적 구조를 가진 트리의 경우는 여러 가지 순서로 노드가 가진 데이터에 접근할 수 있습니다. 이진 트리를 순회하는 대표적인 방법으로는 "전위 순회", "중위 순회", "..

트리의 정의 우리가 여태 알아본 연결 리스트, 스택, 큐와 같은 자료구조들은 선형으로 나열된 선형 자료구조입니다. 반면 오늘 알아볼 "트리"는 대표적인 계층적 구조를 가진 자료구조입니다. 즉, 비선형 자료구조입니다. 비선형 자료구조는 자료들의 앞뒤 관계가 1:n 또는 n:n인 자료들을 구현하기에 적절합니다. "트리"는 이렇게 계층적인 구조를 표현하는데 아주 적합한 자료구조입니다. 트리 자료구조를 제대로 이해하기 위해서는 알아야 하는 용어들이 많습니다. 차근차근 살펴보도록 하겠습니다. 노드(Node): 트리의 구성 요소에 해당하는 A, B, C, D, E, F, G, H, I, J입니다. 루트(Root): 계층적인 구조에서 가장 높은 곳에 있는 노드(A)가 루트입니다. 서브트리(Sub-Tree): 기존의 ..