컴맹탈출기/Data Structure (6) 썸네일형 리스트형 이진 탐색 트리 (Binary Search Trees) - 왼쪽 서브트리의 모든 값 bfs/dfs로 탐색, 찾은 노드+부모노드 함께 반환 -> 다른 함수에서 쓰.. 큐 (Queue) in Python 선입 선출 (FIFO - First In First Out) 선형 자료구조. 한쪽 끝에서 밀어 넣고 다른 쪽 끝에서 뽑아서 씀. [큐의 자료구조 구현 ] 1. 배열(array)를 이용하여 구현 class ArrayQueue: def __init__(self): self.data = [] #빈큐 초기화 def size(self): #큐의 크기 return len(self.data) def isEmpty(self): #큐가 비어있는지 return self.size()==0 def enqueue(self,item): #데이터에 원소를 추가 self.data.append(item) def dequeue(self): return self.data.pop(0) #데이터 원소를 삭제(리턴) def peek(self).. 후위 표기법 (Postfix Notation) 중위표기법 (infix notation) - 연산자가 피연산자들 사이에 위치 예) (a+b)*(c+d) 후위표기법 (postfix notation) - 연산자가 피연산자들의 뒤에 위치 예) ab+cd+* [중위 표현식을 후위 표현식으로 변경하기 (feat.스택)] a*b+c => ab*c+ a+b*c =>abc*+ //문자는 그 순서 그대로, (피연산자1)(피연산자2)(연산종류) 이 형태 유지 1) 스택에 넣기 피연산자인 경우 바로 print 연산자는 stack 에 push ->우선순위가 더 높(거나같 - 먼저나온게 우선임)은게 들어있다면(지금 넣는 것보다 먼저 해야 하니까), pop 하고나서 push ->우선순위가 더 낮은게 들어있다면, 지금 있는 것보다 위에 있어야 하므로 push 수식의 끝까지 왔을.. 양방향 연결리스트 (Doubly Linked List) in Python 연결리스트의 장점은 삽입과 삭제가 비교적 배열에 비해 자유롭다는 것이다. 그런데 왜 link는 한 쪽에 만 존재하고, 한 방향으로만 이동할수 있는 걸까? 뒤에서 앞으로 이동할 순 없는걸까? 이 문제를 해결하기 위해 양방향 연결리스트가 등장했다. 1. 노드의 구조 class Node: def __init__(self,item): self.data = item self.prev = None #새로 추가 된 앞으로 가는 링크 self.next = None 앞으로 가는 링크 prev가 추가됐다. 노드를 초기화할 땐 prev, next 모두 None으로 초기화해주자. 2. 양방향 연결리스트의 구조 -> 처음과 끝에 Dummy Node 추가! 이제 뒤에서도 앞으로 이동이 가능하므로, tail을 가리키는 dummy .. 스택(Stack) in Python [ 스택이란? ] - 자료를 보관할 수 있는 선형 구조. 한쪽 끝에서 밀어넣고(push) 같은 쪽에서부터 뽑아쓴다.(pull) - 후입선출(LIFO - Last In, First Out) [ 스택 언더플로우 & 스택 오버플로우 ] - 스택 언더플로우(stack underflow): 비어있는 스택에서 데이터 원소를 꺼내려고 할 때 발생하는 에러 - 스택 오버플로우(stack overflow): 꽉 찬 스택에 데이터 원소를 넣으려 할 때 발생하는 에러 [ 스택의 추상적 자료구조 구현 ] 1. 구현 방법 1) 배열 이용 - Python의 리스트와 메서드를 이용하여 스택을 구현한다. 2) 연결리스트 이용 - 양방향 연결리스트를 이용하여 스택을 구현한다. 2. 연산의 정의 1) size() - 현재 스택에 들어있.. 연결리스트 (Linked List) in Python 연결리스트는 말 그대로 연결된 리스트이다. 리스트(배열)자료구조에서 각 원소들이 호텔의 방에 하나씩 들어가 있었다면, 연결리스트에서 그 방들은 호텔에 갇힌것이 아닌, 독립적인 캠핑카가 된다. 그리고 서로의 꽁무늬에 'link'라는 연결고리를 달고 다니는데, 이 꼬리엔 아무것도 오지 않을 수도, 혹은 또 다른 캠핑카 한 대가 연결되어 기차같은 모양을 이룰수도 있다. [자료 구조 정의] 1. Node (캠핑카) class Node: def __init__(self,item): self.data = item #캠핑카에 탑승한 운전자 self.next = None #꽁무늬 (link 가 여기선 next) 초기화 item, next 는 각자 캠핑카에 탑승한 자료, 캠핑카의 뒤에 붙은 꽁무늬와 같다. 노드를 초기화.. 이전 1 다음