[데브코스] TIL 5일차

힙(Heap) 대표 문제 풀이 - 더 맵게

1. 손으로 풀어보기
2. 알고리즘 복잡도 생각하기
   1) 리스트 이용
   - 각 단계("섞는 일")에서 요구되는 계산량 : 정렬된 리스트에 순서 맞춰 원소 삽입
   - 최악의 경우 O(N^2)
   
   2) 힙 이용
   - 힙은 완전 이진 트리 형태로 배열을 이용해서 구현 가능
   - 최소 혹은 최대 원소를 꺼내는 문제에선 힙을 이용하면 효율이 좋음
   - 힙의 연산을 다시 생각해보면, heapify (NlogN) / push (logN) / pop (logN)
   - 최악의 경우 O(NlogN)

import heapq
def solution(scoville, K):
    answer = 0
    
    heapq.heapify(scoville) # 최소 힙
    while scoville[0] < K:
        if len(scoville) >= 2:
            s1 = heapq.heappop(scoville)
            s2 = heapq.heappop(scoville)
            heapq.heappush(scoville,s1+s2*2)
            answer += 1
        else:
            return -1
        
    return answer

 

 

힙의 응용

1. 정렬(heapsort)
2. 우선 순위 큐(priority queue)

 

 

동적 계획법(Dynamic Programming)

- 주어진 최적화 문제를 재귀적인 방식으로 작은 문제로 쪼갬

- 그리고 이 작은 문제를 풀어, 이 해의 조합으로 전체 문제의 해답에 이르는 방식

- 알고리즘 진행에 따라 탐색 범위를 동적으로 결정함

 

1. 피보나치 수열
   1) 재귀함수로 구현한다면
   - 복잡도 : 지수 함수의 형태
   2) 동적 계획법으로 구현한다면
   - 복잡도 : 선형 함수의 형태
   
   
2. 이점
   - 문제의 성질에 따라, 동적계획법으로 풀어냄으로써 탐색 범위를 효과적으로 풀어낼 수 있음
   
   
3. 예시 - N으로 표현

def solution(N, number):
    s = [set() for _ in range(8)]
    for i,x in enumerate(s, start=1):
    	x.add(int(str(N) * i))
    for i in range(len(s)):
    	for j in range(i):
        	for op1 in s[j]:
            	for op2 in s[i - j - 1]:
                	s[i].add(op1 + op2)
                    s[i].add(op1 - op2)
                    s[i].add(op1 * op2)
                    if op2 != 0:
                    	s[i].add(op1 // op2)
        if number in s[i]:
            answer = i + 1
            break
    else:
        answer = -1
    	
    return answer

 

 

 

깊이/너비 우선 탐색(DFS/BFS) 대표 문제 풀이 - 여행 경로

- 

 

from collections import defaultdict
def solution(tickets):
    answer = []
    airport = defaultdict(list)
    vis = defaultdict(list)
    for dep,arr in tickets:
        airport[dep].append(arr)

    for i in airport.keys():
        airport[i].sort(reverse=True)
        
    def dfs():
        stack = ["ICN"]
        while stack:
            now = stack[-1]
            if not airport[now]:
                answer.append(stack.pop())
            else:
                stack.append(airport[now].pop())
    
    dfs()
    return answer[::-1]