두시간 알고리즘 - 9일차, 다이나믹 프로그래믹 완전 정복 Chapter3, 4 예제

다이나믹 프로그래밍은 "복잡한 문제를 간단한 여러 개의 문제를 나누어 푸는 방법"으로 어떤 특정한 프로그래밍 기법같은게 아니다. 아무래도 이거 이름 지은 사람은 어쩌면 많은 프로그래머들의 삶에 죄를 조금씩 지은거아닐까. 이거때문에 혼란스러워하는 사람들이 한둘이 아니니. 내 느낌엔 복잡한 문제를 간단하게 풀어야겠다, 하는 마음가짐이 다이나믹 프로그래밍 같다. 안다고해서 문제를 풀때는 도움이 되는 느낌은 안들었다. 왜냐하면 어떻게 간단하게 풀건가, 부분이 핵심인데 다이나믹 프로그래밍이 뭔지 안다고 어떻게 간단하게 푸는진 알아지질 않더라. 그래도 어떻게 접근하면 좋을지를 익혀보려고 한다. .

Chapter3예제 JavaScript화

// 코드 2-5
const cost = [
  [0, 10, 75, 94], 
  [-1, 0, 35, 50],
  [-1, -1, 0, 80],
  [-1, -1, -1, 0]
];

const memo_cost = [
  [0, 0, 0, 0],
  [0, 0, 0, 0],
  [0, 0, 0, 0],
  [0, 0, 0, 0]
]

// s가 시작, d가 종착역
const minCost = (s, d) => {
  
  if(s === d || s === d-1){
    // 같은 역이거나, 한정거장 차이날때
    return cost[s][d];
  }
  
  if(memo_cost[s][d] === 0){
    // s와 d사이가 계산이 안됬을때
    let minValue = cost[s][d]; // s에서 d로 가는 표 바로산거
    for(let i = s+1; i < d; i++){
      let temp = minCost(s, i) + minCost(i, d);
      if(temp < minValue){
        minValue = temp;
      }
    }
     memo_cost[s][d] = minValue;
  }
  
  return memo_cost[s][d];
}

minCost(0, 3); 

// 상향식 다이나믹 프로그래밍으로 해결할때(메모 전략 적용)
const dpMinCost = (n) => {
  const minValue = [0, 0, 0, 0];
  minValue[0] = 0;
  
  minValue[1] = cost[0][1];
  
  for(let i = 2; i <= n; i++){
    minValue[i] = cost[0][i]; // 안거치고 바로 갈때
    for(let j = 1; j < i; j++){
      // 0에서 i사이에서 한번은 거쳐갈때
      if(minValue[i] > minValue[j] + cost[j][i]){
        minValue[i] = minValue[j] + cost[j][i];
      }
    }
  }
  
  return minValue[n];
}

dpMinCost(3)

// 예제: 부분 문자열 다루기
const maxSubStringLen = (str) => {
  let n = str.length;
  let maxLen = 0;
  
  const sum = Array.from({length: n}).map((_) => Array.from({length: n}).map(_ => 0));

  for(let i = 0; i < n; i++){
    sum[i][i] = +str[i];
  }
  
  for(let len = 2; len <= n; len++){
    for(let i = 0; i < n - len + 1; i++){
      let j = i + len - 1;
      let k = Number.parseInt(len / 2);
      
      sum[i][j] = +sum[i][j-k] + +sum[j-k+1][j]; // 반쪼개놓으면 거기에 대해선 항상 해결이 되어있음
      
      if(len % 2 === 0 && sum[i][j-k] === sum[j-k+1][j] && len > maxLen){
        maxLen = len;
      }
    }
  }
  
  return maxLen;
}

console.log(maxSubStringLen("142124"))
console.log(maxSubStringLen("9430723"))

 

Chapter4예제 JavaScript화

다이나믹 프로그래밍을 사용해서 문제를 풀때 저자는 아래 흐름으로 접근해보는 것을 추천했다. 

1. 재귀호출 방식으로 일단 들이박기..
2. 메모전략을 사용해서 캐쉬를 해서 최적화 해보기
3. 아니면 상향식으로 풀도록 해보기

최적의 하위구조(n에대해서 뭔가 풀때 n-1미만인 문제를 해결했던걸 활용해서 문제를 풀수있는 구조)라면 재귀방식한번서보고 반복계산을 memoization을 적용하거나, 상향식으로 풀수있도록 한번 개선해보는 것. 

 

이책이 정말 좋다고 느낀 부분은 다이나믹 프로그래밍 접근법으로 뭔가를 해결하려고 할때 어떤 문제를 겪고 있는지 머릿속을 열어본것처럼 상세하게 알려준다는 부분이다. 

 

아래는 저자가 제안하는 이 문제가 다이나믹 프로그래밍 접근방법으로 풀수있는가, 아닌가를 체크하는 방법이다. 

1. 문제를 같은 형태의 하위 문제로 나눌 수 있습니까?
2. 하위 문제의 계산이 반복되나요?
3. 최적화, 최대화, 최소화나 어떤 작업의 경우의 수를 구하는 유형의 문제입니까?

그리고 나서 해야할 생각은 이런거라고 한다.

1. 이렇게 확인해보고나서 다이나믹 프로그래밍으로 푸는게 맞다고 판단이서면 이제 점화식이나 재귀과정을 한번 정의해본다. 
   1. 문제를 하위문제를 사용해서 하향식으로 한번 정의해본다
   2. 재귀호출의 끝에 대해서 기본경우에 대해서 답을 정의한다
   3. 종료가 꼭 되어야하기때문에 어디서 종료할지를 정의한다
2. (선택적) 메모전략을 시도한다. 계속 반복되는 애들은 캐슁해둔다.
3. 재귀호출로 해결해본후에, 상향식으로 문제풀이를 한번 바꿔본다. 이때 모든 값을 캐슁하기보다는 필요한것만 캐슁해본다. 

// Chapter4
// 예제: 행렬에서 최소 이동 비용 구하기
const cost = [
  [1, 3, 5, 8], 
  [4, 2, 1, 7], 
  [4, 3, 2, 3]
] // cost[i][j] 해당 셀을 통과하는데 드는 비용

// 재귀호출
const getMin = (a, b) => {
  return a < b ? a : b;
}

// (0, 0)에서 (m, n)까지의 최소 이동 비용 
const minPathCost = (m, n) => {
  if(m === 0 && n === 0){
    return cost[m][n];
  }
  
  if(m === 0){
    // 가장 윗줄이다. 
    return minPathCost(0, n-1) + cost[0][n];
  }
  
  if(n === 0){
    // 가장 왼쪽 줄이다 
    return minPathCost(m-1, 0) + cost[m][0];
  }
  
  let fromAbove = minPathCost(m-1, n);
  let fromLeft = minPathCost(m, n-1);
  
  return getMin(fromAbove, fromLeft) + cost[m][n];
}

minPathCost(2, 3);

// memoization 전략 적용
const memo = [
  [0, 0, 0, 0],
  [0, 0, 0, 0],
  [0, 0, 0, 0],
]

const minPathCost2 = (m, n) => {
  if(memo[m][n]) {
    return memo[m][n];
  }
  
  if(m === 0 && n === 0){
    memo[m][n] = cost[m][n];
  }else if(m === 0){
    // 가장 윗줄이다. 
    memo[m][n] = minPathCost2(0, n-1) + cost[0][n];
  }else if(n === 0){
    // 가장 왼쪽 줄이다 
    memo[m][n] = minPathCost2(m-1, 0) + cost[m][0];
  }else{
    let fromAbove = minPathCost2(m-1, n);
    let fromLeft = minPathCost2(m, n-1);
  
    memo[m][n] = getMin(fromAbove, fromLeft) + cost[m][n];
  }
  
  return memo[m][n]
}

minPathCost2(2, 3);

// 상향식 다이나믹 프로그래밍
// (0, 0)에서 (m, n)까지 상향 이동하면서 경로상의 모든셀의 minPathCost를 계산하는 방식
const minPathCost3 = () => {
  const memo = [
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
  ]
  
  // 제일 윗행을 채운다
  memo[0][0] = cost[0][0];
  
  for(let j = 1; j < cost[0].length; j++){
    memo[0][j] = memo[0][j-1] + cost[0][j];
  }
  
  for(let i = 1; i < cost.length; i++){
    memo[i][0] = memo[i-1][0] + cost[i][0];
  }
  
  for(let i = 1; i < cost.length; i++){
    for(let j = 1; j < cost[0].length; j++){
      memo[i][j] = getMin(memo[i-1][j], memo[i][j-1]) + cost[i][j];
    }
  }
  
  return memo[cost.length - 1][cost[0].length - 1];
}

minPathCost3();

// 연습 문제 4-1, 
const minPathCost4 = () => {
  const memo = [
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
  ]
  
  // 제일 윗행을 채운다
  memo[0][0] = cost[0][0];
  
  for(let j = 1; j < cost[0].length; j++){
    memo[0][j] = memo[0][j-1] + cost[0][j];
  }
  
  for(let i = 1; i < cost.length; i++){
    memo[i][0] = memo[i-1][0] + cost[i][0];
  }
  
  for(let i = 1; i < cost.length; i++){
    for(let j = 1; j < cost[0].length; j++){
      // 대각선 위쪽 방향도 비교를 해줘야함
      memo[i][j] = getMin(getMin(memo[i-1][j], memo[i][j-1]), memo[i-1][j-1]) + cost[i][j];
    }
  }
  
  console.log(cost, memo)
  return memo[cost.length - 1][cost[0].length - 1];
}

minPathCost4();

// 예제: 타일로 공터 채우기
// 재귀호출
const countWays = (n) => {
  if(n <= 0 || !n) {
    return 0;
  }
  
  if(n === 1){
    return 1;
  }
  if(n === 2){
    return 2;
  }
  
  return countWays(n-1) + countWays(n-2);
}

countWays(5);

const countWays2 = (n) => {
  const arr = Array.from({length: n+1}).map(_ => 0);
  arr[1] = 1;
  arr[2] = 2;
  
  for(let i = 3; i <= n; i++){
    arr[i] = arr[i-1] + arr[i-2];
  }
  
  console.log(arr);
  return arr[n];
}

countWays2(5);


// 예제: 특정점수에 도달하는 경우의 수 구하기
const waysToScore = (n) => {
  if(n < 0) return 0;
  if(n === 0) return 1;
  return waysToScore(n-10) + waysToScore(n-5) + waysToScore(n-3); 
}

console.log("Ans", waysToScore(13));

const waysToScore2 = (n) => {
  const arr = Array.from({length: n+1}).map(_ => 0);
  
  arr[0] = 1;
  
  for(let i = 1; i <= n; i++){
    if(i - 3 >= 0){
      arr[i] += arr[i-3];
    }
    if(i - 5 >= 0){
      arr[i] += arr[i-5];
    }
    if(i - 10 >= 0){
      arr[i] += arr[i-10];
    }
  }
  
  return arr[n];
}

// 연습 문제 4-4,
const waysToScore3 = (n, cur) => {
  if(n < 0) return 0;
  if(n === 0) return 1;
  let count = 0;
  
  if(cur >= 10){
    count += waysToScore3(n-10, 10);
  }
  if(cur >= 5){
    count += waysToScore3(n-5, 5);
  }
  if(cur >= 3){
    count += waysToScore3(n-3, 3);
  }
  
  return count;
}

console.log("중복 제거", waysToScore3(13, 10));


// 예제: 연속된 부분 배열의 최댓값 구하기
const arr = [-2, -3, 4, -1, -2, 1, 5, -3];

const maxSubArray = () => {
  let maxSumSoFar = 0;
  let maxSumEndingHere = 0;
  
  for(let i = 0; i < arr.length ; i++){
    maxSumEndingHere += arr[i];
    
    if(maxSumEndingHere < 0){
      maxSumEndingHere = 0;
    }
    
    if(maxSumSoFar < maxSumEndingHere){
      maxSumSoFar = maxSumEndingHere;
    }
  }
  
  return maxSumSoFar
}

maxSubArray();

 

 

후기

연습문제가 답이 없어서 고민하다가 4-3은 못풀었는데, 그래도 뭘어쩌라는건지 상세하게 설명해줘서 좋은 챕터였다.