개념 정리 : DP 개념정리 & 예시코드 작성

밀라 알고리즘 스터디 4주차 개념 정리 

 

✍🏻DP
: Dynamic Programming 
기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것

- 이미 계산된 결과는 별도의 메모리 영역에 저장해서 다시 계산하지 않도록 함
- 메모리 적절히 사용하여 수행시간 효율성 향상

 

✍🏻DP를 사용하는 경우
 : 일단 재귀함수, 그리디 , 완전 탐색 등 다른 방법으로 풀 수 있는지 생각
 : 그 이후로 코드 개선이나 되는 경우가 없으면 DP를 고려
- 대표적인 사용 경우 
      : 최적 부분 구조 - 큰 문제를 작은 문제로 나눌 수 있을 때 (= 작은 문제의 답을 모아서 큰 문제를 해결함)
      : 중복되는 부분 문제 - 동일한 작은 문제 반복적 해결

✍🏻Top-Down : 재귀적 구현

ex. 메모이제이션
: 기저 상태에서 출발하는 대신 위에서부터 바로 호출을 시작하여 다음 결과값을 재귀를 통해 전이시켜 재활용하는 방식

 

🧑🏻‍💻구현🧑🏻‍💻

let fiboArr = [0];
let fiboWithMemoization = (n) => {
  if (n < 3) {
    fiboArr[n] = 1;
  }

  if (!fiboArr[n]) { 
    fiboArr[n] = fiboWithMemoization(n - 1) + fiboWithMemoization(n - 2); //재귀 이용해 구현
  }

  return fiboArr[n];
};

✍🏻Bottom-Up : 반복문으로 구현
ex. DP 테이블
: 아래에서부터 계산을 수행하고 누적시켜서 전체 큰 문제를 해결하는 방식 

 

🧑🏻‍💻구현🧑🏻‍💻

int d[100];
int fibonacci(int n) {
  d[0] = 0;
  d[1] = 1;
  
  for(int i=2; i<=n; i++){
    d[i] = d[i-1] + d[i-2]; //반복문 이용해 구현
  }
  
  return d[n];
}

 

✍🏻DP 사용 방법
1) DP로 풀 수 있는 문제인지 확인
2) 문제의 변수 파악
3) 변수 간 관계식 만들기(: 점화식)
4) 메모하기(: 변수 값에 따른 결과를 저장)
- Top-down : memoization
- Bottom-up : tabulation 
5) 기저 상태 파악하기 
6) 구현하기