해시 테이블(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)의 구현가장 간단한 연결리스트인 단순 연결리스트를 구현해보자. 여러 구현 방법이 있지만, 아래 내용들을 응용하면 다양한 연결리스트..
블로그 이사합니다아래에서 확인 가능합니다.https://code-lab1.com/dma/ [운영체제] DMA(Direct Memory Access)란? (DMA vs PIO) - 코드 연구소DMA는 말 그대로 메모리(Memory)에 직접 접근하는 방식을 뜻한다. 이때 CPU는 데이터 전송에 전혀 관여하지 않는다는 점이 중요하다. DMA는 주변장치들이 메인 메모리와 직접 데이터를 공유할 수 있code-lab1.com PIO(Programmed I/O)PIO는 주변장치들(I/O device) 사이 전송되는 모든 데이터가 CPU를 거쳐간다. 이때 CPU는 주변 장치들에 대한 지속적인 모니터링을 통해 주변 장치들이 준비가 됐는지 체크하기 때문에불필요하게 CPU 주기를 낭비하고 "Busy" 상태가 빈번하게 된다..