AI교육과정 - Python.7

힙(Heap)

• 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)
• 완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리

1. 힙(Heap)을 사용하는 이유
   • 배열에 데이터를 넣고 최대값, 최소값을 찾으려면 시간이 많이 걸릴 수 있음
   • 힙에 데이터를 넣고 최대값, 최소값을 찾으면 시간이 적게 소모됨
   • 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨
2. 힙(Heap)의 구조
   • 힙은 최대값을 구하기 위한 구조(최대 힙, Max Heap)와 최소값을 구분하기 위한 구조(최소 힙, Min Heap)로 분류할 수 있음
   • 힙은 아래와 같이 두가지 조건을 가지고 있는 자료 구조
     1. 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다(최대 힙인 경우)
     2. 완전 이진 트리 형태를 가짐
3. 힙과 이진 탐색 트리의 공통점과 차이점
   • 공통점
     • 힙과 이진 탐색 트리는 모두 이진 트리임
   • 차이점
     • 힙은 각 노드의 값이 자식 노드보다 크거나 같음
     • 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그 다음 부모 노드, 그 다음 오른쪽 자식 노드값이 큼
     • 힙은 이진 탐색 트리의 조건인 자식 노드에서 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건이 없음
4. 힙(Heap)의 동작
   1. 힙에 데이터 삽입하기
      • 힙은 완전 이진트리이므로 삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워지는 형태로 삽입
      • 채워진 노드 위치에서 부모 노드보다 값이 클 경우, 부모 노드와 위치를 바꾸는(swap) 작업을 반복함
   2. 힙 데이터 삭제하기
      • 최상단 노드를 삭제하는 것이 일반적
      • 힙의 용도는 최대값 또는 최소값을 root 노드에 놓아서 최대값 또는 최소값을 바로 꺼낼 수 있도록 하는 것
      • 상단의 데이터 삭제 시 가장 최하단부 왼쪽에 위치하는 노드(일반적으로 가장 마지막(왼쪽)에 추가한 노드)를 root 노드로 이동
      • root 노드의 값이 child node보다 작을 경우, root노드의 child node 중 가장 큰 값을 가진 노드와 root 노드 위치를 바꿔주는 작업을 반복
5. 힙 구현 하기
   • 힙 구현 시 배열 자료구조를 활용
   • 배열은 인덱스가 0번부터 시작하지만 힙 구현의 편의를 위해 root 노드 인덱스 번호를 1로 지정하면 구현이 좀 더 수월함
     • 부모 노드 인덱스 번호 = 자식 노드 인덱스 번호 // 2 (//: 몫을 구함)
     • 왼쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2
     • 오른쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2 + 1

힙 클래스 구현하기

class Heap:
  def __init__(self, data):
    self.heap_array = list()
    self.heap_array.append(None) # 0번째 인덱스에 None 삽입
    self.heap_array.append(data) # 1번째 인덱스에 data 삽입

1. 삽입 구현하기

   • 삽입한 노드가 부모 노드의 값보다 클 경우, 부모 노드와 삽입한 노드 위치를 바꿈
   • 삽입한 노드가 루트 노드가 되거나, 부모 노드보다 값이 작을 경우까지 계속 반복

   def move_up(self, inserted_idx):
       if inserted_idx <= 1: # 삽입한 데이터의 인덱스값이 1보다 같거나 작을 경우 = root node
           return False
       parent_idx = inserted_idx // 2 # 삽입한 데이터의 부모 인덱스값
       if self.heap_array[inserted_idx] > self.heap_array[parent_idx]:
   		# 삽입한 데이터가 부모 데이터보다 값이 클 경우
           return True
       else:
           return False
   def insert(self, data):
       if len(self.heap_array) == 0: # array에 삽입된 데이터가 없을 경우
           self.heap_array.append(None)
           self.heap_array.append(data)
           return True
       self.heap_array.append(data)
       inserted_idx = len(self.heap_array) - 1 # 현재 삽입한 데이터의 인덱스 값
       while self.move_up(inserted_idx): # 삽입한 데이터가 부모 데이터보다 값이 클 경우
           parent_idx = inserted_idx // 2
   				# 삽입한 데이터와 부모 데이터 변경
           self.heap_array[inserted_idx], self.heap_array[parent_idx] = self.heap_array[parent_idx], self.heap_array[inserted_idx]
           # 삽입한 데이터의 인덱스를 부모 인덱스로 지정
   				inserted_idx = parent_idx
   	  return True

2. 삭제 구현하기

   • 최상단(root node) 노드를 삭제하는 것이 일반적
   • 상단의 데이터 삭제 시 가장 최하단부에 위치한 노드(일반적으로 가장 마지막에 추가한 노드)를 root 노드로 이동
   • root 노드의 값이 child node보다 작을 경우, root 노드의 child node 중 가장 큰 값을 가진 노드와 root 노드 위치를 바꿔주는 작업을 반복

   def move_down(self, poped_idx):
       left_child_poped_idx = poped_idx * 2 # 삭제한 데이터의 왼쪽 자식노드
       right_child_poped_idx = poped_idx * 2 + 1 # 삭제한 데이터의 오른쪽 자식노드
       # 자식 노드가 없을 때
       if left_child_poped_idx >= len(self.heap_array):
           return False
       # 왼쪽 자식 노드만 있을 때
       elif right_child_poped_idx >= len(self.heap_array):
   				# 삭제할 노드보다 왼쪽 자식 노드가 더 클 경우
           if self.heap_array[poped_idx] < self.heap_array[left_child_poped_idx]:
               return True
           else:
               return False
       # 왼쪽 오른쪽 자식 노드가 모두 있을 때
       else:
   				# 왼쪽 자식노드가 오른쪽 자식노드보다 클 경우
           if self.heap_array[left_child_poped_idx] > self.heap_array[right_child_poped_idx]:
               # 삭제할 데이터가 왼쪽 자식노드보다 작을 경우
   						if self.heap_array[poped_idx] < self.heap_array[left_child_poped_idx]:
                   return True
               else:
                   return False
           else:
   						# 삭제할 데이터가 오른쪽 자식노드보다 작을 경우
               if self.heap_array[poped_idx] < self.heap_array[right_child_poped_idx]:
                   return True
               else:
                   return False
   def pop(self):
       if len(self.heap_array) <= 1: # 현재 리스트의 길이가 1보다 같거나 작을 경우 = 값이 없음
           return None
       returned_data = self.heap_array[1] # 리스트의 root node
       self.heap_array[1] = self.heap_array[-1] # root node 자리에 마지막 데이터 삽입
       del self.heap_array[-1] # 마지막 인덱스 삭제
       poped_idx = 1 # 삭제한 데이터의 인덱스(root node의 idx)
       while self.move_down(poped_idx):
           left_child_poped_idx = poped_idx * 2
           right_child_poped_idx = poped_idx * 2 + 1
           # 왼쪽 자식 노드만 있을 경우
           if right_child_poped_idx >= len(self.heap_array):
   						# 삭제할 데이터가 왼쪽자식노드보다 작을 경우
               if self.heap_array[poped_idx] < self.heap_array[left_child_poped_idx]:
   								# 삭제할 데이터와 왼쪽자식노드 위치 변경
                   self.heap_array[poped_idx], self.heap_array[left_child_poped_idx] = self.heap_array[left_child_poped_idx], self.heap_array[poped_idx]
   		              # 삭제한 데이터의 인덱스값을 왼쪽자식 인덱스값으로 변경
   								poped_idx = left_child_poped_idx
           # 왼쪽 오른쪽 노드 모두 있을 경우
           else:
   						# 왼쪽 자식노드가 오른쪽 자식노드보다 클 경우
               if self.heap_array[left_child_poped_idx] > self.heap_array[right_child_poped_idx]:
   		          # 삭제할 데이터가 왼쪽 자식노드보다 작을 경우
   						  if self.heap_array[poped_idx] < self.heap_array[left_child_poped_idx]:
                    self.heap_array[poped_idx],  self.heap_array[left_child_poped_idx] = self.heap_array[left_child_poped_idx], self.heap_array[poped_idx]
                    poped_idx = left_child_poped_idx
               else:
   							# 삭제할 데이터가 오른쪽 자식노드보다 작을 경우
                 if self.heap_array[poped_idx] < self.heap_array[right_child_poped_idx]:
                     self.heap_array[poped_idx], self.heap_array[right_child_poped_idx] = self.heap_array[right_child_poped_idx], self.heap_array[poped_idx]
                     poped_idx = right_child_poped_idx
       return returned_data

1. 알고리즘 복잡도 계산이 필요한 이유

   하나의 문제를 푸는 알고리즘은 다양함

   • 정수의 절대값을 구하는 방법:
     • 방법1: 값이 음수인지 확인해서 0보다 작은 음수일 때 -1을 곱하기
     • 방법2: 정수값을 제곱한 값에 다시 루트를 씌우기

   다양한 알고리즘 중 어떤 알고리즘이 더 좋은지 분석하기 위해 복잡도를 정의하고 계산함

2. 알고리즘 복잡도 계산 항목

   • 공간 복잡도: 알고리즘이 사용하는 메모리 사이즈
   • 시간 복잡도: 알고리즘 실행 속도

3. 알고리즘 성능 표기법

   • 오메가 표기법
     • 알고리즘 최상의 실행 시간을 표기
   • 세타 표기법
     • 알고리즘 평균 실행 시간을 표기
   • 빅오(Big-O) 표기법
     • 최악의 실행 시간을 표기
     • 아무리 최악의 상황이라도 이 정도의 성능은 보장함을 의미
     • 가장 많이 사용함

4. 빅오 표기법

   • 입력 n에 따라 결정되는 시간 복잡도 함수
   • O(1) < O(𝑙𝑜𝑔𝑛) < O(n) < O(n𝑙𝑜𝑔𝑛) < O(𝑛2) < O(2𝑛) < O(n!)
   • 입력 n에 따라 시간 복잡도가 늘어날 수 있음

   

• 공간 복잡도(Space Complexity): 작성한 프로그램이 얼마나 많은 공간(메모리)을 차지하느냐를 분석하는 방법
• 컴퓨터 성능의 발달로 인해 메모리 공간이 넘쳐나다 보니 중요도가 떨어짐
• 공간 복잡도를 결정하는 것은 배열의 크기가 몇인지, 얼마만큼의 동적 할당인지, 몇 번의 호출을 하는 재귀함수가 있는지가 영향을 끼침
• 알고리즘은 시간 복잡도가 중심

• 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미
• 같은 결과값을 갖는 프로그래밍 소스도 작성 방법에 따라 걸리는 시간이 달라지며 시간이 적게 걸리는 소스가 좋은 소스

1. O(1)

   • 입력 데이터의 크기와 상관없이 언제나 일정한 시간이 걸리는 알고리즘을 나타냄. 데이터가 얼마나 증가하든 성능에 영향을 미치지 않음

   def print_data(data):
       print(data[0])

2. O(𝑙𝑜𝑔𝑛)

   • 입력 데이터의 크기가 커질수록 처리 시간이 로그만큼 짧아지는 알고리즘. 이진 탐색이 대표적이며 재귀가 순기능으로 이루어지는 경우도 해당됨

   def print_data(data):
       i = data
       while i > 1:
           print(i)
           i = i / 2

3. O(n)

   • 선형 복잡도라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미

   def print_data(data):
       for i in range(len(data)):
           print(data[i])

4. O(𝑛2)

   • 2차 복잡도라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미

   def print_data(data):
       for i in range(len(data)):
           for j in range(len(data)):
               print(data[i], data[j])

• 1부터 n까지 합을 구하는 알고리즘

1. O(n)

   def sum_all(n):
     total = 0
     for num in range(1, n+1):
       total += num
     return total

2. O(1)

   

   def sum_all(n):
     return int(n*(n+1)/2)

• 위와 같이 동일한 문제를 푸는 알고리즘은 다양할 수 있음. 어떤 알고리즘이 보다 좋은지 객관적으로 비교하기 위해 빅오 표기법 등 시간 복잡도 계산법을 이용

정렬(sort)

• 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것
• 프로그램 개발 시 빈번하게 정렬을 필요로 함
• 다양한 알고리즘이 고안되었으며 알고리즘 학습의 필수 사항

버블 정렬(bubble sort)

• 두 인접한 데이터를 비교해서 앞에 있는 데이터가 뒤에 있는 데이터보다 크면(작으면) 자리를 바꾸는 정렬 알고리즘

def bubblesort(data):
  for i in range(len(data)):
    for j in range(len(data) - i - 1):
      if data[j] > data[j+1]:
        data[j], data[j+1] = data[j+1], data[j]
  return data

삽입 정렬(insertion sort)

• 인덱스(key) 앞에 있는 데이터(A)부터 비교해서 key가 더 작으면(크면) 데이터(A)값을 뒤 인덱스로 복사
• key가 더 큰 데이터를 만날 때까지 반복
• 큰 데이터를 만난 위치 바로 뒤에 key를 이동

[https://upload.wikimedia.org/wikipedia/commons/9/9c/Insertion-sort-example.gif]

def insertionsort(data):
  for i in range(len(data)):
    for j in range(i + 1, 0, -1):
      if data[j] < data[j-1]:
        data[j], data[j-1] = data[j-1], data[j]
      else:
        break
  return data

선택 정렬(selection sort)

• 주어진 데이터 중, 최소값을 찾음
• 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함
• 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복

def selectionsrot(data):
  for i in range(len(data)):
    min = i
    for j in range(i, len(data)-1):
      if data[min] > data[j]:
        min = j
    data[min], data[i] = data[i], data[min]
  return data