TIL - Heap / Dynamic Programming / DFS&BFS (문제풀이 위주)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

import heapq #heap 라이브러리 사용

def solution(scoville, K):
    answer = 0
    # heapify, heappop, heappush 활용
    heapq.heapify(scoville) #min heap 구성
    while True:
        s1 = heapq.heappop(scoville)
        if s1 >= K : #모든 스코빌 지수가 K이상
            break
        elif len(scoville) == 0: # K이상으로 만들 수 없는 경우
            answer = -1
            break
        s2 = heapq.heappop(scoville)
        newS = s1 + s2*2
        heapq.heappush(scoville,newS)
        answer += 1
    return answer

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def solution(N, number):
    strN = str(N)
    # 직관적인 코드를 위해 다음과 같이 index : 1~8 사용 설정 (index 0은 사용하지 않음)
    numberUsed = [{} for _ in range(9)]
    for i in range(1, 9):
        numberUsed[i] = {int(strN * (i))}   # N을 i번 나열한 숫자 ex) 555, 7777, ...
        for j in range(1 , i):
            for n1 in numberUsed[j]:
                for n2 in numberUsed[i-j]:
                    newNumbers = [n1*n2, n1+n2, n1-n2]
                    if n2 != 0 : newNumbers.append( n1//n2 )
                    numberUsed[i].update(newNumbers) #set1.update(set2) 사용하여 원소 추가. set 아닌 list를 넘겨줄수도 있다.
        if number in numberUsed[i]:
            return i
    return -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def solution(tickets):
    routes = {}
    for a, b in tickets: #출발지, 도착지
        routes[a] = routes.get(a, []) 
        routes[a].append(b)
    
    for r in routes:
        routes[r].sort(reverse=True) 
        # 역순인 이유? 파이썬의 데이터 삭제 과정을 살펴보면 뒤에서 뽑는게 더 효울적이기 때문    
    stack = ["ICN"]
    path = []
    while 0 < len(stack):
        top = stack[-1]
        if top not in routes or len(routes[top]) == 0: # 이 공항에서 떠나는 티켓이 존재하지 않음
            path.append(stack.pop()) 
        else :
            stack.append(routes[top].pop())
    return path[::-1]