사진과 음악을 좋아하는 개발자 지망생의 블로그

1) 큐(Queue) - 한쪽 끝에서 삽입이 이루어지고(인큐, Enqueue) 다른 한쪽에선 삭제 연산(디큐, Dequeue)만 이뤄지는 선형의 자료 구조 - 선입선출(FIFO, First In, First Out) 특징을 가지는 선형 자료구조 ex) 대기열 2) 큐(Queue) 자료구조 구현 ① 배열(array, list)을 이용하여 구현 → Python List 와 method들을 이용 class ArrayQueue : def size(self) :# 현재 큐에 들어 있는 데이터 원소의 수 return len(self.data) def isEmpty(self) :# 현재 큐가 비어 있는지를 판단 return self.size() == 0 def enqueue(self, item) :# 데이터 원소 i..

1) 스택(Stack) - 자료(Data element)를 단방향을 보관할 수 있는 (선형) 구조 - 단방향이므로 자료를 넣고(Push) 꺼낼 때(Pop) 한 쪽으로만 수행해야하는 제약이 있음 => 후입선출(LIFO) ※ Stack에서 발생하는 오류 - 비어 있는 스택에서 데이터 원소를 꺼내려 할 때 → Stack Underflow - 꽉 찬 스택에 데이터 원소를 넣으려 할 때 → Stack Overflow 2) 스택의 추상적 자료구조 구현 ① 배열(array, list)을 이용하여 구현 → Python List 와 method들을 이용 class ArrayStack : def size(self) :# 현재 스택에 들어 있는 데이터 원소의 수 return len(self.data) def isEmpty(..

3) 양방향(Doubly) 연결 리스트 ① 양방향 연결 리스트 정의 - 단반향 리스트와 달리 앞과 뒤(양방향)으로 리스트 접근이 가능하다 def __init__(self, item) : self.data = item self.prev = None self.next = None - 삽입 및 정렬 연산에서 head 및 tail에서 연산할 시 리스트 처음과 끝에 Dummy Node를 둠으로써 양방향 연결 리스트를 형성한다 def __init__(self): self.nodeCount = 0 self.head = Node(None) self.tail = Node(None) self.head.prev = None self.head.next = self.tail# Doubly self.tail.prev = self..

연결리스트 2) Dummy Head를 가지는 연결 리스트 ① Dummy Head 개요 - 연결 리스트는 삽입 및 삭제가 유연하게 이뤄질 수 있다는 장점 있음 - 하지만, 리스트의 길이가 길어질수록 실행 시간이 늘어난다 - 이러한 단점을 보완하기 insertAfter(prev, newNode), popAfter(prev)와 같은 메소드를 만든다 - insertAfter(prev, newNode), popAfter(prev)는 prev가 Head일 시 어떻게 처리해야할 지에 대한 문제가 생김 - 이러한 문제를 해결하기 위해 Dummy Node를 추가하고 Dummy Node를 '0'번으로 정함 class LinkedList : def __init__(self) : self.nodeCount = 0 self.h..

리스트(List) 1) 리스트(List) - 여러 개의 데이터를 하나의 변수로 저장 및 관리할 때 사용되는 집합 - 리스트 내 서로 다른 자료형의 데이터들을 저장할 수 있을 정도로 배열 보다 높은 융통성을 갖는다 - 배열과 마찬가지로 각 원소들엔 index라는 번호가 붙여진다 2) 리스트(List)관련 method 정리 ① 원소 추가하기 - append(x) : list 끝에 요소x를 추가함 ※ append(x) vs +=(+) * +=는 append method 보단 extend method에 더 가깝다.(두 list를 합쳐 새로운 list를 만듬) * 반면, append는 하나의 list 끝에 항목을 추가함. * 따라서, 겉으론 += 연산이 깔끔해 보일 수 있으나 append method를 사용하는 ..