초이의 끄적끄적

힙 자료구조

• 데이터를 정렬된 상태로 저장하기 위해서 사용하는 파이썬 heapq(힙큐) 내장 모듈 사용
• heapq 모듈은 이진트리(binart tree)기반의 최소 힙(min heap) 자료구조를 제공한다
• 최대, 최소값을 가져올 때 많이 사용한다

힙 관련 함수들 (import heapq)

• 힙 생성 - heap = [] 
• 힙 원소 추가 - heapq.heappush(heap, 4)
• 힙에서 원소 삭제 heapq.heappop(heap)) // 가장 작은 원소 삭제 후 그 값 리턴
• 최솟값 삭제하지 않고 얻기 - heap[0]
• 기존 리스트를 힙으로 변환 - heapq.heapify(heap)

import heapq	# 모듈 임포트
heap = []		# 힙 생성

# 힙에 원소 추가
heapq.heappush(heap, 4)	
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)
print(heap)
>>> [1, 3, 7, 4]

# 힙에서 원소 삭제
print(heapq.heappop(heap))	# 가장 작은 원소 삭제 후 그 값 리턴
print(heap)	
>>> 1
>>> [3, 4, 7]

# 최소값 삭제하지 않고 얻기
print(heap[0])
>>> 3

# 기존 리스트를 힙으로 변환
heap = [4, 1, 7, 3, 8, 5]
heapq.heapify(heap)
print(heap)
>>> [1, 3, 5, 4, 8, 7]

+ 힙 정렬

import heapq

def heap_sort(nums):
  heap = []
  for num in nums:
    heapq.heappush(heap, num)
  
  sorted_nums = []
  while heap:
    sorted_nums.append(heapq.heappop(heap))
  return sorted_nums

print(heap_sort([4, 1, 7, 3, 8, 5]))

>>> [1, 3, 4, 5, 7, 8]

+ 최대 힙

• heapq 모듈은 최소 힙만 동작하기 때문에 최대 힙으로 하기 위해 요령이 필요
• 힙에 튜플(tuple)을 원소로 추가하거나 삭제하면, 튜플 내에서 맨 앞에 있는 값을 기준으로 최소 힙이 구성되는 원리를 이용한다
• 따라서, 최대 힙을 만들려면 각 값에 대한 우선순위를 구한 후, (우선 순위, 값) 구조의 튜플(tuple)을 힙에 추가하거나 삭제하면 됩니다. 그리고 힙에서 값을 읽어올 때는 각 튜플에서 인덱스 1에 있는 값을 취하면 됩니다. (우선순위에는 관심이 없으므로 )

import heapq

nums = [4, 1, 7, 3, 8, 5]
heap = []

for num in nums:
  heapq.heappush(heap, (-num, num))  # (우선 순위, 값)

while heap:
  print(heapq.heappop(heap)[1])  # index 1
  
>>> 8
>>> 7
>>> 5
>>> 4
>>> 3
>>> 1

+ K번째 최소값/최대값

• K번째 최소값을 구하기 위해서는 주어진 배열로 힙을 만든 후, heappop() 함수를 K번 호출하면 됩니다.

import heapq

def kth_smallest(nums, k):
  heap = []
  for num in nums:
    heapq.heappush(heap, num)

  kth_min = None
  for _ in range(k):
    kth_min = heapq.heappop(heap)
  return kth_min

print(kth_smallest([4, 1, 7, 3, 8, 5], 3))

>>> 4

+ 힙 개념 문제 :

2021.03.19 - [알고리즘] - 20210319_코테공부

+ 이중우선순위큐

https://programmers.co.kr/learn/courses/30/lessons/42628

기본 딕셔너리 구조 - Key와 Value를 한 쌍으로 갖는 자료형

{Key1:Value1, Key2:Value2, Key3:Value3, ...}

※ key는 고유한 값이여야 한다. 중복 시 나머지 무시함

※ key에는 리스트 쓸 수 없다. value에는 가능

딕셔너리 선언

>>> dic = {}	# 딕셔너리 선언

>>> dic[1] = 'a' # 딕셔너리 쌍 추가
>>> dic['name'] = 'pey'
>>> dic
{1: 'a', 'name': 'pey'}
>>> dic[1]		# key 사용해 value 얻기
'a'

>>> del a[1]	# 딕셔너리 삭제 del a[key값] index아님
>>> a
{2: 'b', 'name': 'pey', 3: [1, 2, 3]}

딕셔너리 관련 함수들

• key 리스트 만들기 - a.keys() # dict_keys 객체 반환
• value 리스트 만들기 - a.values() # dict_values 객체 반환
• key, value 쌍 얻기 - a.items() # 튜플로 묶은 값을 dict_items 객체로 반환
• key : value 쌍 모두 지우기 - a.clear()
• key로 value 얻기 - a.get('키값')
  • a.get('name')과 a['name']과 동일한 결과값 
  • But 키가 존재하지 않을 경우, a.get('nokey')는 None을, a['nokey']는 오류 발생
• 해당 key가 딕녀서리 안에 있는지 조사하기 - in (True, False 반환)
  • ex) 'a' in dic: ~~~

※ dict_keys 객체는 리스트 고유의 append, insert, pop, remove, sort 함수는 수행할 수 없다. 때문에 list로 변환해서 사용해야됨 -> list(a.keys())

>>> a = {'name': 'pey', 'phone': '0119993323', 'birth': '1118'}
>>> a.keys()
dict_keys(['name', 'phone', 'birth'])

>>> a.values()
dict_values(['pey', '0119993323', '1118'])

>>> a.items()
dict_items([('name', 'pey'), ('phone', '0119993323'), ('birth', '1118')])

>>> a.clear()
>>> a
{}

>>> a.get('name')
'pey'

>>> 'name' in a
True

딕셔너리 정렬 -> 기본. sorted를 이용한다

- key값을 이용한 정렬

>>> dict = {'A' :1,'D' :4,'C' :3,'B' :2}
>>> sdict= sorted(dict.items()) # 오름차순 정렬
[('A', 1), ('B', 2), ('C', 3), ('D', 4)]

>>>sdict= sorted(dict.items(), reverse=True) # 내림차순 정렬
[('D', 4), ('C', 3), ('B', 2), ('A', 1)]

- value값을 이용한 정렬 

-> items()와 lamba를 사용한다

• 딕셔너리에 items() 메서드를 사용해주면 {"key" : value}의 형태를 [(key, value)]의 형태로 만들어 준다. -> 튜플
• 이를 sorted해주면 key값을 기준으로 오름차순으로 정렬해준다.
• value값으로 정렬하려면 lambda를 사용해주면 된다. ( [0]일 경우 key기준, [1]일 경우 value 기준 정렬 )
• 내림차순 정렬 시, reverse=True

>>> dict = {'A' :1,'D' :4,'C' :3,'B' :2}
>>> sdict= sorted(dict.items(), key= lamba x : x[1])
[('A', 1), ('B', 2), ('C', 3), ('D', 4)]

+ itemgetter를 사용한 정렬

• python의 내장모듈 operator를 이용한 정렬
• key = itemgetter(기준 인덱스)

>>> from operator import itemgetter
>>> dict = {'A' :1,'D' :4,'C' :3,'B' :2}
>>> sdict= sorted(dict.items(), key= itemgetter(1))
[('A', 1), ('B', 2), ('C', 3), ('D', 4)]

+ 딕셔너리 선언, 정렬 문제 : 

2021.03.16 - [알고리즘] - 20210316_코테공부