해시 테이블(Hash Table)이란?해시 테이블은 (Key, Value)식으로 데이터를 저장하는 자료구조 중 하나로 key를 통해 평균 O(1)에 value를 검색할 수 있는 자료구조이다.해시 테이블은 Key 값을 해시함수(Hash Function)를 사용하여 변환한 값을 색인(index)으로 삼는다.해시 함수(Hash Function)를 사용해 Key 값을 색인(index)으로 변환하는 과정을 해싱(Hashing)이라고 한다. 해시 함수(Hash Fucntion)해시 함수의 가장 중요한 점은 고유한 인덱스를 만드는 것이다. 만약 중복되는 인덱스가 발생한다면 이는 충돌(Collision)로 이어지게 된다. 따라서 해시 함수를 구현하는 해시 알고리즘을 적절히 구현하는 것이 중요하다. 해시 테이블에 사용되..
그래프란?그래프는 연결되어 있는 원소 사이의 다대다 관계를 표현하는 자료구조이다.그래프 G는 객체를 나타내는 정점 V(vertex)와 객체를 연결하는 간선 E(edge)의 집합이다.트리도 그래프의 한 종류이며, 그 중 사이클(cycle)이 허용되지 않는 그래프를 말한다.그래프의 종류방향 그래프 vs 무방향 그래프간선에 방향이 있는 그래프는 방향 그래프(Directed Graph) 라고 하고, 간선에 방향이 없는 그래프를 무방향 그래프(Undirected Graph) 라고 한다.완전그래프완전 그래프(Complete Graph)는 각 정점에서 다른 모든 정점이 연결된, 최대한 많은 간선 수를 가진 그래프를 뜻한다.정점이 N개인 무방향 그래프에서 최대 간선 수 : N(N-1)/2 개 ( ex : 위 그림에서 ..
힙(Heap)이란?힙이란 완전이진트리의 일종으로 여러 값들 중 최댓값 혹은 최솟값을 빠르게 찾아내기 위한 자료구조이다.힙은 중복된 값을 허용한다.Max Heap 은 가장 큰 값을 빠르게 찾기 위한 것이고 Min Heap 가장 작은 값을 빠르게 찾기 위한 것이다.완전이진트리가 무엇인지 모르겠다면 다음을 참고하자. [자료구조] 트리(Tree)의 개념, 이진 트리, 전 이진 트리, 완전 이진트리, 포화 이진 트리, 이진 탐트리(Tree)의 개념트리는 노드로 이루어진 자료구조로 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다.트리는 계층적 관계를 표현하는 자료구조이다.트리는 다음과 같은 특징들을 갖code-lab1.tistory.com Max Heap(최대 힙)Max Heap 은 부모 노드의 키 값이..
이진탐색트리(Binary Search Tree)이란?이진탐색트리란 다음과 같은 특징을 갖는 이진트리를 말한다. ( #이진트리 - 각 노드의 자식 노드가 최대 2개인 트리)1. 각 노드에 중복되지 않는 키(key)가 있다.2. 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다.3. 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다.4. 좌우 서브 트리도 모두 이진 탐색 트리여야 한다.예를 들어 다음과 같은 트리가 이진탐색트리이다.이진 탐색 트리의 특징이진 탐색 트리는 기존 이진트리보다 탐색이 빠르다. 이진 탐색 트리의 탐색 연산은 트리의 높이(height)가 h라면 O(h)의 시간 복잡도를 갖는다. 이러한 효율적인 탐색이 가능한 이..
트리의 순회이 게시글에서 설명하는 트리의 순회는 이진트리를 기준으로 한다. 이진 트리에 대해 모른다면 다음 포스팅을 참고하자. [자료구조] 트리(Tree)의 개념, 이진 트리, 전 이진 트리, 완전 이진트리, 포화 이진 트리, 이진 탐색트리 [자료구조] 트리(Tree)의 개념, 이진 트리, 전 이진 트리, 완전 이진트리, 포화 이진 트리, 이진 탐트리(Tree)의 개념트리는 노드로 이루어진 자료구조로 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다.트리는 계층적 관계를 표현하는 자료구조이다.트리는 다음과 같은 특징들을 갖code-lab1.tistory.com 트리의 순회 중 중위(inorder) 순회, 전위(preorder) 순회, 후위 순회(postorder) 순회에 대해 알아보자.여기서 설..
트리(Tree)의 개념트리는 노드로 이루어진 자료구조로 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다.트리는 계층적 관계를 표현하는 자료구조이다.트리는 다음과 같은 특징들을 갖는다.1. 트리는 하나의 루트 노드를 갖는다.2. 루트 노드는 0개 이상의 자식 노드를 갖는다.3. 자식 노드 또한 0개 이상의 자식 노드를 갖는다.4. 노드(Node)들과 노드들을 연결하는 간선(Edge)들로 구성되어 있다.트리에는 사이클(cycle)이 존재할 수 없다. 여기서 사이클이란 시작 노드에서 출발해 다른 노드를 거쳐 다시 시작 노드로 돌아올 수 있다면 사이클이 존재한다고 한다.트리는 사이클(cycle)이 없는 하나의 연결 그래프(Connected Graph)라고 할 수 있다.트리의 노드는 self-loop가 ..
큐(Queue) 란?큐는 컴퓨터의 기본적인 자료구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 형식을 말한다. 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다.스택은 아래 부분이 막히고 윗 부분이 뚫린 통과 같았다면, 큐는 양 쪽이 뚫린 통과 같다. 스택이 가장 윗부분에서 데이터를 넣고 꺼냈다면, 큐는 front 에서 Dequeue(데이터를 꺼냄) 연산이 진행되고, rear 부분에서 Enqueue(데이터를 넣음) 연산이 진행된다.c언어 구현큐는 배열 혹은 연결리스트로 구현할 수 있다. 배열로 구현할 시에는 여러가지 문제점이 발생할 수 있다. 여기서는 연결리스트를 이용해 큐를 구현해보도록 한다.1. 노드 정의, 큐 초기화..
배열(Array)배열은 논리적 저장순서와 물리적 저장순서가 일치하는 자료구조이다. 즉 인덱스(index)로 해당 원소에 접근 할 수 있다. 따라서 원소의 인덱스값을 이용하면 O(1)에 해당 원소에 접근 할 수 있다. 그러나 삭제 또는 삽입의 과정에서 추가적인 시간이 소요될 수 있다. 예를 들어 아래와 같은 상황에서 배열의 첫번째 자리(Arr[0])에 새로운 원소를 추가한다고 하자. 위와 같은 상황에서 Arr[0] 에 데이터 10을 추가하기 위해서는, Arr[0] 부터 Arr[4] 까지 모든 원소가 한 칸 씩 오른쪽으로 이동하게 된다.즉, 원소를 삽입할 때 최악의 경우 모든 원소들을 1씩 옮기는 작업이 필요할 수 있다. 따라서 배열의 삽입은 O(n) 의 시간을 요구하게 된다. 마찬가지로 삭제의 경우도 O(..
연결리스트(Linked List)란?연결리스트(Linked List)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다.- 각 노드는 다음 노드를 가리키는 포인터를 포함한다. - 다음 노드를 가리키는 포인터는 다음 노드의 주소를 값으로 가지고 있다. - 각 노드의 포인터 변수는 다음 노드의 데이터의 주소를 값으로 가진다. 또한 각 포인터 변수의 주소도 따로 존재한다.(그림에 나타난 주소는 정확하지 않다. 이해를 돕기 위해 임의로 설정했다. 실제 주소값은 저런식으로 저장되지 않는다)단순연결리스트(Singly Linked List)의 구현가장 간단한 연결리스트인 단순 연결리스트를 구현해보자. 여러 구현 방법이 있지만, 아래 내용들을 응용하면 다양한 연결리스트..
B- 트리란?보통 B 트리라고 하면 B- 트리를 의미한다. B 트리는 트리 자료구조의 일종으로 이진트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. 이러한 B 트리의 다음과 같은 특징을 그림과 함께 알아보자. 1. 노드에는 2개 이상의 데이터(key)가 들어갈 수 있으며, 항상 정렬된 상태로 저장된다. [그림 1]처럼 한 노드에 2개, 3개의 데이터가 들어가 있을 수 있으며, 항상 정렬된 상태로 저장된다. 2. 내부 노드는 ceil(M/2) ~ M개의 자식을 가질 수 있다. 최대 M개의 자식을 가질 수 있는 B 트리를 M차 B트리라고 한다. [그림 1]은 3차 B트리를 나타낸다. ceil() 함수는 올림 함수를 뜻한다. 즉, ceil(3/2) = 2이다..