이것 저것 뚝딱거리는 사람 이것 저것 뚝딱거리는 사람

해시 이번에는 해시, 해시테이블에 대해서 알아보자 이전에 배웠던 자료형들은 값을 여러가지 형태로 저장할 수 있었다. 그러나 원하는 자료형을 찾기란 쉽지않다. 예를들어 리스트에서 원하는 값을 찾기 위해서는 앞에서부터 순서대로 순회해야하며, 힙의 경우에서도 최소값, 최대값을 찾을 수 있을 뿐, 원하는 값을 찾을 수는 없다. 그래서 이번에 배울 자료형인 해시는 색인이 쉽게 만들어 졌다. 해시의 원리 해시는 값과, 이 값을 찾기위한 key를 사용한다. 파이썬의 딕셔너리와 비슷하다고 생각할 수 있는데, 딕셔너리도 해시로 이루어져있다. 가장 먼저 키를 해시함수에 입력한다. 해시함수는 키를 입력받아서 숫자로된 인덱스를 결과로 내는 함수이다. 해시함수의 출력으로 인덱스가 나오면 리스트와 비슷한 자료형 테이블의 인덱스 ..

그래프 트리와 같이 노드와 간선으로 연결된 형태를 그래프라고 한다. 싸이클이 형성될 수 있기 때문에 계층적 자료구조라기 보다는 전체를 나타내는 형태로 생각할 수 있다. 따라서 부모-자식 관계나 루트노드 같은 성질이 없다. 위 그림에서 A-B-E-C-A의 사이클이 있다. 그래프에는 여러가지 특징이 있다. 먼저, 방향이 있는 그래프와 방향이 없는 그래프로 나눌 수 있다. 위에서 그린 그래프는 방향이 없는 그래프이고, 방향이 있는 그래프는 다음과 같다. 방향이 있을 때는 해당 방향으로만 진행할 수 있다는 특징이 있다. 다음으로는 모든 노드가 연결되어있지 않아도 된다는 것이다. 이를 비연결그래프, disjoint 그래프라 한다. 반면 모든 노드가 서로 연결되어있는 그래프는 완전그래프라 한다. 간선에 가중치를 둘..

Heap 최대값, 혹은 최소값을 빠르게 찾기 위한 자료구조이며, 일반적으로 완전이진트리를 활용하여 구현하고, 우선순위 큐에 사용한다. 우선순위 큐란 FIFO구조의 일반적인 큐가 아니라, 각 데이터에 우선순위가 있어서, 우선순위가 높은 데이터가 먼저 POP되는 자료형태이다. 예를 들어 운영체제에서 프로그램들을 스케쥴링 할 때, FIFO방식으로 프로세스를 처리한다면, 처리시간이 긴 프로세스를 처리하는 동안 처리시간이 짧은 프로세스는 대기시간이 길어지게 되고, 이는 비효율적이다. 따라서 처리시간이 짧은 프로세스에 높은 우선순위를 두어 이를 먼저 처리하고, 처리시간이 긴 프로세스를 나중에 처리하려고 할 때 우선순위 큐를 사용할 수 있다. Heap의 구조 힙은 두가지로 나뉜다. 루트노드가 가장 작은 값인 Min ..

이진 탐색 트리 앞으로 글을 쓰겠지만 선형 자료 구조에서는 원하는 값을 탖는 방법이 여러가지가 있다. 가장 먼저 생각할 수 있는 것은 앞 혹은 뒤에서부터 하나씩 살펴보는 선형탐색이다. 그렇다면 트리형 자료구조에서는 원하는 값을 어떻게 찾을 수 있을까? 가장 기초적인 방법이 바로 이진탐색 트리이다. (물론 모두 살펴볼 수도 있을 것이다.) 먼저 그림부터 보자. 루트 노드에 값 K가 담겨있다고 생각하자. 그렇다면 이 루트 노드의 왼쪽에 있는 서브 트리에는 K보다 작은 값이, 오른쪽에는 K보다 큰 값만이 들어있는 트리를 생각할 수 있고, 이 모든 서브트리에도 같은 생각이 적용된다면 원하는 값을 찾기가 쉬울 것이다. 이를 이진 탐색 트리라 한다. 실제 값을 넣어서 확인해보자 위 트리에서 13을 찾고 싶다고 생각..

트리 단순 선형 자료구조에서는 계층을 나타내기가 어렵다. 따라서 계층적 자료구조를 만들기 위해서 트리를 생각했다. 값을 가지는 노드와, 노드 사이를 잇는 간선으로 이루어져 있으며, 부모 - 자식 관계를 가진다. 트리를 그림으로 나타내면 위와 같다. 여기서 A - B, C, D의 관계를 부모 - 자식 관계라 하며, 마찬가지로 B - E, F의 관계도 부모 - 자식 관계이다. 가장 위에 있는 노드인 A를 루트(Root)노드라 하고, 자식이 없는 노드들(E, F, C, G)를 리프(Leaf)노드라 한다. 위의 트리는 3개의 층으로 되어있는데, 이를 높이가 3인 트리라고 한다. 트리는 서브트리로 나눌 수 있다. 이렇게 나누면 B와 D는 각각의 서브트리에서 루트노드가 된다. 트리의 자식이 연결되어 싸이클이 생기면..

LinkedList 대표적으로 C같은 경우 선형 자료구조인 Array가 있다. 그러나 이 배열의 경우는 시작부터 크기를 지정해주어야하고, 새로운 요소를 추가하거나, 배열 안의 요소를 제거할 때 비용(시간)이 많이 든다. 이를 개선하기 위해서 구조체를 만드는데, 이 구조체에는 하나의 요소 값과, 다음 구조체의 정보를 가진다. 이 구조체를 연결하여 만드는 리스트가 바로 LinkedList이다. LinkedList를 사용함으로써 크기가 유동적인 자료형을 만들 수 있고, 삽입, 제거에 시간이 적게 든다. 특히 값을 탐색하다가 데이터를 추가, 제거하기에 용이하다. 단점으로는 index가 없어 값을 앞에서부터 탐색해야 한다. -> 탐색에 시간이 많이 소요된다. 종류로는 단순(Single), 양방향(Double)이 ..

Queue 한쪽 끝으로 데이터를 넣고 반대쪽 끝으로 데이터가 나오는 FIFO(First In First Out)형식의 자료 구조 사용 사례 데이터를 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용(대기열) 캐시(Cache) 프로세스 관리 코드와 연산 # 리스트 형태의 큐 # 큐 생성 queue = [] # 큐에 값 추가 (enqueue) queue.append(1) # 큐에서 값 제거 후 반환 (dequeue) queue.pop(0) 파이썬 기본 모듈을 이용한 큐 import queue # 큐 생성 q = queue.Queue() # 큐에 요소 추가 q.put(123) # 큐에서 요소 제거 후 반환 q.get() queue — 동기화된 큐 클래스 — Python 3.9.10 문서 queue —..