본문 바로가기

Python81

[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.
[Python 자료구조] 연결리스트 (Linked List) #자료 구조 정의 #노드 class Node: def __init__(self.item): self.data = item self.next = None #비어있는 연결리스트 class LinkedList: def __init(self) self.nodeCount = 0 self.head = None self.tail = None #연산 정의 (1) 특정 원소 참조 (k번째) #K번째 노드 찾기 #[1][67] -> [2][34] -> [3][58] # 노드의 개수: 3 #Head: 67 #Tail: 58 def getAt(self, pos): if pos self.nodeCount: #pos 번째에 있는 노드를 반환하는 것이 목표 retrun None #pos가 0보다 작거나 노드 개수보다 작으면 없다... 2020. 9. 9.
LeetCode 155. Min Stack - Python 155. Min Stack Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element. getMin() -- Retrieve the minimum element in the stack. Constraints: Methods pop, top and getMin operations will always be called on non-empty stacks. Example: Input [".. 2020. 9. 9.
LeetCode 53. Maximum Subarray - Python LeetCode 53. Maximum Subarray - Python Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle. Example 1: Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: [4,-1,2.. 2020. 9. 7.
[Algorithm] 동적계획법(Dynamic programming) - Brute Force, Kadane’s Algorithm #동적계획법(Dynamic programming) - 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 (wikipedia) - Bottom-Up 적 방법 #동적계획법 예제 - nm선 자르기 #nm의 선을 1m나 2m 자르는 방법의 수 #1m 선의 경우 #[1,1,1] => 1가지 #dy[1]=1 #2m 선의 경우 #[1,1,1],[2] => 2가지 #dy[2]=2 #3m 선의 경우 #[1,1,1] => 1가지 #[1,1,1],[2] => 2가지 #1가지(1m선의 경우) + 2가지(2m선의 경우) = 3가지 #dy[3]=3 #4m 선의 경우 #2가지(2m선의 경우) + 3가지(3m선의 경우) = 5가지 #dy[4]=5 n = int(input()) dy=[0]*(n+1) #배열을 만듦 dy[1]=.. 2020. 9. 6.

티스토리툴바