Algorithm/DP

BOJ#1463 1로 만들기

밤이2209 2016. 11. 21. 14:28

BOJ#1463 1로 만들기


* 문제

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


* 풀이

동적 계획법 (Dynamic Programming) 기초 문제입니다.


* 동적 계획법 (Dynamic Programming)


 : 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다.

 : 문제를 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종 목표를 구한다.

 : 하위 문제들의 해결책을 저장하여 이후 같은 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다.


* 메모이제이션 (Memoization)


 : 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 반복 계산을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다.

 : 동적 계획법의 핵심이 되는 기술이다.

 


(예제) 피보나치 수열


보통 피보나치 수열을 구하는 함수는 다음과 같이 작성한다.

function fib(n)
 if n = 0
  return 0
 else if n=1
  return 1
 else
  return fib(n-1) + fib(n-2)

이때, fib(5)를 구한다고 한다면 계산은 다음과 같이 이루어진다.

  1. fib(5)
  2. fib(4) + fib(3)
  3. (fib(3) + fib(2)) + (fib(2) + fib(1))
  4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
  5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

여기에서 세 번째 줄의 fib(2)가 중복되어 계산되고, 이것은 전체적인 계산 속도를 떨어뜨린다. 이 알고리즘의 시간 복잡도는 지수 함수가 된다.

여기에서 각 함수의 계산값을 저장하는 객체 m을 추가하면, 이 알고리즘은 다음과 같이 바뀐다.

var m := map(0 → 1, 1 → 1)
function fib(n)
 if n not in keys(m)
  m[n] := fib(n-1) + fib(n-2)
 return m[n]

이렇게 각 계산값을 저장하면, 중복 계산이 줄어들고 시간 복잡도는 O(n)이 된다.


출처 : https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95


위의 동적계획법을 적용해보자.


정수 X가 N이고, dp[N]을 'N을 1로 만들기 위해 필요한 연산의 횟수' 라고 했을 때

dp[N] = min(dp[N-1] + 1, dp[N/3] + 1, dp[N/2] + 1) 이라고 할 수 있다.


즉, dp[N] 은 아래 3가지 하위 문제로 나눌 수 있다는 것이다.

  1) dp[N-1] + 1

  2) if (N%3 == 0) dp[N/3] + 1

  3) if (N%2 == 0) dp[N/2] + 1







* 나의 코드

https://github.com/stack07142/BOJ/tree/master/BOJ%231463_SetTo1

'Algorithm > DP' 카테고리의 다른 글

BOJ#11053 가장 긴 증가하는 부분 수열 (LIS)  (0) 2016.12.06
BOJ#2156 포도주 시식  (0) 2016.11.25
BOJ#9465 스티커  (3) 2016.11.24
BOJ#10844 쉬운 계단 수  (0) 2016.11.22
BOJ#11726 2xn 타일링  (0) 2016.11.21