목록큐 (14)
넘치게 채우기
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/A89wq/btr900j6f8e/rCyX7aatQc2W3Y8tMuvwS0/img.jpg)
힙 힙(Heap)은 다음과 같은 특성을 가지고 있다: 1. 완전 이진 트리이다. 2. (부모 노드의 index) = (자식 노드의 index) // 2 3. (왼쪽 자식의 index) = (부모 노드의 index) * 2 4. (오른쪽 자식의 index) = (부모 노드의 index) *2 +1 5. 루트의 index는 1이다. (구현의 편의상 1부터 시작한다.) 힙은 이러한 특성때문에 보통 배열로 많이 구현한다. 힙의 삽입과 삭제는 O(log N)이 걸리고, 탐색에는 O(N)이 걸린다. 힙은 두 가지의 종류가 있다. 최대 힙과 최소 힙이다. 최대 힙(max heap)은 부모 노드의 key값이 자식 노드의 key 값보다 큰 힙이고, 최소 힙(min heap)은 부모 노드의 key값이 자식 노드의 key ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bopI4q/btrPGP8oxFU/7oNdPw2c4wqGtnJg3W5A5K/img.png)
덱 덱(deque)는 double - ended - queue의 줄임말로, 앞뒤로 빼고, 넣는 것이 가능한 자료구조이다. 큐와 스택을 합친 자료구조라고 볼 수도 있다. 파이썬에서는 collections 라는 모듈에서 쉽게 사용할 수 있다. 리스트와 비슷해보이는 연산들이 있지만, 들여다보면 차이가 존재한다. 리스트는 맨 앞 데이터를 빼면, 뒤에 있는 데이터들이 다 앞으로 당겨져서 시간복잡도가 O(n)이 된다. 덱은 이중 연결리스트 기반으로 구현되어, 맨 앞 데이터를 빼더라도 시간복잡도가 O(1)이다. 덱의 연산 appendleft(): 앞쪽으로 데이터 enqueue popleft(): 앞쪽에서 데이터 dequeue append(data): 뒤쪽으로 데이터 enqueue pop(): 뒤쪽에서 데이터 dequ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/cQgtwy/btrPvjIMtws/iTofYuzsllQfmR1c8sWCyk/img.png)
지난 2-2 글에서, 내가 구현한 배열을 이용한 큐는, 엄밀히 따지면 파이썬의 리스트를 이용한 것이다. '배열'이랑 구현한 것과 다른 점은, 큐의 크기를 정하지 않는다.(append하면 뒤에 새 칸을 만들고, pop하면, 칸이 줄어든다) pop 했을 때, 뒤 데이터들이 빈 자리를 채우러 앞으로 당겨진다. 그래서, '배열스러운' 큐를 다시 구현해보았다. 큐 - '배열'을 이용한 구현(Python) class queue(): #큐 선언 def __init__(self, size): self.size = size self.arr = [None] * self.size self.first = 0 self.last = 0 def isEmpty(self): #큐가 비어있는지 확인 if self.first >= sel..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bSq7eW/btrOyhS0rSK/8NsDj1rj4j22eXyPXjsSkk/img.png)
큐(Queue) 큐 자료구조는 우리가 평소에 줄을 서듯, 먼저 들어온 사람이 먼저 나가는, 선입선출(先入先出, First in First out)의 형식을 따른다. 큐의 연산 큐의 연산은 다음 5가지가 있다: isEmpty(): 큐가 비어있는지를 판단한다. True 또는 False값으로 반환된다. enqueue(data): 큐에 값을 입력시킨다. dequeue(): 큐의 제일 먼저온 값을 내보낸다. rear(): 큐의 맨 뒤에 있는 값을 반환한다. front(): 큐의 제일 반저온 값을 반환한다(큐에서 pop하지는 않는다) 큐의 구현 - 배열을 이용한 구현(Python) class queue(): #큐 선언 def __init__(self): self.arr = [] def isEmpty(self): #..