다이나믹프로그래밍

[1로 만들기] 정수 X를 입력해, 5 로 나누거나, 3으로 나누거나, 2 로 나누거나, 1을 빼는 연산을 반복하여 1을 갖겠끔 하는 최단 연산의 갯수를 구하시오 도식화를 해보고 느낀 점은 1부터 해서 바텀 업 연산을 해야겠다. 1부터 X값 까지 최단 연산의 갯수를 다 구하면 되지 않을까? 근데 어떻게 연산 갯수 세는걸 어떻게 구현해야할지 모르겠어서 책을 봤다. ( 졸면서 5시간 고민 했는데 점화식이라는 개념이 미쳐 떠오르지 않았다. ) 점화식을 구해서 : \( a_i = min(a_{i-1},a_{i/2},a_{a/3},a_{a/5})+1 \) 점화식을 토대로 소스 코드를 작성한다. def sol(X): # df 테이블 초기화, d[1] = 0 d = [0]*(X+1) for i in range(1,X..

저희 스터디에서 학습 진도에 관해 제가 발표할 차례가 되어 발표 자료를 다음과 같이 만들었는데 그걸 가지고서 다이나믹 프로그래밍을 정리해보고자 합니다. [피보나치 수열을 통한 개념 설명] 효율적인 알고리즘! 이라고 간단히 표현할 수 있겠다. 예시) def fibo(x): if x=1 or x=2: return 1 return fibo(x-1) + fibo(x-2) fibo(6)을 호출해 봅시다. 중복되어 사용되는 코드가 보이시나요? 바로 이러한 중복된 코드 등을 줄임으로써 코드를 효율적으로 만드는걸 DP이라고 합니다. [다이나믹 프로그래밍] 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은 문제에서 구한 정답이, 그것을 포함하는 큰 문제에서 구한 작은 문제에 대한 정답과 같다. 위 두 조건을 만족할..