[Python] 힙, 자료구조

순열

• 서로 다른 n개에서 서로 다른 r개를 선택하여 일렬로 나열하는 것

from itertools import permutations
data = ['A','B','C']
result = list(permutations(data, 3))

'''
서로다른 data 내에서 서로 다른 3개를 선택하여 모든 값을 리스트로 나열한다
'''

 

조합

• 서로 다른 n개에서 순서에 상관없이 서로 다른 r개를 선택하는 것

from itertools import combinations
data = ['A','B','C']
result = list(combinations(data, 2))

'''
서로다른 data 내에서 서로 다른 2개를 선택하여 모든 값을 리스트로 나열한다
'''

 

 

Counter

• 등장횟수를 세는 기능을 제공

from collections import Counter
counter = Counter(['red','blue','red','green','blue','blue'])

#일때,

counter['blue']
#= blue가 등장한 횟수 출력(3)
dict(counter)
#= 사전 자료형으로 변환 => 출력시 {'red': 2, 'blue': 3, 'green': 1} 이됨

 

 

최대공약수 최소공배수

• math 라이브러리의 gcd()를 이용하자

import math

math.gcd(21,14)  //최대공약수 계산 = 7
lcm(21,14)   //최소공배수 계산 = 42

 

 

힙 자료구조

• 이진트리 기반의 최소 힙 자료구조를 제공함
• 원소들이 항상 정렬된 상태로 추가/삭제됨

import heapq #힙 함수 적기전에 필요한것
heap = [] #초기화. 최소 힙 생성

heapq.heappush(heap, 4) #heap에 원소 추가하기
heapq.heappop(heap) #heap에서 원소 삭제하기

#기존 리스트를 힙으로 변환
heap1 = [4,1,2,3,5]
heapq.heapify(heap1)

 

최소값 얻기

• 리스트 첫번째 원소만 최소값이기 때문에, 두번째로 작은 원소는
• 첫번째 원소를 삭제후에 heap[0] 이런식으로 접근해야함

heapq.heappop(heap) #heap의 최소값 삭제
print(heap[0]) #두번째로 작은 원소 출력하기

 

최대 힙 구하기

• 힙에 튜플을 원소로 추가/삭제 하면,
• 튜플 내에서 맨 앞에 있는 값을 기준으로 최소 힙이 구성되는 원리를 이용한다
  • 우선순위  = 이 값을 기준으로 정렬, 값 = 원래값

heapq.heappush(heap1, (-num, num)) #(우선순위, 값)