🌓 Dynamic Programming

💫 Dynamic Programming (동적 프로그래밍, 동적 계획법)

---

여러 개의 하위 문제를 먼저 푼 후에 그 결과를 쌓아올려서 주어진 문제를 해결하는 알고리즘
쉽게 설명하면 문제를 해결하기 위한 점화식을 찾아낸 후 점화식의 항을 밑에서부터 차례로 구해나가서 답을 알아내는 형태의 알고리즘.

피보나치 문제
피보나치 수열의 N번째 항을 지금처럼 재귀적으로 구하면 중복된 연산이 계속 발생해서 O(1.618N)의 시간이 걸립니다.
그런데 피보나치 문제를 DP로 해결하면 이렇게 미리 배열을 만들어두고 0번째 인덱스부터 하나씩 채워가는 방식으로 해결할 수 있고 N+1칸을 채우고 나면 답을 알 수 있으니 O(N)에 답을 알아낼 수 있습니다.

이렇게 중간 결과를 저장해서 이용하는지 그렇지 않은지에 따라 극적인 시간복잡도의 차이가 발생합니다.

DP를 풀기 위해서는 먼저 테이블을 정의해야 하고 점화식을 찾은 후에 초기 값을 정해야 합니다.
DP는 작정하고 어렵게 하고자 한다면 한도 끝도 없이 어려워지지만, 코테에 나올 수준의 DP 문제는 일단 점화식만 찾고나면 그 뒤는 초기 값을 채워넣은 후에 반복문을 돌면서 배열을 채우면 끝이어서 구현이 굉장히 쉽습니다.

하지만 다양한 DP 문제를 풀어봤거나 뛰어난 수학적 직관력을 가지고 있지 않은 이상 문제에서 점화식을 이끌어내는 과정이 그렇게 쉽지 않고, 무엇보다도 초보 단계에서는 주어진 문제가 DP로 푸는 문제라는 것 자체를 알아차리지 못할 수도 있습니다.

문제집 문제 존나 풀어볼 것
1로 만들기

부분제를 미리 풀고 저장해두긴 하는데, 이게 해답을 구할때 쓰일지 안쓰일지는 모름.
아무튼 일단 미리 구해놓고 보는것이다.

각 부문제의 해답을 풀어서 저장하고 나중에 같은 부문제의 답이 필요한 경우 저장된 해답을 찾아서 해결

• 부문제를 이용한 다른 알고리듬
  • 욕심쟁이 방법: 각 단계에서 해답의 일부를 선택한 후 남은 부문제를 해결
  • 분할정복: 귀납적 정의를 이용하여 부문제로 분할, 정복, 결합
    

🫧 vs Divide-Conquer

분할정복은 문제 자체를 나누고 푸는거라, 풀어둔 것들이 나중에 해답을 구할 때 다 쓰인다.
중첩된 부문제 스탈이면 동적 계획법, 아니면 분할 정복

• 공통점
  • 순환적으로 정의된 문제로부터 출발

@ 4_0000

• 중첩된 부문제 (Overlapping Subproblems) 특성
  • 부문제들이 심하게 중복되는 문제
  • DC : 같은 함수를 반복해서 순환 호출 (4_0000), 즉 부문제를 독립적으로 처리하기 때문에 동일한 부문제도 매번 새로 풀어야 함
  • DP : 동일한 부문제가 몇 번 등장하건 간에 한번만 풀면 되기 때문에, 중복된 부문제의 수가 증가하면 할수록 유리
  • 부문제가 중복되지 않는 문제 : DP의 장점이 의미가 없고, 오히려 최종 해답에 쓰이지 않을 답을 미리 계산하느라 많은 시간을 낭비
• DC
  • 적합한 예: 합병정렬, 퀵정렬
    • 부문제들이 중복되지 않음: 중첩된 부문제 특성이 없음
  • 큰 문제를 작은 문제로 쪼갠 후 부문제를 해결하려는 전략 → 하향식
• DP
  • 적합한 예: 피보나치 수열 계산
    • 부문제들이 심하게 중복: 중첩된 부문제 특성을 가짐
  • 부문제를 풀고 이를 이용하여 더 큰 문제를 해결하는 전략 → 상향식

int IterativeFib(int n)
{
	int[] fib = new int[MAX_SIZE];
	fib[0] = 0;
	fib[1] = 1;
	for (int i = 2; i <= n; i++)
		fib[i] = fib[i - 1] + fib[i - 2];
	return fib[n];
}

🫧 vs Greedy

• 공통점: 최적 부분 구조를 갖는 최적화 문제를 해결

최적해 : 최고 좋은 해답

• 그리디
  • 최적해를 보장한다는 증명만 되면 가장 효율적
  • 최적해의 일부를 먼저 선택한 후 남은 부문제를 해결하려는 전략 → 하향식
• 동적 계획법
  • 일반적인 문제 + 최적화 문제: 범용성
  • 문제를 해결하기 위한 모든 대안들의 답을 구하고 그 가운데 최적의 해답을 찾음 → 지능적인 무작위 기법, 상향식
    

🫧 동적 계획법의 적용

• ➊ 최적화 문제의 경우 최적 부분구조를 갖는지 검증
• ➋ 문제를 순환적으로 정의
• ➌ 중첩된 부문제 특성을 갖는지 조사
• ➍ 부문제의 해답을 저장하고 이로부터 최적해를 구성하는 알고리즘을 구축
  

🫧 Memoization

Memoization

💫 정리

---

• 정리
  • 최적 부분구조를 갖는 최적화 문제를 해결하는데 사용
  • 특히 부문제가 중첩되는 정도가 높을수록 유용
  • 크기 별로 가능한 모든 문제를 미리 풀어놓고 재사용하기 때문에 지능화된 무작위 기법이라는 별칭

중첩도가 높으면, 부문제가 똑같은 걸 많이 쓰면, 미리 다 풀어두고 쓰는 동적 계획법
낮으면 미리 풀어둔 부문제를 안써서 효율이 낮으니까, 차라리 분할정복을 고려해볼것

• 기타 예제
  • 데이터의 유사성을 알아내는데 유용한 최장 공통 부분순서 (longest common subsequence) 문제
  • 2장에서 다룬 여행하는 외판원 문제
  • 음성 인식이나 합성에서 사용되는 비터비(Viterbi) 알고리즘
    

💫 이용

---

0-1-KnapSack-Problem
Algorithm-Bellman-Ford
Algorithm-Floyd-Warchall