두시간 알고리즘 - 8일차, 다이나믹 프로그래믹 완전 정복 Chapter1,2 예제 JavaScript화 하기

http://m.yes24.com/goods/detail/79257722

다이내믹 프로그래밍 완전 정복 - YES24

다이나믹프로그래밍 완전정복 책을 공부하기시작했다!

알고리즘쪽에서 늘수있을가 의심이되기까지하는 분야가 다이나믹 프로그래밍이라 이책으로 진짜 제발 이게 뭔지 이해를 했으면 좋겠다. 

 

 

Chapter1. 재귀 호출의 이해

재귀호출 문제를 풀때는 항상 뭔가가 찜찜한 마음으로 푸는데, 이 책에서 쉽게 표현하기로는

 

문제의 풀이법을 직관적으로 정리하기 어려울때 문제의 크기를 줄여놓고, 큰 문제와 작은 문제의 관계 속에서 문제의 풀이법을 찾아보는 방식

이라고 한다. 수열을 공부할 때 점화식을 표현했던 것처럼(수열의 귀납적 정의), 컴퓨터에서는 이렇게 귀납적으로 정의하는것을 재귀(recursion)이라고 한다. 

 

아래는 해당 챕터의 예제 코드 및 연습 문제를 JavaScript로 푼 것이다. 

// 예제: 1에서 n까지 양의 정수의 합을 계산하기
const sum = (n) => {
  if(n <= 0){
    return 0;
  }
  if(n === 1){
    return 1;
  }
  return n + sum(n-1);
}

sum(55);

// 연습 문제 1-1
// 일반적으로
const fact1 = (n) => {
  let answer = 1;
  for(let i = 1; i <= n; i++){
    answer *= i;
  }
  return answer;
}
fact1(10);
// 재귀함수
const fact2 = (n) => {
  if(n === 1){
    return 1;
  }
  return n * fact2(n-1);
}
fact2(10);


// 연습 문제 1-2
const accSum = (array, index) => {
  if(index <= 0){
    return array;
  }
  array[index] += accSum(array, index-1)[index-1];
  return array;
}

accSum([1,2,3,4,5,6], 5)

// 코드 1-5
const power = (x, n) => {
  if(n === 0 || x === 1){
    return 1;
  }
  if(n === 1){
    return x;
  }
  return x * power(x, n-1);
}

// 코드 1-6 하노이탑
// S: 출발지, D: 목적지, E: 임시, n개의 원반
const towerOfHanoi = (s, d, e, n) => {
  if(n <= 0){
    return;
  }
  towerOfHanoi(s, e, d, n-1);
  console.log(`${n}번 원반을 ${s}에서 ${d}로 옮깁니다`);
  towerOfHanoi(e, d, s, n-1);
}

towerOfHanoi('s', 'd', 'e', 3);

// 코드 1-7 선생 재귀와 후행 재귀
const arr = [1,2,3,4,5];
// 선행 재귀
const traverse1 = (arr, index) => {
  if(index < arr.length){
    traverse1(arr, index+1);
    console.log(arr[index]);
  }
}
traverse1(arr, 0);
// 후행 재귀, 이건 for loop으로 작성이 쉽다
const traverse2 = (arr, index) => {
  if(index < arr.length){
    console.log(arr[index]);
    traverse2(arr, index+1);
  }
}
traverse2(arr, 0);

// 재귀
const tree = {
  0: {
    value: 0, 
    left: 1, 
    right: 2
  }, 
  1: {
    value: 1, 
    left: 3, 
    right: 4
  },
  2: {
    value: 2, 
    left: 5, 
    right: 6
  }, 
  3: {
    value: 3, 
    left: null, 
    right: null,
  },
  4: {
    value: 4, 
    left: null, 
    right: null,
  },
  5: {
    value: 5, 
    left: null, 
    right: null,
  },
  6: {
    value: 6, 
    left: null, 
    right: null,
  }
}

const inOrder = (tree, index) => {
  if(tree[index].left){
    // 있을때만 탐색
    inOrder(tree, tree[index].left);
  }
  
  console.log(tree[index].value);
  
  if(tree[index].right){
    // 있을때만 탐색
     inOrder(tree, tree[index].right);
  }
}

inOrder(tree, 0);

// 재귀를 사용한 문제 해결
// 버블 소트
const bubbleSort = (arr, n) => {
  if(n === 1) return;
  
  for(let j = 0; j < n-1; j++){
    if(arr[j] > arr[j+1]){
      let temp = arr[j];
      arr[j] = arr[j+1];
      arr[j+1] = temp;
    }
  }
  
  bubbleSort(arr, n-1);
}

const bArr = [9, 6, 2, 12, 11, 9, 3, 7];
bubbleSort(bArr, bArr.length);
console.log(bArr);

// 연습문제 1-3
const printTable = (n, i) => {
  if(i <= 0) return;
  
  printTable(n, i-1); // 먼저 처리하고
  console.log(`${n} * ${i} = ${n*i}`); // 다음에 출력
}

printTable(2, 15);

 

 

Chapter2. 재귀 호출의 특징과 메모 전략

재귀 접근 방식은 두가지 특징을 가지고 있다고 한다. 최적의 하위 구조, 하위 문제의 반복계산이다. 이때 하위 문제가 반복계산되는건 Memoization으로 해결 할 수 있다. 

 

 

최적의 하위 구조 Optimal substructure

n에 대해서 해결해야하는 문제가 있을때, n미만개의 문제를 해결할때 사용한 방법을 가져다 쓰는게 가장 효율적인 구조이다. 

어떤 문제의 풀이법을 같은 문제의 더 작은 문제로 정의하는게 최적의 풀이법이라면 이문제는 최적의 하위 구조를 가졌다고 합니다. 최적의 하위구조를 가진 문제는 다이내믹 프로그래밍 방법을 적용하기 좋은 문제입니다. p62, 다이나믹 프로그래밍 완전 정복

 

다이나믹 프로그래밍이란?

이렇게 최적의 하위구조를 풀기 위해서 재귀 접근 방법을 쓸때, 메모리나 시간쪽에서 효율적으로 할때 다이나믹 프로그래밍 방법론을 통해서 접근한다. 풀때 점화식을 작성하거나, 최적의 하위구조를 정의하는 일부터 해야한다. 재귀방식으로 풀수가 없다면 다이나믹을 적용하기도 어렵다. 

 

이 책의 저자가 제안하는 방식은, 다이나믹 프로그래밍과 관련된 문제가 주어지면, 점화식이나, 재귀 방식을 사용해서 문제를 해결한다음, 다이나믹 프로그래밍의 관점인 상향식으로 접근을하라고 한다. 

 

 

하위 문제의 반복 계산

피보나치 수열같은 문제는 사실 어떤 작은 문제 하나를 계속 접근한다. 그 작은 문제가 계산할때마다 달라지는 것도 아닌데. 

 

// 코드 2-4, 메모 전략을 이용한 피보나치 계산, 
const memo = new Map();

const fibonacci = (n) => {
  if(memo.has(n))
      return memo.get(n);
  
  if(n===1 || n === 2){
    memo.set(n, 1);
  }else{
    memo.set(n, fibonacci(n-1) + fibonacci(n-2));
  }
  
  return memo.get(n);
}


fibonacci(20);
console.log(memo);

// 코드 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);
console.log(memo_cost)

 

후기

오랜만에 본 정말 좋은 책이다. 정말 재귀와 다이나믹프로그래밍을 제대로 이해하는 날이 올련강.