Python으로 구현하는 자료구조 : Queue (3) Priority Queue

이번 포슽팅에서는 자료구조 Queue의 한 종류인 Priority Queue(우선순위 큐)에 대한 특징을 살펴보고 파이썬으로 Priority Queue에 원소를 삽입, 삭제하는 코드를 짜보도록 하겠습니다. # Priority Queue란 Priority Queue(우선순위 큐)는 Dijkstra 알고리즘, Huffman 코딩, Prim 알고리즘 등 다양한 알고리즘에서 활용되는 자료구조입니다. Priority Queue의 각 원소들에게는 우선순위 값이 있으며, 이 값이 낮을 수록 급하게 처리해야 하는 데이터입니다. 보통 Queue는 들어오는 순서대로 원소들을 저장하지만, Priority Queue에서는 우선순위가 높은 원소가 먼저 나오도록 정렬되어 있습니다. # Priority Queue 구현하기 # 파이..
Data structure 2019. 5. 14. 09:30

Python으로 구현하는 자료구조 : Queue (2) Circular Queue

이번 포스팅에서는 자료구조 큐(Queue) 중에 Circular Queue(환형큐)에 대해 살펴보고 파이썬으로 Circular Queue를 구현하여 삽입(enqueue), 삭제(dequeue)하는 코드를 짜보도록 하겠습니다. # Circular Queue란 Queue 자료구조의 특성상 한쪽 방향에선 데이터가 들어가고 한쪽 방향에서는 데이터가 나가면서 뒤에 저장된 데이터들을 한 칸씩 모두 이동해야 하는 한계가 있습니다. 물론 Linked List를 통해 큐를 구현한다면 이러한 한계점을 극복할 수는 있지만 리스트를 사용해 Queue를 구현하고자 한다면 Circular Queue를 만들어 한계를 극복할 수 있습니다. Circular Queue는 번거로운 데이터 이동을 발생시키지 않고 주어진 공간을 활용할 수 ..
Data structure 2019. 5. 13. 09:00

Python으로 구현하는 자료구조 : Queue (1) Queue

이번 포스팅에서는 자료구조 큐(Queue)에 대한 특징을 살펴보고 파이썬으로 큐에 원소를 삽입, 삭제, 조회하는 코드를 짜보도록 하겠습니다. # Queue란? 큐란 목록 한쪽 끝에서만 자료를 넣고 다른 한쪽 긑에서만 자료를 빼낼 수 있는 자료구조 입니다. 먼저 집어넣은 데이터가 먼저 나오는 (FIFO : First in, First out) 구조로 데이터를 저장합니다. 데이터가 입력한 순서대로 처리되어야 할 경우에 사용합니다. 큐에 새로운 데이터가 들어오면 큐의 끝에 데이터가 추가되며(enqueue), 반대로 삭제될 때는 첫번째 위치의 데이터가 삭제됩니다(dequeue). # Queue의 종류는? 선형큐, 환형큐, 우선순위큐가 있습니다. 여기서는 기본적인 큐의 형태만 살펴보고 그 외의 큐는 다른 포스팅에..
Data structure 2019. 5. 12. 09:30

Python으로 구현하는 자료구조 : Heap

Python으로 Heap을 구현해보고 Heap 자료구조의 특징과 데이터의 삽입과 삭제에 대해 알아보도록 하겠습니다. # Heap이란 힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조입니다. 힙에는 두가지 종류가 있으며, 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙을 '최대 힙', 부모노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙을 '최소 힙'이라고 부릅니다. 원소 값의 대소 관계는 오로지 부모 노드와 자식 노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않습니다. 힙에서는 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 뿌리 노드에 오게 되는 특징이 있으며, 이를 응용하면 우선순위 큐와 같은 추상적..
Data structure 2019. 5. 11. 09:00

Python으로 구현하는 자료구조 : Linked List (3) Circular linked list

이 포스팅에서는 Circular linked list의 특징을 알아보고 파이썬으로 Circular linked list의 삽입, 삭제, 조회를 구현해보도록 하겠습니다. # Circular linked list란 환형 연결 리스트라고도 부르는 이 연결 리스트는 머리와 꼬리가 연결되어 순환 구조를 지닙니다. 환형 연결 리스트라는 것은 Node에 포인터 공간이 두 개 일수도 있고, 한개 일수도 있으며 포인터 공간의 개수가 중요한 것이 아니라 노드의 Next가 None인 경우가 없이 끊임 없이 이어진다는 의미입니다. 따라서 노드가 한개인 경우에도 무한대로 순환할 수 있습니다. # Circular linked list 구현하기 # 삽입 # 삭제 # 파이썬 코드 1 2 3 4 5 6 7 8 9 10 11 12 13..
Data structure 2019. 5. 10. 09:30

Python으로 구현하는 자료구조 : Linked List (2) Doubly linked list

이 포스팅에서는 Doubly linked list의 특징을 알아보고 파이썬으로 Doubly linked list의 삽입, 삭제, 조회를 구현해보도록 하겠습니다. # Doubly linked list 란? Doubly linked list는 각 노드에 자료 공간과 두 개의 포인터 공간이 있고, 각 노드의 포인터는 이전 노드와 다음 노드를 가리킵니다. # 이중 연결 리스트의 특징, 장점, 단점은요 단순 연결리스트와 이중 연결 리스트의 차이는 prev를 가리키는 포인터 공간이 추가되면서 이전 노드에 대한 정보를 알 수 있다는 점입니다. 이로인해 단순 연결 리스트로는 할 수 없는 역으로 출력하는 것이 가능하고, 특정 노드의 이전 노드를 삭제하거나 특정 노드의 이전에 삽입하는게 가능해졌습니다. 그러나 단순 연결 ..
Data structure 2019. 5. 9. 19:00

Python으로 구현하는 자료구조 : Linked List (1) Singly linked list

Linked list(연결 리스트)는 (데이터와 다음 노드의 주소를 담고 있는) 노드들이 한 줄로 연결되어 있는 방식의 자료 구조입니다. 연결되는 방향에 따라, (1) Singly linked list (단일 연결 리스트), (2) Doubly linked list (이중 연결 리스트), (3) Circular linked list (환형 연결 리스트)가 있습니다. 이 포스팅에서는 Linked list와 Singly Linked list 의 특징을 알아보고 파이썬으로 Singly Linked list의 삽입, 삭제, 조회를 구현해보도록 하겠습니다. # Linked list란? Linked List는 데이터를 노드의 형태로 저장합니다. 노드에는 데이터와 다음 노드를 가르키는 포인터를 담은 구조로 이루어져 ..
Data structure 2019. 3. 31. 02:00

Python으로 구현하는 자료구조 : Stack

Python으로 Stack을 구현해보고 Stack 자료 구조의 특징과 데이터의 삽입과 삭제에 대해서 알아보도록 하겠습니다. # Stack 이란 Stack은 데이터의 삽입과 삭제가 저장소의 맨 윗 부분(the top of stack)에서만 일어나는 자료구조입니다. 스택은 데이터가 순서대로 저장되고 스택의 마지막에 넣은 요소가 처음으로 꺼내집니다(LIFO : Last-in, First-out"). Stack은 연속으로 저장된 데이터 구조를 가지고 있고 맨 위 요소에 대한 포인터(주소값)을 가지고 있는 Array나 singly linked list로 구현할 수 있습니다. Stack의 장점은, (1) 참조 지역성(한번 참조된 곳은 다시 참조될 확률이 높다)을 활용할 수 있다는 점이며, Stack의 단점은, (1..
Data structure 2019. 3. 31. 01:28

Python으로 구현하는 자료구조 : Array

Array Python Array 자료형의 특징과 삽입, 삭제, 조회(검색) 하는 방법에 대해 알아보도록 하겠습니다. Python은 Array를 기본 자료형으로 제공하지 않습니다. 따라서 Array을 사용하고 싶다면 NumPy와 같은 패키지를 추가로 설치해야만 합니다. 이 포스팅에서는 NumPy를 따로 설치하여 사용하지 않고 Python의 기본 컨테이너 중 하나인 List를 Array 대신 사용해보도록 하겠습니다. # Array는 무엇인가요 Array는 여러 원소들이 순차적으로 메모리에 저장(contiguous memory locations)하는 구조입니다. 기본적으로 배열은 모든 원소가 같은 자료형이어야 하며, 배열의 크기를 변경할 수 없습니다. Array를 담은 변수에는 배열의 첫 원소의 메모리 주소..
Data structure 2019. 3. 30. 16:00