두시간 알고리즘 12일차.. 다이나믹 프로그래밍 몇문제 풀기

1. 최소 교정 비용 문제

// 5.1 최소 교정 비용 문제

// 재귀 호출 을 사용하는 풀이와 설명
// str1에 뭔가 해서 바껴야함
const editDistance1 = (str1, index1, str2, index2) => {
  if(index1 >= str1.length - 1){
    return str2.length - index2;
  }
  if(index2 >= str2.length - 1){
    return str1.length - index1;
  }
  
  if(str1[index1] === str2[index2]){
    return editDistance1(str1, index1+1, str2,  index2 + 1);
  }
  
  // 삭제
  let d = editDistance1(str1, index1+1, str2, index2); // 하나 삭제
  
  // 업데이트
  let u = editDistance1(str1, index1+1, str2, index2+1);
  
  // 삽입
  let i = editDistance1(str1, index1, str2, index2+1);
  
  return Math.min(d, u, i) + 1; // 지금한 것
}

editDistance1("computer", +0, "commuter", +0);

// 다이나믹 프로그래밍을 사용하는 풀이와 설명
// d[i][j] str1의 i번째 글자까지랑, str2의 j번째 글자까지랑을 비교해서 i에 최소한의 뭔가를 해서 j로 될 수 있는 경우
const str1 = "sunday";
const str2 = "saturday";

const editDistance2 = (str1, str2) => {
  let m = str1.length;
  let n = str2.length;
  
  const d = Array.from({length: m+1}).map(_ => Array.from({length: n+1}).map(_ => 0));
  
  console.log(d);
  
  for(let j = 0; j <= n; j++){
    d[0][j] = j;
  }
  
  for(let i = 0; i <= m; i++){
    d[i][0] = i;
  }
  
  for(let i = 1; i <= m; i++){
    for(let j = 1; j <= n; j++){
      if(str1[i-1] === str2[j-1]){
        d[i][j] = d[i-1][j-1]; // 앞에 문자까지의 최소 교환 값이랑 같다. 
      }else{
        // 지금 삭제, 삽입, 치환 연산 중에 하나를 하고, 그전까지의 교환 횟수를 더해줌
        d[i][j] = 1 + Math.min(
          d[i][j-1], // 삽입, i번째문자까지포함하고 뭐하나를 삽입해서 j까지 문자를 만들어내야한다. 
          d[i-1][j-1], // 치환, i번째에 j번 문자랑 똑같은걸 집어 넣을거니까, 그앞에거까지나 교환횟수 맞추면됨
          d[i-1][j] // 삭제(해당 글자를 삭제하고 어찌됬건간에 j까지 다시 만들어내는 교환횟수
        )
      }
    }
  }
  
  return d[m][n];
}

editDistance2(str1, str2);

 

 

2. 직사각형에서 총 경로 수 구하기

// 재귀 호출을 사용해 총 경로 수를 구하는 함수
const numOfPaths = (m, n) => {
  if(m === 0 && n === 0){
    return 0;
  }
  
  if(m === 0 || n === 0){
    return 1;
  }
  
  return +numOfPaths(m-1, n) + +numOfPaths(m, n-1);
}

numOfPaths(2, 3);

// 다이나믹 프로그래밍을 사용하는 풀이와 설명
const numOfPaths2 = (m, n) => {
  const cache = Array.from({length: m}).map(_ => Array.from({length: n}).map(_ => 0));
  
  for(let i = 1; i < m; i++) {
    cache[i][0] = 1;
  }
  
  for(let j = 1; j < n; j++){
    cache[0][j] = 1;
  }
  
  for(let i = 1; i < m; i++){
    for(let j = 1; j < n; j++){
      cache[i][j] = cache[i-1][j] + cache[i][j-1];
    }
  }
  
  return cache[m-1][n-1];
}

numOfPaths2(3, 4);

 

3. 연습문제

- 연습 문제 5-1

// 연습문제 5-1

const getXY = (x, y) => {
  if(x === 0 && y === 0) return 0;
  if(x === 0 || y === 0) return 1;
  
  return getXY(x-1, y) + getXY(x, y-1);
}

getXY(3, 3);

const getXY2 = (m, n) => {
  const d = Array.from({length: m + 1}).map(_ => Array.from({length: n+1}).map(_ => 0));
  
  for(let i = 1; i <= m; i++) {
    d[i][0] = 1;
  }
  
  for(let j = 1; j <= n; j++) {
    d[0][j] = 1;
  }
  
  for(let i = 1; i <= m; i++){
    for(let j = 1; j <= n; j++){
      d[i][j] = d[i-1][j] + d[i][j-1];
    }
  }
  
  return d[m][n]
}

getXY2(3, 3)

 

 

후기

첫번째 문제를 이해하는게 조금 어려웠다.