[Algorithm] DP(Dynamic Programing)

🤖 Algorithm

---

🟦 Dynamic Programing

연산한 값을 기억해놓고 이 연산 결과를 재활용하여 다음 연산을 수행하는 방식

memoization
: 한 번 계산한 결과를 저장해두었다 재활용하는 최적화 기법

다음과 같은 경우에 사용

1. DFS/BFS로 풀 수는 있으나 경우의 수가 너무 많은 경우
   (DFS or 완전탐색으로 풀 수 있는 한계 -> 경우의 수 : 500만개)

2. 경우의 수들에 중복 연산이 많이 존재하는 경우

이미 계산한 값을 저장해두는 메모리를 cache라고 부름

ex) 조합 폭발 - 이항 계수

//nCr = n-1 C r-1 + n-1 C r
int bino(int n, int r)
{
	if(r==0 || n==r)
    {
    	return 1;
    }
    
    return bino(n-1, r-1) + bino(n-1, r);
}    

nCr = n-1 C r-1 + n-1 C r은 이항계수를 구하는 기본적인 수학 공식이다.
그러나 위와 같은 계산 식을 이용하여 이항계수를 구하게 된다면 중복 계산 多

따라서 메모이제이션을 사용하여 문제를 푸는 것이 좋다.

vector<vector<int>> cache(N,vector<int>(N,-1));
int bino(int n, int r)
{
	if(r==0 || n==r)
    {
    	return 1;
    }
    
    if(cache[n][r] != -1)
    {
    	return cache[n][r];
    }
    
    return cache[n][r] = bino(n-1, r-1) + bino(n-1, r);
}

위와 같이 코드를 구성하게되면 nCr의 결과값을 cache[n][r]에 저장해두고,
저장된 nCr의 값이 있는 경우 그 값을 재활용하기에 같은 연산을 수행하지 않는다.

❗DP 문제를 풀면서 항상 고려해야할 점

현재 단계에서 이전 단계로 돌아가지 말아야 한다 => 최적의 답을 쌓아가야 한다

➕ 내가 문제 풀면서 자주 놓친 부분

• 오버플로우
  int의 max => 2,147,483,647 유의

• cache[] 배열을 idx 1부터 N까지 사용하는 경우
  cache[0]이 문제의 답에 영향을 주는지 꼭 확인
  cache[] 배열 초기화할 때, 입력값과 무관한 값으로 초기화 할 것

문제 풀이 규칙

• 기저 사례를 가장 먼저 처리
  (ex - 배열의 index를 넘어가는 경우 종료)
• 함수의 반환값과 무관한 값으로 cache 배열 초기화
  (반환값이 >= 0 이라면 배열을 -1로 초기화 -> -1이면 계산한 적 없음)

  - 반복문이 아닌 memset 함수를 사용하여 배열 초기화하는 것이 편할 것
  memset(cache, -1, sizeof(cache));

• cache[a][b]의 값을 담는 참조형 변수를 사용하자
  (ex - int &ret -> 답을 저장할 때 간편 + 인덱스 순서 바꿔 쓰는 실수 X)

문제 풀이 과정

1. 재귀 호출에서 시작
   해당 문제를 재귀적으로 해결하는 완전 탐색 알고리즘을 만든다.

2. 중복된 부분 문제를 한 번만 계산하도록 메모이제이션을 적용한다.