오늘 배운 것🤓

Heap을 이용한 알고리즘 문제 풀이

• Heap은 완전이진트리를 만족하는 자료 구조로써, Max Heap, Min Heap으로 사용한다.
• 최대/최소 원소를 빠르게 찾을 수 있다는 장점을 가지고 있고, 완전이진트리 성질을 이용해 배열로써 구현이 가능하기 때문에 메모리적인 이점도 가지고 있다.
• 연산에는 힙 구성(Heapify), 삽입(insert), 삭제(remove)를 가지고 있다.
  • 힙 구성 : $O(NlogN)$
  • 삽입 : $O(logN)$
  • 삭제 : $O(logN)$
• 이런 특징과 연산에 근거하여 정렬(heapsort), 우선 순위 큐(Priority Queue) 에 사용된다.
• python에는 heapq라는 라이브러리를 사용한다. 단, 최소힙만 지원하기 때문에 최대힙은 따로 처리를 해주어야 한다.

1. 더 맵게
   • 여러 음식의 맵기가 담긴 리스트와 원하는 맵기 k가 주어지면 특정한 연산을 통해 모든 음식의 맵기를 k 이상으로 만드는 문제
   • 연산 : (가장 안매운 음식) + (두번째로 안매운 음식 *2)
   • 맵기의 크기 순대로 정렬한 뒤, 가장 작은 맵기와 두번째로 작은 맵기를 연산하여 다시 정렬해야하므로 힙을 사용한다.
   • 시간 복잡도 : $O(NlogN)$

import heapq

def solution(scoville, K):
    # 횟수가 1 증가할 때마다 1씩 늘어남
    answer = 0
    
    # scoville 리스트를 heap으로 만듬
    heapq.heapify(scoville)

    while True:
        # 가장 작은 맵기를 가져온다.
        min1 = heapq.heappop(scoville)
        # 가장 작은 맵기가 K보다 크거나 같다면 끝!
        if min1 >= K:
            break
        # 마지막 계산까지 K가 만족이 안됐다면 -1 반환
        elif len(scoville) == 0:
            answer = -1
            break
        # 두번째로 작은 맵기를 가져와서 연산하여 push한다.
        min2 = heapq.heappop(scoville)
        new = min1 + min2*2
        heapq.heappush(scoville, new)
        answer += 1
            
    return answer

동적 계획법(Dynamic Programming)을 이용한 알고리즘 문제 풀이

• 주어진 최적화 문제를 재귀적인 방식으로 작은 부분 문제로 나누어 부분 문제를 풀어 이 해를 조합하여 전체 문제의 해답에 이르는 방식
• 알고리즘의 진행에 따라 탐색해야 할 범위를 동적으로 결정함으로써 탐색 범위를 한정할 수 있다.
• 문제의 성향에 따라, DP로 풀어냄으로써 탐색하는 범위를 효과적으로 줄일 수 있다.
• 가장 대표적인 문제 : Knapsack 문제

1. N으로 표현
   • number와 N이 주어지고 N을 이용해서 사칙연산을 통해 number를 만들어야 한다. 이 때 사용되는 최소의 N의 수를 찾는 문제
     단, N은 1이상 9이하인 정수고 반환하는 최솟값이 8보다 크면 -1을 반환해야한다.
   • N을 1개 사용했을 때, 2개 사용했을 때, ... 8개를 사용했을 때 나올 수 있는 모든 경우의 수를 차례대로 늘려가면서 찾는다.

느낀 점

오늘은 보고서 작성하고 README 작성하는 등 여러 작업들 때문에 공부를 많이 하지는 못했다. 하지만 동적 계획법 문제풀이가 너무 재미있었다. 다시 한번더 코드를 살펴봐야할 것 같다.