Dynamic Programming

야생피카츄·2023년 10월 24일

알고리즘

목록 보기

1/1

DP란?

Dynamic Programming ... 뭔가 이름만 들어도 무섭게 생겼다
-> 기억하기 알고리즘
-> 메모를 사용한다

어떻게 접근해야 할까?

1. DFS/ BFS로 풀 수 있는데 경우의 수가 너무 많은 문제

정수삼각형 문제 : 합이 최대가 되는 경로 구하기
최댓값을 구하기, 패턴이 보일 때까지 반복해서 봐봅시다.

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

경우의수
1줄 : 1개
2줄 : 2개
3줄 : 4개
4줄 : 8개
2^(n-1)

1000줄이면? 어머어마한 경우의 수

2. 경우의 수들에 중복적인 연산이 많은 경우

이미 최댓값이 될 수 없는 조합도 연산을 해서 시간 낭비를 하고 있는 경우
각 위치까지 올 수 있는 최적의 값만 남겨 놓고 나머지 조합을 다 버립니다.
안될 조합들을 미리 버려 가장 좋은 조합들만 다시 경쟁을 시켜 가장 좋은 조합을 얻어냅니다.

3. 문제 해결 접근 방법

문제를 많이 풀어보고 풀이들을 참고해 DP식 사고방식을 습득 하는 게 좋습니다.
30분 고민 후 풀이를 참고해서 구현만 해보는 방식을 추천합니다.
30분 동안 고민할 것
- 현재 단계까지 연산을 잘 했는데 그 연산을 또 하지 않으려면 어떤 정보를 남겨야 하지?
- 어떤 식으로 정보를 누적 해야 되지?

수행시간 단축 기법이기 때문에 구현 방법이 다양합니다.

재귀/DFS를 활용한 풀이

피보나치 수

idx	0	1	2	3	4	5	6	7	8	9
fib	0	1	1	2	3	5	8	13	21	34

fib(n) = fib(n-1) + fib(n-2)
fib(0) = 0
fib(1) = 1

function fib(num){
	// 2. 탈출 조건
	if (num < 2) return num;
	// 1. 기본 동작
	return fib(num-1) + fib(num-2)
}

만약 num의 크기가 크다면? -> 중복되는 연산이 다수 발생!

이미 계산되었던 중복 작업이 많이 호출됩니다.

DP적으로 생각해보자...
- 내가 한 번 연산한 것을 다시 연산하지 않겠다
- 어딘가 저장해 뒀다 똑같은 연산을 두번 사용하는 일이 없게 하겠다

function fib(num) {
  // -1 : 한 번도 연산한 적이 없다
  if (dp[num] === -1) dp[num] = fib(num - 1) + fib(num - 2);

  return dp[num];
}

let dp = Array(100).fill(-1);

//계산이 필요없는 정의된 값
dp[0] = 0;
dp[1] = 1;

console.log(fib(10));

더 간단하게 할 수 있다...!

let num = 10;

let dp = Array(100).fill(0);

dp[1] = 1;

for (let i = 2; i < num + 1; i++) {
  dp[i] = dp[i - 1] + dp[i - 2];
}

console.log(dp[num]);