6주차: 그리디 알고리즘과 동적 계획법

출처
📚 Do it! 알고리즘 코딩 테스트 파이썬 편
📚 쉽게 배우는 자료구조 with 파이썬

그리디 알고리즘(greedy algorithm)

'탐욕법'이라고도 불리는 그리디(greedy) 알고리즘은 현재 상태에서 보는 선택지 중에서 최선의 선택을 하는 알고리즘이다.

그리디 알고리즘 수행 과정:
1. 해 선택: 현재 상태에서 최선의 해를 선택함
2. 적절성 검사: 선택한 해가 제약조건에 벗어나지 않는지 검사함
3. 해 검사: 현재까지 선택한 해의 집합이 전체 문제를 해결할 수 있는지 검사함

우선순위 큐

그리디 알고리즘에서는 주로 우선순위 큐를 이용해 문제를 해결한다.

기존의 큐(Queue)는 FIFO 방식의 자료구조였다면,
우선순위 큐는 우선순위가 높은 데이터가 먼저 나가는 방식이다.
일반적으로 힙(heap)을 이용해 구현한다.

힙(heap)

우선순위 큐를 위해 고안된 완전 이진 트리의 형태이다.
힙은 다음 두 가지의 조건을 만족해야 한다.

1. 완전 이진 트리
2. 모든 노드는 값을 갖고,
   2-1. 최대 힙: 자식노드(들)보다 크거나 같다
   2-2. 최소 힙: 자식노드(들)보다 작거나 같다.

---

❗️ 완전 이진 트리

루트부터 시작해 모든 노드가 정확히 자식 노드를 2개씩 가진 트리를 포화 이진 트리라고 한다.

반면 노드 수가 맞지 않아 포화 이진 트리를 만들 수 없을 때, 최대한 포화 이진 트리에 가깝게 만든 것이 '완전 이진 트리'이다.

완전 이진 트리는 리스트로 표현할 수 있다.
리스트가 A[0]부터 시작된다면, A[k]의 자식은 A[2k+1]과 A[2k+2] 이다.
반대로, A[k]의 부모 노드는 A[(k+1)/2]가 된다.

다음은 10개의 원소로 구성된 힙과 이에 대응하는 리스트이다.

---

힙의 ADT: __A[], insert(x), deleteMax(), max(), buildHeap(), isEmpty(), clear()

python에서는 heapq모듈과 PriorityQueue모듈을 제공한다. 이를 이용해서 힙 자료구조를 사용할 수 있다.

from queue import PriorityQueue
from heapq import heappush, heappop, heapify

그리디 알고리즘 활용 문제풀이 링크

---

동적 계획법

다이나믹 프로그래밍(dynamic programming)이라고도 불리는 동적 계획법은, 복잡한 문제를 여러 개의 작은 문제로 분할하여 부분의 문제들을 해결함으로써 전체 문제를 해결하는 방법을 말한다.

동적 계획법의 원리와 구현 방식
1. 큰 문제를 작은 문제로 나눌 수 있어야 한다.
2. 작은 문제들이 반복되어 나타나고, 그 결과값은 항상 일정하다.
3. 메모이제이션 기법을 이용한다.
4. 톱-다운 방식과 바텀-업 방식으로 구현된다.

동적 계획법의 가장 대표적 예제인 피보나치 수열을 예로 들어 동적 계획법을 이해해보자.

1. 동적 계획법으로 해결할 수 있는지 확인 (1, 2)
   6번째 피보나치 수는 5번째 피보나치 수와 4번째 피보나치 수의 합이고, 5번째 피보나치 수는 4번째와 3번째의 합이다. 즉, 작은 문제로 나눌 수 있고 수열의 합은 항상 같기 때문에 동적 계획법으로 해결할 수 있다.

2. 점화식 세우기
   F[i] = F[i-1] + F[i-2]

3. 메모이제이션 원리 이해하기

   ❗️ 메모이제이션(memoization) 이란, 부분 문제를 풀었을 때 이 문제를 DP 테이블에 저장해 놓고, 다음에 같은 문제가 나왔을 때 재계산하지 않고 DP테이블의 값을 이용하는 것을 말한다. 이 방식을 사용하면 불필요한 연산과 탐색이 줄어들어 시간복잡도 측면에서 매우 유리하다.

   한 번 계산한 피보나치 수열의 값은 DP테이블에 저장된다. 이후 수열의 값을 계산할 때, 이전 값들을 새로 계산하는 것이 아니라 DP테이블에서 값을 리턴받아 사용할 수 있다.

4. 탑다운, 바텀업 방식 이해하기
   1) 탑-다운 (Top-down):
   위에서부터 문제를 파악해 내려오는 방식으로, 주로 재귀함수 형태로 코드를 구현한다.

   import sys
   input = sys.stdin.readline
   
   N = int(input())
   D = [-1]*(N+1)
   D[0] = 0
   D[1] = 1
   
   def fibo(n):
       if D[n] != -1:
           return D[n]
   
       D[n] = fibo(n-2) + fibo(n-1)
       return D[n]
   
   a = fibo(N)
   print(a)

   2) 바텀-업 (bottom-up):
   가장 작은 문제부터 해결하면서 점점 큰 문제로 확장해 나가는 방식. 주로 반복문을 사용하여 코드를 구현한다.

   import sys
   input = sys.stdin.readline
   
   N = int(input())
   D = [-1]*(N+1)
   D[0] = 0
   D[1] = 1
   
   for i in range(2, N+1):
       D[i] = D[i-2] + D[i-1]
   
   print(D[N])

동적계획법 활용 문제풀이 링크

---