본문 바로가기

Python/Data Structure & Algorithm in Python16

[Python] 자료구조와 알고리즘 기초 - 재귀 알고리즘, 동적 계획법, 연결리스트, 스택, 큐, 이진트리 Contents 선형 배열(Linear Array) 정렬(Sort) 탐색(Search) 재귀 알고리즘 동적계획법 연결리스트 양방향 연결리스트 스택 큐 환형큐 우선순위 큐 이진 트리 이진 탐색 트리 힙 선형 배열(Linear Array) #Python 리스트에 활용할 수 있는 연산들 (1) 리스트 길이과 관계 없이 빠르게 실행 결과를 보게되는 연산들 원소 덧붙이기 .append() 원소 하나를 꺼내기 .pop() (2) 리스트의 길이에 비례해서 실행 시간이 걸리는 연산들 원소 삽입하기 .insert() 원소 삭제하기 .del() #리스트에서 원소 찾아내기 Example 1: Input: L = [64, 72, 83, 72, 54] x = 72 Output: [1, 3] Example 2: Input: L .. 2020. 9. 12.
[Python 자료 구조] 힙 (Heaps) #힙과 이진 탐색 트리 비교 구분 힙 이진 탐색 트리 원소들은 완전히 크기 순으로 정렬되어 있는가? X O 특정 키 값을 가지는 원소를 빠르게 검색할 수 있는가? X O 부가의 제약 조건은 어떤 것인가? 완전 이진 트리이어야 한다. #연산의 정의 init() : 비어 있는 최대 힙을 생성 insert(item) : 새로운 원소를 삽입 remove() : 최대 원소(root node)를 반환하고 삭제 #배열을 이용한 이진 트리의 표현 class MaxHeap: def __init__(self): self.data = [None] #최대 힙에 원소 삽입 (1) 방법 - 트리의 마지막 자리에 새로운 원소를 임시로 저장 - 부모 노드의 키 값을 비교하여 위로, 비교하고 위로 이동 (2) 복잡도 - 원소의 개수가.. 2020. 9. 11.
[Python 자료 구조] 이진 탐색 트리 (Binary Search Trees) #이진 탐색 트리이진 탐색 트리 (Binary Search Trees) - 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고, 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰 성질을 만족하는 이진트리 (중복되는 데이터 원소는 없는 것으로 가정) #연산의 정의 insert(key, data) : 트리에 주어진 데이터 원소를 추가 remove(key) : 특정 원소를 트리로 부터 삭제 lookup(key) : 특정 원소를 검색 inorder() : 키의 순서대로 데이터 원소를 나열 min(), max() : 최소 키, 최대 키를 가지는 원소를 각각 탐색 #insert(key, data) class Node: def insert(self, key, data): if key < self... 2020. 9. 11.
[Python 자료구조] 이진 트리 (Binary Trees) #연산의 정의 size() : 현재 트리에 포함되어 있는 노드의 수를 구함 depth() : 현재 트리의 깊이(또는 높이;height)를 구함 순회(traversal) #이진 트리의 구현 - size() # 이진트리의 구현 - 노드(node) class Node: def __init__(self, item): self.data = item self.left = None self.right = None # 이진 트리의 구현 - 트리(tree) class BinaryTree: def __init__(self, r): self.root = r class Node: # 이진 트리의 크기 - 재귀함수 이용 def size(self): l = self.left.size() if self.left else 0 # 왼.. 2020. 9. 10.
[Python 자료 구조] 우선순위 큐 (Priority Queues) #우선순위 큐 (Priority Queues) - 큐가 FIFO(First-In-First-Out) 방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 방식 #우선순위 큐 구현 방식 - (1) Enqueue할 때 우선순위 순서를 유지하도록 vs (2) Dequeue할 때 우선순위 높은 것을 선택 - (1) 가 더 유리, (2)는 모든 원소를 다 살펴보아야 함 #우선순위 큐 연상 구현 class PriorityQueue: # 양방향 연결리스트를 이용하여 초기화 def __init__(self, x): self.queue = DoublyLinkedList() # 크기 def size(self): return self.queue.getLength() # 비어있는지 def isEmpty(self): .. 2020. 9. 10.
[Python 자료구조] 환형 큐(Circular Queue) #환형 큐 - '정해진' 개수의 저장 공간을 빙 돌려가며 이용 - 큐가 가득 차면 더이상 원소를 넣을 수 없음 #연산의 정의 size() : 현재 큐에 들어 있는 데이터 원소의 수를 구함 isEmpty() : 현재 큐가 비어 있는지를 판단 isFull() : 큐에 데이터 원소가 꼭 차 있는지를 판단 qneueue(x) : 데이터 원소 x를 큐에 추가 dequeue() : 큐의 맨 앞에 저장된 데이터 원소를 제거(또한, 반환) peek() : 큐의 맨 앞에 저장된 데이터 원소를 반환(제거하지 않음) #배열로 구현한 환형 큐 class CircularQueue: #큐 초기화 def __init__(self, n): self.maxCount = n self.data = [None] * n self.count .. 2020. 9. 10.
[Python 자료구조] 큐 (Queues) #연산의 정의 size() : 현재 큐에 들어있는 데이터 원소의 수를 구함 isEmpty() : 현재 큐가 비어 있는지를 판단 enqueue(x) : 데이터 원소 x를 큐에 추가 dequeue() : 큐의 맨 앞에 저장된 데이터 원소를 제거(또는 반환) peek() : 큐의 맨 앞에 저장된 데이터 원소를 반환(제거하지 않음) #배열을 이용하여 구현 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): r.. 2020. 9. 10.
[Python 자료구조] 스택(Stacks) #연산의 정의 size(): 현재 스택에 들어 있는 데이터 원소의 수를 구함 isEmpty(): 현재 스택이 비어 있는지를 판단 (size() == 0?) push(x): 데이터 원소 x 를 스택에 추가 pop(): 스택에 가장 나중에 저장된 데이터 원소를 제거 (또한, 반환) peek(): 스택에 가장 나중에 저장된 데이터 원소를 참조 (반환), 그러나 제거하지는 않음 #배열로 구현한 스택 class ArrayStack: def __init__(self): self.data = [] def size(self): #크기 리턴 return len(self.data) def isEmpty(self): return self.size() == 0 def push(self, item): self.data.appe.. 2020. 9. 10.
[Python 자료구조] 양뱡향 연결 리스트(Doubly Linked Lists) #Node의 구조 확장 # class Node: def __init__(self, item): self.data = item self.prev = None self.next = None #Dummy node class DoublyLinkedList: def __init__(self): self.nodeCount = 0 self.head = Node(None) self.tail = Node(None) self.head.prev = None self.head.next = self.tail self.tail.prev = self.head self.tail.next = None #리스트 순회 def traverse(self): result = [] curr = self.head while curr.next.ne.. 2020. 9. 10.
[Python 기초] 선형 배열(Linear Array) #Python 리스트에 활용할 수 있는 연산들 (1) 리스트 길이과 관계 없이 빠르게 실행 결과를 보게되는 연산들 원소 덧붙이기 .append() 원소 하나를 꺼내기 .pop() (2) 리스트의 길이에 비례해서 실행 시간이 걸리는 연산들 원소 삽입하기 .insert() 원소 삭제하기 .del() #리스트에서 원소 찾아내기 Example 1: Input: L = [64, 72, 83, 72, 54] x = 72 Output: [1, 3] Example 2: Input: L = [64, 72, 83, 72, 54] x = 83 Output: [2] Example 3: Input: L = [64, 72, 83, 72, 54] x = 49 Output: [-1] Solution 1: def solution(L,.. 2020. 9. 9.

티스토리툴바