[TIL] 자료구조/알고리즘 풀기 (3)

이원진·2023년 4월 12일
TIL데브코스알고리즘
0

데브코스

목록 보기
3/54
post-thumbnail

학습 주제

  1. 큐(Queue)

  2. 환형 큐(Circular Queue)

  3. 우선순위 큐(Priority Queue)

  4. 트리(Tree)

  5. 이진 트리(Binary Tree)

  6. 이진 트리 - 넓이 우선 순회(Breadth First Traversal)

  7. 이진 탐색 트리(Binary Search Tree)

  8. 힙(Heap)

1. 큐(Queue)

  • 선입선출(FIFO)의 특징을 갖는 선형 자료구조

  • 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 일어나는 경우 활용

  • 추상자료형
    - size(): 현재 큐의 데이터 원소 수 계산

    - isEmpty(): 현재 큐가 비어있는지를 판단
- enqueue(x): 데이터 원소 x를 큐에 추가
- dequeue(): 큐의 최전방 데이터 원소를 추출
- peek(): 큐의 최전방 데이터 원소를 반환

  • 구현

    1. 배열로 구현

        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):
			return self.data[0]
      • dequeue() 연산의 시간복잡도가 O(N)

    2. 양방향 연결 리스트로 구현

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

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

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

	    def enqueue(self, item):
  			node = Node(item)
  			self.data.insertAt(self.size() + 1, node)

		def dequeue(self):
  			return self.data.popAt(1)

	    def peek(self):
  			return self.data.getAt(1).data

2. 환형 큐(Circular Queue)

  • 정해진 개수의 저장 공간을 돌면서 이용하는 큐

  • 추상자료형

    • size(): 현재 큐의 데이터 원소 수 계산

    • isEmpty(): 현재 큐가 비어있는지를 판단

    • isFull(): 현재 큐가 가득 차있는지를 판단

    • enqueue(x): 데이터 원소 x를 큐에 추가

    • dequeue(): 큐의 최전방 데이터 원소를 추출

    • 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 is full')

          self.rear = 0 if self.rear == self.maxCount - 1 else self.rear + 1
          self.data[self.rear] = x
          self.count += 1

      def dequeue(self):
          if self.isEmpty():
              raise IndexError('Queue is empty')

          self.front = 0 if self.front == self.maxCount - 1 else self.front + 1
          x = self.data[self.front]
          self.count -= 1
          return x

      def peek(self):
          if self.isEmpty():
              raise IndexError('Queue is empty')

          return self.data[0 if self.front == self.maxCount + 1 else self.front + 1]

3. 우선순위 큐(Priority Queue)

  • FIFO 방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 큐

  • 운영체제의 CPU 스케줄링에 활용

  • 구현

    • enqueue()할 때 우선순위 순서를 유지하도록 하는 것이 조금 더 유리
      • dequeue()할 때 우선순위를 고려하면, 다른 모든 항목을 탐색해야 함

    • 양방향 연결 리스트로 구현하는 것이 배열로 구현하는 것보다 빠름


4. 트리(Tree)

  • 노드와 간선(Edge)을 이용하여 데이터의 배치 형태를 추상화한 계층형 자료구조

  • 구조

    • 루트 노드(Root): 트리의 최상위 노드
    • 단말 노드(Leaf): 자식이 없는 노드
    • 부모 노드(Parent)
    • 자식 노드(Child)
    • 형제 노드(Siblings) : 같은 부모를 갖는 노드
    • 서브 트리(Subtree) : 자신과 모든 자손으로 이루어진 트리
    • 간선(Edge) : 노드 간 연결선
    • 레벨(Level)
    • 깊이(Depth)
    • 차수(Degree): 자식(서브트리)의 수

5. 이진 트리(Binary Tree)

  • 모든 노드의 차수가 2 이하인 트리

  • 재귀적으로 정의 가능

    • 루트 노드 + 왼쪽 서브트리 + 오른쪽 서브트리

  • 완전(Complete) 이진 트리

    • 마지막 레벨을 제외하고 모든 레벨이 노드로 완전히 채워져있는 트리

    • 마지막 레벨은 왼쪽부터 채워진 트리

    • 배열을 사용해 효율적으로 표현 가능


  • 전(Full) 이진 트리

    • 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리


  • 포화(Perfect) 이진 트리

    • 전 이진 트리이면서 완전 이진 트리인 경우

    • 말단을 제외한 모든 노드가 2개의 자식을 가짐

    • 모든 말단 노드가 동일한 레벨을 가짐

    • 노드의 개수가 항상 2^(k - 1)개
      - k: 트리의 높이


  • 균형(Balanced) 이진 트리

    • 모든 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차가 1 이하인 트리


  • 추상자료형

    • size(): 현재 트리에 포함되어 있는 노드의 수를 계산

    • depth(): 현재 트리의 깊이(= 높이)를 계산

    • 순회(Traversal)

      • 깊이 우선 순회(Depth First Traversal)
        • 중위 순회(In-order)
          • 왼쪽 자식 노드 → 현재 노드 → 오른쪽 자식 노드
        • 전위 순회(Pre-order)
          • 현재 노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드
        • 후위 순회(Post-order)
          • 왼쪽 자식 노드 → 오른쪽 자식 노드 → 현재 노드

    • 넓이 우선 순회(Breadth Fist Traversal)

  • 구현

    class Node:
      def __init__(self, item):
          self.data = item
          self.left = None
          elf.right = None

      def size(self):
          l = self.left.size() if self.left else 0
          r = self.right.size() if self.right else 0

          return l + r + 1

      def depth(self):
          l = self.left.depth() if self.left else 0
          r = self.right.depth() if self.right else 0

          return max(l, r) + 1

      # preorder, postorder도 inorder와 거의 똑같고 순서만 다름
      def inorder(self):
          traversal = []

         if self.left:
             traversal += self.left.inorder()

         traversal.append(self.data)

         if self.right:
             traversal += self.right.inorder()

         return traversal
    class BinaryTree:
      def __init__(self, node):
          self.root = node
          
      def size(self):
          # 빈 트리가 아닌 경우
          if self.root:
              return self.root.size
              
          else:
              return 0

      def depth(self):
          if self.root:
              return self.root.depth()
      
          else:
              return 0

      def inorder(self):
          if self.root:
              return self.root.inorder()
              
          else:
              return []

6. 이진 트리 - 넓이 우선 순회(Breadth First Traversal)

  • 레벨이 낮은 노드를 우선으로 방문

  • 같은 레벨일 경우 부모 노드의 순서에 따라, 같은 부모일 경우 왼쪽부터 방문

    • 한 노드를 방문했을 때, 다음에 방문할 노드들을 큐에 순서대로 기록해야 함

  • 재귀 적합 X

  • 구현

    def bft(self):
    if not self.root:
        return []

    queue = ArrayQueue()
    queue.enqueue(self.root)

    traversal = []

    while not queue.isEmpty():
        popped = queue.dequeue()
        traversal.append(popped.data)

        if popped.left:
            queue.enqueue(popped.left)

        if popped.right:
            queue.enqueue(popped.right)

    return traversal

7. 이진 탐색 트리(Binary Search Tree)

  • 모든 노드에 대해, 왼쪽 서브트리의 데이터는 모두 현재 노드의 값보다 작고, 오른쪽 서브트리의 데이터는 모두 현재 노드의 값보다 큰 이진 트리

  • 이진 탐색에 비해 데이터 원소 추가, 삭제 용이

    • But, 공간 소요 큼

  • 노드의 값이 연속적일 경우, 한쪽으로만 치우치기 때문에 효율적이지 못함
    -> AVL tree와 같이 높이의 균형을 유지하도록 구현하면, 탐색 효율성 보장 가능

  • 추상자료형

    • insert(key, data): 트리에 주어진 데이터 원소 추가

    • remove(key): 트리에서 특정 원소 삭제

      • 자식의 개수에 따라 해야 할 연산이 다름

    • lookup(key): 트리에서 특정 원소 검색

    • inorder(): 키의 순서대로 데이터 원소 정렬

    • min(), max(): 최소 키, 최대 키를 갖는 원소 각각 탐색

  • 구현

    class Node:
       def __init__(self, key, data):
           self.key = key
           self.data = data
           self.left = None
           self.right = None

        def inorder(self):
           traversal = []

           if self.left:
               traversal += self.left.inorder()

           traversal.append(self)

           if self.right:
               traversal += self.right.inorder()

           return traversal

        def min(self):
            if self.left:
                return self.left.min()

            else:
                return self

        def max(self):
            if self.right:
                return self.right.max()

            else:
                return self

        # parent의 default는 None
        # remove() 연산에서 parent 요구
        def lookup(self, key, parent = None):
            if key < self.key:
                if self.left:
                    # 왼쪽 자식 노드의 부모는 현재 노드
                    return self.left.lookup(key, self)

                else:
                    return None, None

            elif key > self.key:
                if self.right:
                    return self.right.loopup(key, self)

                else:
                    return None, None

            else:
                return self, parent

        def insert(self, key, data):
            if key < self.key:

                # 왼쪽 자식이 없는 경우, 삽입
                if self.left is None:
                    self.left = Node(key, data)

                # 있는 경우, 왼쪽 자식으로 insert() 메서드 재귀 호출
                else:
                    self.left.insert(key, data)

            elif key > self.key:
                if self.right is None:
                    self.right = Node(key, data)

                else:
                    self.right.insert(key, data)

            # 인자로 받은 key값과 현재 노드의 key값이 같다면, KeyError 발생
            else:
                raise KeyError

        def countChildren(self):
            count = 0

            if self.left:
                count += 1

            if self.right:
                count += 1

            return count
    class BinarySearchTree:
		def __init__(self):
		    self.root = None

		def inorder(self):
		    if self.root:
			    return self.root.inorder()

			else:
				return []

		def min(self):
		    if self.root:
			    return self.root.min()

			else:
				return None

		def max(self):
		    if self.root:
			    return self.root.max()

			else:
				return None

		def lookup(self, key):
		    if self.root:
			    return self.root.lookup(key)

			else:
				return None, None

		def insert(self, key, data):
		    if self.root:
			    self.root.insert(key, data)

			else:
			    self.root = Node(key, data)

8. 힙(Heap)

  • 완전 이진 트리의 한 종류

    • 노드의 추가/삭제는 마지막 노드에서만 수행

    • 배열로 구현하기 용이

  • 루트 노드가 최댓값(Max Heap) or 최솟값(Min Heap)

  • 재귀적으로 정의 가능

  • 이진 탐색 트리와는 다르게 크기 순으로 정렬되어 있지 않기 때문에, 탐색이 빠르지 않음

  • 삽입/삭제 연산의 시간복잡도는 O(log N)

  • 추상자료형

    • init(): 빈 최대 힙 생성

    • insert(item): 새로운 원소 삽입

    • remove(): 최댓값 갖는 원소 추출

  • 구현

    • 노드 번호가 m일 경우, 왼쪽 자식의 번호는 2m, 오른쪽 자식의 번호는 2m + 1

    • 부모 노드의 번호는 m // 2

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

    def insert(self, item):
        self.data.append(item)
        index = len(self.data) - 1

        while index > 1:
            curr_index = index
            curr = self.data[index]

            index = index // 2
            parent = self.data[index]

            if parent < curr:
                self.data[curr_index], self.data[index] = self.data[index], self.data[curr_index]

            else:
                break

    def remove(self):
        if len(self.data) > 1:
            self.data[1], self.data[-1] = self.data[-1], self.data[1]
            data = self.data.pop(-1)
            self.maxHeapify(1)

        else:
            data = None

        return data

    def maxHeapify(self, i):
        left = 2 * i
        right = (2 * i) + 1
        smallest = i

        # 왼쪽 자식이 존재하고, 왼쪽 자식의 값이 현재 노드의 값보다 큰 경우
        if left < len(self.data) and self.data[smallest] < self.data[left]:

            # smallest 는 왼쪽 자식의 인덱스
            smallest = left

        if right < len(self.data) and self.data[smallest] < self.data[right]:
            smallest = right

        if smallest != i:
            self.data[i], self.data[smallest] = self.data[smallest], self.data[i]
            self.maxHeapify(smallest)

  • 응용

    1. 우선순위 큐

    2. 힙 정렬(Heap Sort)

      • 시간복잡도가 O(N * log N)

메모

  • 환형 큐 구현 실습
    • dequeue()할 때 list.pop()이 아니라, 인덱스로 접근해 값을 가져와야 함
      • pop()은 항목의 값이 아닌 항목 자체를 추출하기 때문에 리스트의 길이 감소
profile
이원진
이전 포스트

[TIL] 자료구조/알고리즘 풀기 (2)

다음 포스트

[TIL] 자료구조/알고리즘 풀기 (4)

0개의 댓글