아이테킨의 끄적끄적

피보나치 수열을 구하는 대표적은 다이나믹 프로그래밍 문제이다. 그러나 이번 문제는 단순히 문제를 해결하는 것 뿐만 아니라 더 빨리 효율적으로 풀 수 있는 알고리즘을 물어보고 있다. 문제의 답은 반복문 또는 메모이제이션을 이용해서 풀면 된다. (메모이제이션을 이용한 코드는 아래 있다.) # 반복문으로 푼 피보나치 n = int(input()) dp = [0]*100 dp[1] = 1 for i in range(2,n+1): dp[i] = dp[i-1] + dp[i-2] print(dp[n]) 이번 기회에 피보나치 수열을 구하는데 사용되는 3가지 방법에 대해서 정리해보았다. 반복문, 재귀, 메모이제이션 총 세가지 방법으로 피보나치 수열을 풀 수 있지만 각각 시간복잡도, 메모리를 사용하는 정도가 다르다. 1...

메모이제이션을 이용해서 풀어야 하는 DP 문제다. 3차원 리스트를 이용하면 쉽게 풀 수 있다. # 9184 - 신나는 함수 실행 dp = [[[0]*21 for _ in range(21)] for __ in range(21)] def w(a, b, c) : print(dp) if a20 : return w(20, 20, 20) if dp[a][b][c]: return dp[a][b][c] if a

피보나치 함수를 구하는 문제이다 보통 피보나치 수열은 재귀함수를 이용해서 구할 수 있다. def fibo(x): if x == 1 or x == 2: return 1 else: return fibo(x-1) + fibo(x-2) 이런 식으로 구할 수 있는데 문제는 숫자가 조금만 커지게되면 연산횟수가 급격하게 증가하고 그에 따라서 속도도 엄청 느려지게 된다. 이런 문제를 메모이제이션(재귀함수이용) 또는 반복문을 이용해서 해결할 수 있다. 메모이제이션은 이미 한번 연산을 했던 값은 따로 저장해뒀다가 필요할때마다 찾아서 쓴다는 아이디어다. 말 그대로 따로 메모해둔다고 생각하면 된다. 반복문을 이용하는 방법은 작은 문제부터 하나하나씩 풀어나가는 방법이다. 결론적으로는 선형시간의 시간복잡도를 갖는다. 코드로 살펴..