본문 바로가기

분류 전체보기142

[Vector/List]17. Vector ADT 목차 1. Vector ADT 2. Application of Vector 3. Array-based Vector 1. Vector ADT Vector ADT(벡터)는 배열과 비슷하며, 여러 특징을 지니고 있습니다. 1) 특징 - 초기에 크기 지정을 하지 않는다. - Vector의 element는 index에 따라서 접근되거나, 삽입/삭제 된다. 2) 주요 기능 - at(int i): index i에 저장되어 있는 element를 반환한다. - set(int i, object o): index에 저장되어 있는 element를 o로 바꾼다. - insert(int i, object o): 새로운 element o를 index i 자리에 삽입한다. - erase(int i): index i의 위치하고 있는 .. 2021. 2. 21.
[Queue]16. Array-base Queue 구현 목차 1. class Queue_array 2. 테스트 1. class Queue_array class Queue_array: def __init__(self): self.queue = [] # queue 저장할 리스트 self.f = 0 # queue의 front idx self.r = -1 # queue의 rear idx def size(self)-> int: # queue의 크기 반환하는 함수 return len(self.queue) def empty(self)-> bool: # queue가 비어있는지 여부를 반환하는 함수 return len(self.queue)==0 def front(self)-> object: # front의 element를 반환하는 함수 if self.empty(): # qu.. 2021. 2. 20.
[Queue]15. Queue 종류 목차 1. Array-base Queue(배열 기반 큐) 2. Array-base Circular Queue(배열 기반 원형 큐) 3. Linked list-base Queue(연결 리스트 기반 큐) 1. Array-base Queue(배열 기반 큐) Array-base Queue(배열 기반 큐)는 제목과 같이, queue를 array에 저장하는 방식을 말합니다. 위의 그림과 같이 배열의 앞부분을 front, 뒷부분을 rear로 놓고 사용합니다. 일반 배열 기반 큐의 특징은 값을 계속 enqueue할 경우, 앞의 메모리 공간이 비어있는 상태로 방치된다는 단점이 있습니다. 물론 파이썬을 기반으로 구현하면 그렇지 않지만, c++, java 등 array를 선언할 시 배열의 크기가 정해지는 경우, 이는 심각한.. 2021. 2. 20.
[Queue]14. Queue(큐) 목차 1. Queue(큐) ADT 2. Applications of Queue(활용하는 곳) 1. Queue(큐) ADT Queue(큐) ADT는 줄서기 알고리즘이라고 생각하면 됩니다. 1) 특징 - 임의의 데이터를 저장한다. - FIFO(First In First Out, 먼저 들어간 데이터가 먼저 나옴), 선입선출의 개념을 따른다 - rear(데이터가 들어오는 곳)에서 insertion이 이루어지며, front(데이터가 나가는 곳)에서 removal이 이루어짐 2) 주요 기능 - enqueue(object): element를 insert하는 함수(queue의 end에) - dequeue(): element를 remove하는 함수(queue의 front에서) 3) 부가 기능 - object front(.. 2021. 2. 20.
[Stacks]13. 후위 표기식 연산 구현 (Stack 응용) 목차 1. 중위 표기법, 후위 표기법 2. 후위 표기식 연산 방법 3. class Cal_post_fix 4. 테스트 1. 중위 표기법, 후위 표기법 1) 중위 표기법(Infix Notation) - 연산자를 피연산자의 가운데 표기하는 방법을 말한다. ex) A+B, A*B-C/D, A-B*C+D 2) 후위 표기법(Postfix Notation) - 연산자를 피연산자 뒤에 표기하는 방법을 말한다. ex) AB+, AB*CD/-, ABC*-D+ 2. 후위 표기식 연산 방법 후위 표기식을 입력받아 연산하는 방법은 다음의 과정과 같다. 1. 피연산자를 만나면 스택에 push한다. 2. 연산자를 만나면 필요한 만큼의 피연산자를 스택에서 pop하여 연산하고, 연산 결과를 다시 스택에 push한다. 3. 수식이 끝.. 2021. 2. 20.
[Stacks]12. Linked list-based Stack(연결 리스트 기반 스택) 구현 목차 1. Linked list-based Stack(연결 리스트 기반 스택) 구현 2. class Node, S_linked_list 3. class Stack_linked 4. 테스트 1. Linked list-based Stack(연결 리스트 기반 스택) 구현 Linked list-based Stack을 구현할 경우, 1. Singly linked list를 구현한다. 2. append, pop은 모드 singly linked list의 head에서 이루어진다. 3. 이를 기반으로 스택 알고리즘을 구현한다. Singly linked list를 활용하여 스택 알고리즘을 구현할 경우, head에서 append와 pop을 진행하야한다는 사실만 주의하면 됩니다. 지난 Linked list 게시물에서도 언급.. 2021. 2. 20.
[Stacks]11. Array-based Stack(배열 기반 스택) 구현 목차 1. Array-based Stack(배열 기반 스택) 구현 2. 실제 구현 3. size() 4. empty() 5. top() 6. push() 7. pop() 8. 테스트 1. Array-based Stack(배열 기반 스택) 구현 Array를 기반으로 Stack ADT 알고리즘을 구현할 경우 1. 임의의 크기의 array를 선언한다 2. 해당 array의 0번째 부터 들어오는 element를 저장한다. 3. 현재 위치를 t로 저장하며, 해당 위치에서 element를 호출되는 기능에 따라 추가하고, 삭제한다. Array를 기반으로 Stack ADT 알고리즘을 구현할 경우, 가장 큰 문제점이 바로 Array의 최대값에 다다랐을 경우입니다. 이와 같은 경우를 ADT에서 설명하지는 않지만, 구현하고.. 2021. 2. 19.
[Stacks]10. Stack ADT(스택) 목차 1. Abstract Data Types(ADTs, 추상 자료형) 2. Stack ADT(스택) 3. Applications of Stack(활용하는 곳) 4. Performance and Limitations 1. Abstract Data Types(ADTs, 추상 자료형) Abstract Data Types(ADTs, 추상 자료형)은 특정 자료구조에 명세된 내용을 의미합니다. 즉, 각각의 ADT는 1. 해당 ADT가 어떤 자료를 지니고 있는지 2. 해당 ADT가 어떤 기능을 취할 수 있는지(탐색, 삽입, 삭제 등...) 이 두가지 해당사항(가이드라인)을 제시해 주는 것을 말합니다. 2. Stack ADT(스택) 위에서 언급한 ADT의 한 종류인 Stack ADT(스택)은 여러 특징들을 가집니다... 2021. 2. 19.

티스토리툴바