dynamic programming3 [백준/파이썬3/1003] 피보나치 함수 피보나치 함수 문제 다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다. int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); } } fibonacci(3)을 호출하면 다음과 같은 일이 일어난다. fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다. fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다. 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다. fibona.. 2020. 1. 10. [백준/파이썬3/1463] 1로 만들기 풀이 x = int(input()) dp = [0 for _ in range(x+1)] dp[1] = 0 for i in range(2, x+1): dp[i] = dp[i-1]+1 if not i%2 and dp[i]>dp[i//2]+1: dp[i] = dp[i//2]+1 if not i%3 and dp[i]>dp[i//3]+1: dp[i] = dp[i//3]+1 print (dp[x]) 우선, Dp문제 이해가 안갔다. 유튜브 영상 몇개 보면서 감이 오는거 같긴했는데...... 머리가 평균이하인듯 ;ㅅ; 그래서 아나콘다에서 Spyder라는 툴을 이용해서 배열에 들어가는 값을 시각화 해보았다. 이해가 안가신다면 코드를 빤히 10분만 쳐다보시면 뭔가가 보일 것이다. 우선 index의 숫자를 보시면 예를 들어.. 2019. 12. 4. Dynamic programming 동적 계획법 엄청 예전에 프로그래밍 수업을 들을때 피보나치 수열 값 표시하면서 분명히 들어본거 같은데, 그 당시만해도 딱히 프로그래밍에 관심이 없어서 당시에는 아 이런게 있구나하고 넘어갔지만, 이제서야 동적계획의 Dynamic programming의 중요성을 새삼 느꼈습니다. 아래 코드를 보시면, A = int(input()) def fibo(x): if x==1: return 1 if x==2: return 1 return fibo(x-1)+fibo(x-2) print(fibo(A)) 피보나치 수열의 수를 나타내는 코드입니다. 그런데 이 같은 경우에는 특정 수를 구하기 위해서 그전의 수를 모두 다 찾아야합니다. 예를 들어서 4를 찾고 싶으면 모든 수를 다 계산해서 2와 3을 더해야하고 5를 찾고 싶다면 아래 빨간색.. 2019. 11. 26. 이전 1 다음
