📖 오늘의 학습

• 자료구조 : 큐, 트리, 힙

---

큐

1. 큐 (Queue)

• 자료를 보관할 수 있는 선형 구조
• 단, 넣을 때에는 한쪽 끝에서 밀어넣어야(enqueue) 하고 꺼낼 때에는 반대쪽에서 뽑아(dequeue) 꺼내야함
• 선입선출 FIFO 특징을 가지는 선형 자료구조
  • 공장에서 먼저 들어온 부품을 사용
  • 일상생활에서의 줄서기
• 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 일어나는 경우
• 자료를 생성하는 작업이 여러 곳에서 일어나는 경우
• 자료를 이용하는 작업이 여러 곳에서 일어나는 경우
• 자료를 처리하여 새로운 자료를 생성하고, 나중에 그 자료를 또 처리해야 하는 작업의 경우

큐의 추상적 자료구조 구현

1. 배열을 이용하여 구현
2. 연결리스트를 이용하여 구현

연산의 정의

1. size : 현재 큐에 들어 있는 데이터 원소의 수를 구함
2. isEmpty : 현재 큐가 비어 있는지를 판단
3. enqueue : 데이터 원소 x를 큐에 추가
4. dequeue : 큐의 맨 앞에 저장된 데이터 원소를 제거, 반환
5. peek : 큐의 맨 앞에 저장된 데이터 원소를 반환 (제거하지 않음)

코드구현

class ArrayStack:
	def __init__(self):
		self.data = []

	def size(self):
		return len(self.data)

	def isEmpty(self):
		return len(self.data) == 0

	def enqueue(self, item):
		self.data.append(item)
	
	def dequeue(self):
		return self.data.pop(0)

	def peek():
		return self.data[0]

이렇게 배열을 이용해서 구현하면 구현은 아주 편리하지만 dequeue를 할 때 선형탐색을 해야한다는 단점이 있음
양방향 연결리스트로 이를 보완한다.

양방향 연결리스트로 큐를 구현 ( DoublyLinkedList 는 이전 TIL 참고)

class LinkedListQueue:

    def __init__(self):
        self.data = DoublyLinkedList()

    def size(self):
        return self.data.getLength()

    def isEmpty(self):
        return self.data.getLength() == 0
    
    def enqueue(self, item):
        node = Node(item)
        self.data.insertAt(self.data.nodeCount + 1, node)
       
    def dequeue(self):
        return self.data.popAt(1)
     
    def peek(self):
        return self.data.getAt(1).data

2. 환형 큐 (Circular Queue)

• 정해진 갯수의 저장 공간을 빙 돌려가면서 이용
  • 데이터를 넣는 포인트를 rear
  • 데이터를 꺼내는 포인트를 front로 설정하고 이를 기억하면서 데이터를 삽입, 삭제한다.
• 큐의 길이를 제한하고 있기 때문에 큐가 가득 차면 더이상 원소를 삽입할 수 없다. (큐의 길이를 기억하고 있어야 함)
• front와 rear를 적절히 계산하여 환형으로 재활용

연산의 정의

1. size : 현재 큐에 들어 있는 데이터 원소의 수를 구함
2. isEmpty : 현재 큐가 비어 있는지를 판단
3. isFull : 큐에 데이터 원소가 꽉 차 있는지 판단 --> (추가)
4. enqueue : 데이터 원소 x를 큐에 추가
5. dequeue : 큐의 맨 앞에 저장된 데이터 원소를 제거, 반환
6. peek : 큐의 맨 앞에 저장된 데이터 원소를 반환 (제거하지 않음)

코드구현

class CircularQueue:

    def __init__(self, n):
        self.maxCount = n
        self.data = [None] * n
        self.count = 0
        self.front = -1
        self.rear = -1

    def size(self):
        return self.count

    def isEmpty(self):
        return self.count == 0

    def isFull(self):
        return self.count == self.maxCount

    def enqueue(self, x):
        if self.isFull():
            raise IndexError('Queue full')
        self.rear = (self.rear + 1) % self.maxCount
        self.data[self.rear] = x
        self.count += 1

    def dequeue(self):
        if self.isEmpty():
            raise IndexError('Queue empty')
        self.front = (self.front + 1) % self.maxCount
        x = self.data[self.front]
        self.count -= 1
        return x

    def peek(self):
        if self.isEmpty():
            raise IndexError('Queue empty')
        return self.data[(self.front + 1) % self.maxCount]

🚨 주의할 점 : front 위치에 있는 원소는 비활성화 된 상태이기 때문에 peek()할 때 front + 1을 해야 활성화 된 원소를 꺼낼 수 있다.

3. 우선순위 큐 (Priority Queue)

• 원소에 우선순위를 부여하고 우선순위가 높은 순서대로 꺼내는 큐
• 대표적인 예로 운영체제에서 CPU 스케줄러를 구현할 때, 실행할 수 있는 작업들 중 가장 우선순위가 높은 것을 골라 실행하는 알고리즘
• 큐에 원소를 넣을 때 우선순위 순서대로 정렬한다.
  • 이 방식이 유리한 이유는 넣을 때 우선순위를 찾게 되면 모든 원소를 탐색할 필요가 없으니 꺼낼 때 찾게 되면 모든 원소를 탐색하여 우선순위를 비교해야 하기 때문이다.
• 양방향 연결리스트를 이용
  • 우선순위에 따라 원소를 삽입하기 때문에 중간에 원소를 삽입하기 효율적인 양방향 연결리스트가 적합

코드 구현

class PriorityQueue:

    def __init__(self):
        self.queue = DoublyLinkedList()

    def size(self):
        return self.queue.getLength()

    def isEmpty(self):
        return self.size() == 0

    def enqueue(self, x):
        newNode = Node(x)
        curr = self.queue.head.next
        while curr.next is not None and curr.next.data <= x:
            curr = curr.next
        self.queue.insertAfter(curr, newNode)

    def dequeue(self):
        return self.queue.popAt(self.queue.getLength())

    def peek(self):
        return self.queue.getAt(self.queue.getLength()).data

트리

1. 트리 (Trees)

• 2차원의 자료구조
• 정점과 간선, 노드와 엣지를 이용해서 데이터의 배치형태를 추상화함
• 루트 - 내부 - 리프 노드
• 부모 노드와 자식 노드의 관계를 가짐

트리의 용어

• 노드 (nodes)
• 간선 (edges)
• 루트 노드 (root node), 리프 노드 (leaf nodes), 내부 노드 (internal nodes)
• 부모의 부모 - 조상 (ancestor)
• 자식의 자식 - 후손 (descendant)
• 노드의 수준 (level) root는 0
• 노드의 차수 (degree) = 자식(서브트리)의 수, 만약 자식이 없다면 degree가 0임
• 트리의 높이 (height) - 또는, 깊이 (depth) - 최대수준level + 1
• 부분 트리 (서브트리; subtrees)
• 이진 트리 (binary trees) - 모든 노드의 차수가 2 이하인 트리
• 포화 이진 트리 (full binary trees) - 모든 레벨에서 노드들이 모두 채워져 있는 이진 트리
• 완전 이진 트리 (complete binary trees) - 레벨 k-2까지는 모든 노드가 2개의 자식을 가진 포화트리이고 레벨 k-1에서는 왼쪽부터 노드가 순차적으로 채워져 있는 이진 트리

2. 이진트리 (Binary Trees)

• 트리에 포함되는 모든 노드의 차수가 2이하인 트리
• 즉, 모든 노드는 자식이 없거나, 하나만 있거나, 둘이 있거나의 셋 중 하나다.
• 연산이 대부분 재귀적으로 구현 가능

연산의 정의

• 노드의 수 구하기
• 트리의 깊이(또는 높이) 구하기
• 순회 (traversal)

이진 트리의 넓이 우선 순회

• 중위 순회하는 것처럼 재귀적으로는 불가능
• 나중에 다시 방문하기로 하고 그 순서를 기억해두자 => 큐를 이용
• 노드가 자식이 있다면 큐에 삽입, 처리가 끝나면 빼낸다. 꺼낼 때 해당 노드의 자식이 있다면 큐에 삽입
• 절차
  1. 빈 리스트, 큐
  2. 빈 트리가 아니면 root node를 큐에 추가
  3. 큐가 비어있지 않은 동안
     1. 큐에서 원소를 추출
     2. 추출된 원소를 리스트에 붙임
     3. 원소의 왼,오른쪽 자식이 있다면 큐에 추가
  4. 빈 큐가 되면 노드 방문 완료

3. 이진 탐색 트리 (Binary Search Trees)

• 모든 노드에 대해서 왼쪽 서브트리에 있는 데이터는 모두 현재 노드 값보다 작고 오른쪽 서브트리에 있는 데이터는 모두 현재 노드 값보다 큰 성질을 만족하는 이진트리
• 중복되는 원소는 없는 것으로 가정 = 같은 값이 없다
  정렬된 배열을 이용한 이진 탐색과 비교
• 장점: 데이터 원소의 추가, 삭제가 용이
• 공간 소요가 큼
• 탐색 복잡도는? O(log n) 인가?
• node가 key, value쌍으로 되어있음

연산의 정의

• insert : 트리에 주어진 데이터 원소를 추가
• remove : 특정 원소를 트리로부터 삭제 -> 조금 복잡함
• lookup : 특정 원소를 검색
• inorder : 키의 순서대로 데이터 원소를 나열
• min, max : 최소 키, 최대 키를 가지는 원소를 각각 탐색

힙

• 루트노드가 항상 최댓값을 가진다.
• 완전 이진트리이다.
• 최대 입 내의 임의의 노드를 루트로 하는 서브트리 또한 최대 힙이다.

이진트리와 비교

1. 원소들은 크기 순으로 정렬되어 있지 않음
2. 특정 키 값을 가지는 원소를 빠르게 검색할 수 없다.
3. 부가의 제약 조건은 어떤것인가? 완전이진트리여야한다.

배열을 이용한 이진트리 표현

노드 번호 m을 기준으로

• 왼쪽 자식의 번호 : 2 * m
• 오른쪽 자식의 번호 : 2 * m + 1
• 부모 노드의 번호 : m // 2
  완전 이진 트리이므로 노드의 추가/삭제는 마지막 노드에서만 이루어진다.

최대 힙에 원소 삽입

1. 트리의 마지막 자리에 새로운 원소를 임시로 저장
2. 부모 노드와 키 값을 비교하여 새로운 원소가 작을때까지 위로 서로 위치를 바꾸면서(swap) 이동

• 복잡도
  • 원소의 개수가 n인 최대 힙에 새로운 원소 삽입 - 부모노드와의 대소 비교 최대 횟수 : log2n

최대 힙에서 원소의 삭제

1. 루트 노드의 제거 - 이것이 원소들 중 최댓값으로 이 값을 리턴한다
2. 트리 마지막 자리 노드를 임시로 루트 노드의 자리에 배치
3. 자식 노드들과의 값 비교와 아래로 이동 - 자식노드들보다 클때까지, 왼쪽 오른쪽 중 더 큰 값을 가지는 쪽으로

• 복잡도
  • 원소의 개수가 n인 최대 힙에서 최대 원소 삭제
  • 자식 노드들과의 대소 비교 최대 횟수 : 2 * log2n

---

📝 주요메모사항

---

😵 공부하면서 어려웠던 내용