본문 바로가기

dev course - DE/TIL

[데브코스] 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]

'dev course - DE > TIL' 카테고리의 다른 글

[데브코스] TIL 7일차  (0) 2024.04.02
[데브코스] TIL 6일차  (0) 2024.04.01
[데브코스] TIL 4일차  (0) 2024.03.28
[데브코스] TIL 3일차  (1) 2024.03.27
[데브코스] TIL 2일차  (0) 2024.03.26