[TIL] Day 4~5 - 자료구조와 알고리즘(4)

람다식에서 슬라이스 가능 ex)

L.sort(key = lambda x : (x*4)[:4], reverve=True)

힙(heap) 이용

import heapq

heapq.heapify(L)  #리스트 자체 순서가 min heap으로 바뀐다
min_value = heapq.heappop(L) # 기본적으로 min heap이기 때문에 pop하면 최소값
heapq.heappush(L,item) # 자기 자리로 min heap을 유지하며 들어간다

# 각각의 명령어 시간복잡도 O( log N )

그렇다면 MAX heap 은?

데이터 형식을 ( -number, number ) 인 튜플 형식으로 push 하면,
앞의 마이너스값(0번 인덱스) 기준으로 min heap이 곧 뒤의 값(1번 인덱스)의 max heap

# lv2 배상비용 최소화 max heap
def solution(no, works):
    import heapq
    max_heap = []

    #max heap은 (-number, number) 값으로
    #index 0번쨰 튜플로 min heap이 index 1번쨰 튜플의 max heap이 된다
    for work in works :
        heapq.heappush(max_heap, (-work,work) )
    
    for i in range(no):
        # max heap의 실제 값은 튜블의 뒤에 즉 1번자리에 있기때문에 pop 할때도 1번자리
        temp = heapq.heappop(max_heap)[1]
        if temp == 0 :
            return 0
        else :
            temp -= 1
            heapq.heappush(max_heap, (-temp, temp) )
    
    return sum([ w[1]**2 for w in max_heap ])

동적 계획법 (DP)

알고리즘 진행에 탐색해야 할 범위를 동적으로 결정함으로 범위를 조절하며 구해간다.
재귀적인 방식으로 생각, 작은 문제 해결 -> 큰 문제 해결

# N으로 표현 문제 중
s = [ set() for _ in range(8) ]  # [set(),set() ... set()]
for i,x in enumerate(s, start = 1) :
	x.add( int(str(N) * i )
    # s는 set이므로 mutable 하기 때문에 x.add해도 s의 값이 바뀐다.