💡 DP(Dynamic Programming)

• Dynamic Programming = 동적 계획법
• 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법
• 부분 문제 반복과 최적 부분 구조를 가진 알고리즘을 더욱 적은 시간 내에 풀 때 사용

💻 원리

• 일반적으로 주어진 문제를 풀기 위해, 문제를 여러 개의 하위 문제로 나누어 푼다
• 나누어 푼 것을 결합하여 최종적인 목적에 도달하는 것
• 각 하위 문제를 해결한 뒤 해결책을 저장하여, 후에 하위 문제가 나왔을 경우 저장해둔 것을 사용해 간단하게 해결

  따라서 동적 계획법은 계산 횟수를 줄일 수 있다. 하위 문제의 수가 기하급수적으로 증가할 때 유용함

• 가능한 모든 방법을 고려해야 한다는 단점이 있음
  (이를 극복하기 위해 나온 것이 그리디 알고리즘)

📝 문제 링크

https://www.acmicpc.net/problem/16395

👩‍💻 적용

1. Top-Down : 재귀 함수

브루트포스를 DP로 착각했음.
내가 쓴건 재귀함수를 이용한 top-down 방식이 아니라, 그냥 브루트포스임

function pascalTriangle(line, order) {
  if (order == 1) {
    return 1;
  } else if (line == order) {
	  return 1;
  } else {
	  return pascalTriangle(line - 1, order) + pascalTriangle(line - 1, order - 1);
  }
}

console.log(pascalTriangle(n-1, k-1));

• line 번째 order 번째 수는 해당 요소 위행의 인접한 두 수의 합
• 모든 요소들은 같은 공식으로 이루어져 있음
• 즉, 분할 정복과 기저 조건을 사용하는 재귀함수로 풀 수 있다
• 첫 번째 수는 1을 return,
  line과 order가 동일하면 1을 return
  (1번째 행 1번째 수, 2번째 행 2번째 수, 3번째 행 3번째 수, 4번째 행 4번째 수... 모두 1이므로)
• 그 외의 수는 위행의 인접한 두 수의 합
  pascalTriangle(line - 1, order) + pascalTriangle(line - 1, order - 1)

동작 방법

pascalTriangle 함수가 호출될 때마다 콘솔을 찍어보자
맨 처음 입력값을 매개변수로 입력하여 호출했을 때,
k가 1도 아니고, n과 k가 같지도 않기 때문에
pascalTriangle(line - 1, order) + pascalTriangle(line - 1, order - 1)를 반환한다
이때 수식 앞쪽을 쭉 호출한 후 뒤쪽도 마저 호출하는 것을 볼 수 있다
재귀 함수는 호출한 역순으로 다시 올라간다

3번째 라인, 1번째 수 = 1 (order == 1)
2번째 라인, 1번째 수 = 1 (order == 1)
2번째 라인, 2번째 수 = 1 (line == order)
3번째 라인, 2번째 수 = 2번째 라인, 1번째 수+2번째 라인, 2번째 수 = 2 (위에 값이 구해져 있음)
.
.
.
5번째 라인, 3번째 수 = 6
이런 식으로 값을 구하는 것임

2. Bottom-Up : 반복문

let dp = Array.from(Array(31), () => Array(31).fill(0));

// 모든 행의 첫번째 수는 1
for (let i = 0; i < dp.length; ++i) {
  dp[i][0] = 1;
}

// 2번째 줄부터 쭉 계산(제일 왼쪽 값(index 0)은 위에서 세팅해 놓았으므로 pass)
for (let i = 1; i < dp.length; ++i) {
  for (let j = 1; j <= i; ++j) {
    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
  }
}

console.log(dp[n - 1][k - 1]);

• 상태 정의 : dp 배열을 만들었을 때 index 값이 의미하는 상태
• ex) dp[0][0] = 1번째 줄, 1번째 수 = 1
• 점화식 구하기 : dp[i][j] = dp[i-1][j-1]+dp[i-1][j]

동작 방법

let dp = Array.from(Array(31), () => Array(31).fill(0));

// 모든 행의 첫번째 수는 1
for (let i = 0; i < dp.length; ++i) {
  dp[i][0] = 1;
}

// 2번째 줄부터 쭉 계산(제일 왼쪽 값(index 0)은 위에서 세팅해 놓았으므로 pass)
for (let i = 1; i < dp.length; ++i) {
  for (let j = 1; j <= i; ++j) {
    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
    console.log(`dp[${i}][${j}] = ${dp[i][j]}`);
  }
}

console.log(dp[n - 1][k - 1]);

console 값을 찍어보면 아래와 같다

dp[1][1] = 1
dp[2][1] = 2
dp[2][2] = 1
dp[3][1] = 3
dp[3][2] = 3
dp[3][3] = 1
dp[4][1] = 4
dp[4][2] = 6
dp[4][3] = 4
dp[4][4] = 1
dp[5][1] = 5
dp[5][2] = 10
dp[5][3] = 10
dp[5][4] = 5
dp[5][5] = 1
dp[6][1] = 6
dp[6][2] = 15
dp[6][3] = 20
.
.
.
dp[30][17] = 119759850
dp[30][18] = 86493225
dp[30][19] = 54627300
dp[30][20] = 30045015
dp[30][21] = 14307150
dp[30][22] = 5852925
dp[30][23] = 2035800
dp[30][24] = 593775
dp[30][25] = 142506
dp[30][26] = 27405
dp[30][27] = 4060
dp[30][28] = 435
dp[30][29] = 30
dp[30][30] = 1

따라서 우리가 알고 있는

다음과 같은 파스칼의 삼각형을 만든 것이다
이제 우리가 원하는 값을 찾기만 하면 된다