다이나믹 프로그래밍 Dynamic Programming

다이나믹 프로그래밍 Dynamic Programming 

Dynamic Programming의 개념

• 큰 문제를 작은 문제로 나누어 문제를 푸는 기법
• divide and conquer 기법과 달리 작은 문제의 중복이 발생하지 않는다.
• 분할된 모든 작은 문제들은 한번만 풀어야 하기 때문에 작은 문제의 정답은 구한 뒤 메모해 둔다. 그리고 큰 문제를 풀다가 동일한 작은 문제가 나타나면 앞에 메모한 작은 문제의 결과값을 이용한다.

Dynamic Programming의 조건

• 작은 문제가 반복적으로 일어나는 경우
• 같은 문제를 구할 때마다 결과값이 같은 경우

---

메모이제이션 Memoization 

• 한번 계산한 작은 문제의 결과값을 저장해두는 것
• Bottom-up 구현

def fibonacci_bottom_up(n):
	if n <= 1:
		return n;
	first = 0
	second = 1
	for i in range(0, n-1):
		next = first + second
		first = second
		seconde = next
	return next

if __name__ == '__main__':
	n = int(sys.stdin.readline())
	print(fibonacci_bottom_up(n))

• Top-down 구현 

def fibonacci_top_down(n):
	if memo[n] > 0 :
		return memo[n]
	if n <= 1:
		memo[n] = n
		return memo[n]
	else: 
		memo[n] = fibonacci_top_down(n-1) + fibonacci_top_down(n-2)
		return memo[n]

if __name__ == '__main__':
		memo = [0 for i in range(1000)]
		n = int(sys.stdin.readline())
		print(fibonacci_top_down(n))

---

최장 공통 부분 수열 문제 LCS 

• 두 개의 문자열에서 순서대로 겹치는 문자가 최대 몇 개인지 구하는 문제

• example

  x = 'ABCBDAB'

  y = 'BDCABA'

  LCS = z = 'BCAB' or 'BDAB' or 'BCBA'

  LCS(x,y) = 4

  ** if x == y :

  LCS(x,y) = max(LCS(x, y-1), LCS(x -1, y))

function LCS(x, y) {
  var i = x.length;
  var j = y.length;
  var result = [];
  for (var k = 0; k <= i; k++) {
    if (!result[k]) {
      result[k] = []; // 이전 계산 값 저장 공간
    }
  }
  for (k = 0; k <= i; k++) {
    for (var l = 0; l <= j; l++) {
      console.log(k, l);
      if (k === 0 || l === 0) { // 베이스 값 설정
        result[k][l] = 0;
      } else if (x[k - 1] === y[l - 1]) { // 마지막 두 문자 비교, 같으면
        result[k][l] = result[k - 1][l - 1] + 1;
      } else { // 마지막 두 문자가 다르면
        result[k][l] = Math.max(result[k - 1][l], result[k][l - 1]);
      }
    }
  }
  return result[i][j];
}
LCS('ABCBDAB', 'BDCABA'); // 4

---

References

• https://www.zerocho.com/category/Algorithm/post/584b979a580277001862f182