자료구조5 [자료구조] 연결 리스트(Linked List) 정리 1. 연결 리스트(Linked List)란?연결 리스트(Linked list)는 데이터를 저장하는 선형 자료구조로써, 각 구성 요소가 노드(Node)로 구성되어 있으며 하나의 노드(Node)에는 데이터가 저장된 부분과 다음 노드를 가리키는 포인터(Pointer)로 구성되어 있습니다.또한 연결 리스트의 시작지점을 가리키는 'Head'와 연결 리스트의 끝을 가리키는 Tail로 구성되어 있습니다.2. 연결 리스트(Linked list)의 종류연결 리스트의 종류는 크게 (1)Singly Linked List, (2)Doubly Linked List, (3)Circular Linked List가 있습니다. 이번 포스트에서는 Singly Linked List와 Doubly Linked List에 대해서만 다뤄보고.. 2024. 11. 10. [자료구조] 힙(Heap) 정리 1. 힙(Heap) 이란?Heap은 완전 이진트리의 한 종류로써, 우선순위 큐(Priority Queue)를 위해 고안된 자료 구조입니다. 특히, 다수의 자료에서 최소값과 최대값을 빠르게 찾을 수 있는 특징을 가지고 있습니다. 2. Heap의 종류최대 힙(Max Heap)최대 힙은 부모 노드의 값이 자식 노드 보다 크거나 같은 경우를 만족하는 완전 이진트리를 말합니다.(key(parents node) >= key(child node))부모 노드의 값이 항상 자식 노드보다 크거나 같기 때문에, root node는 항상 최대값을 가지게 된다.최소 힙(Min Heap)최소 힙은 부모 노드의 값이 자식 보드보다 작거나 같은 경우를 만족하는 완전 이진트리를 말합니다.(key(parents node) 부모 노드의.. 2024. 11. 8. [자료구조] 우선순위 큐(Priority Queue) 정리 1. 우선순위 큐(Priority Queue)란?우선순위 큐란, 큐(Queue)에 입력된 데이터를 우선순위에 따라 먼저 처리하고 싶은 경우에 사용합니다. 따라서 기존 FIFO(First In First Out)를 따르는 큐와는 다르게 순서와 상관 없이 우선순위가 높은 데이터가 먼저 나옵니다. 2. 우선순위 큐 구현방법우선순위 큐를 구현하는 방법은 크게 2가지가 있습니다. [1] 리스트(List)를 이용하여 구현하는 방법[2] 힙(Heap)을 이용하여 구현하는 방법2.1. 리스트를 이용하여 구현하는 방법리스트(List)를 이용하여 구현하게 되면 매우 간단히 구현할 수 있는 장점이 있습니다. 하지만, 리스트를 이용하여 구현하는 경우, 자료의 입출력의 속도는 선형적이므로(앞에서 부터 찾아가는 방법) 자료가 매.. 2024. 11. 7. [자료구조] 재귀(Recursion) 정리 1. 재귀(Recursion) 이란? 자료구조에서 재귀(recursion)는 함수의 실행 과정에서 자기 자신을 호출하는 함수를 의미합니다. Example : Factorial Function 재귀의 간단한 예시는 팩토리얼(Factorial) 함수를 예로 들 수 있습니다. 팩토리얼 함수를 수식으로 표현하면 다음과 같습니다. $$ f(n) = \begin{cases} 1 & n = 0 \newline n \cdot f(n-1) & else \end{cases} \quad where \ n \in \mathbb{Z}^+$$ 위 수식을 Python으로 구현하면 다음과 같이 구현해 볼 수 있습니다. 2. 재귀 함수 구현 시 주의사항 다음으로는 재귀함수를 작성할 때 반드시 포함되어야 하는 부분은 (1) Base c.. 2024. 2. 16. [Python] Stack(스택) 과 Queue(큐) 정리 및 예제 자료구조를 공부하다 보면 반드시 배우는 개념이 Stack & Queue입니다. # Stack Stack은 선입 후출 방식으로 가장 나중에 들어오는 데이터를 제일 먼저 반환하는 방식입니다. 파이썬으로 구현하는 방법은 리스트에 자료를 넣고 빼는 방식으로 구현하면 되며 자료를 넣을 땐 append함수를 이용하면 리스트에 넣는 순서대로 데이터가 들어가기 때문에 간단히 구현할 수 있습니다. 반대로 stack에서 데이터를 빼내는 과정은 가장 마지막 자료부터 빼야 합니다. 이때, 빼낸 자료는 리스트에 없어야 합니다. 이때 사용하는 함수는 pop 함수를 이용합니다. # Queue 다음으로 Queue는 Stack과는 다르게 선입선출 방식으로써 먼저 들어온 데이터를 먼저 처리하게 됩니다. 데이터를 넣는 방식은 Stack과.. 2022. 8. 23. 이전 1 다음
