Gopythor

이미 계산된 결과를 메모리에 저장하면 다음과 같이 색칠된 노드만 처리할 것을 기대할 수 있습니다. 실제로 호출되는 함수에 대해서만 확인해보면 다음과 같이 방문합니다. 피보나치 수열: 메모이제이션 동작 분석 메모이제이션을 이용하는 경우 피보나치 수열 함수의 시간 복잡도는 O(N)입니다. d = [0] * 100 def fibo(x): print('f(' + str(x) + ')', end=' ') if x == 1 or x == 2: return 1 if d[x] != 0: return d[x] d[x] = fibo(x - 1) + fibo(x - 2) return d[x] fibo(6) # f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(4)

Python/이코테 2022. 6. 24. 03:02

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 d = [0] * 100 # 첫번째 피보나치 수와 두번째 피보나치 수는 1 d[1] = 1 d[2] = 2 n = 99 # 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍) for i in range(3, n + 1): d[i] = d[i - 1] + d[i - 2] #218922995834555169026

Python/이코테 2022. 6. 24. 02:53

# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화 d = [0] * 100 # 피보나치 함수(Fibonacci Function)를 재귀함수로 구현(탑다운 다이나믹 프로그래밍) def fibo(x): # 종료 조건(1 혹은 2일 때 1을 반환) if x == 1 or x == 2: return 1 # 이미 계산한 적 있는 문제라면 그대로 반환 if d[x] != 0: return d[x] # 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환 d[x] = fibo(x - 1) + fibo(x - 2) return d[x] print(fibo(99)) #218922995834555169026

Python/이코테 2022. 6. 24. 02:43

메모이제이션 (Memoization) 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나입니다. (탑다운 방식=하향식) 한 번 계산한 결과를 메모리 공간에 메모하는 기법입니다. 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옵니다. 값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 합니다. 탑다운 vs 보텀업 탑다운(메모이제이션) 방식은 하향식이라고도 하며 보텀업 방식은 상향식이라고도 합니다. 다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식입니다. 결과 저장용 리스트는 DP 테이블이라고 부릅니다. 엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미합니다. 따라서 메모이제이션은 다이나믹 프로그래밍에 국한된 개념은 아닙니다. 한 번 계산된 결과를..

Python/이코테 2022. 6. 24. 02:27

피보나치 수열은 다음과 같은 형태의 수열이며, 다이나믹 프로그래밍으로 효과적으로 계산할 수 있습니다. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 점화식이란 인접한 항들 사이의 관계식을 의미합니다. 피보나치 수열을 점화식으로 표현하면 다음과 같습니다. a(n) = a(n-1) + a(n-2) a(1) = 1, a(2) = 1 피보나치 수열이 계산되는 과정은 다음과 같이 표현할 수 있습니다. 프로그래밍에서는 이러한 수열을 배열이나 리스트를 이용해 표현합니다. 피보나치 수열 피보나치 수열이 계산되는 과정은 다음과 같이 표현할 수 있음 n번째 피보나치 수를 f(n)라고 할 때 4번째 피보나치 수 f(4)를 구하는 과정은 다음과 같음 피보나치 수열: 단순 재귀 소스코드 (Pytho..

Python/이코테 2022. 6. 22. 23:53

다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법입니다. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 합니다. 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운과 보텀업)으로 구성됩니다. 다이나믹 프로그래밍은 동적 계획법이라고도 부릅니다. 일반적인 프로그래밍 분야에서의 동적(Dynamic)이란 어떤 의미를 가질까요? 자료구조에서 동적 할당(Dynamic Allocation)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미 반면에 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미 없이 사용된 단어입니다. 다이나믹 프로그래밍은 문제가 다음의 조건을 만족할 떄 사용할 수 있습니다. 최적 부..

Python/이코테 2022. 6. 22. 22:49

N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요. 예를 들어 수열 {1,1,2,2,2,2,3}이 있을 때 x = 2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력합니다. 단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받습니다. 정렬된 배열에서 특정 수의 개수 구하기: 문제 해결 아이디어 내코드 from bisect import bisect_left, bisect_right N, x = map(int, input().split()) arr = list(map(int,input().split())) def sorted(arr, target): left = bisect_left(a..

Python/이코테 2022. 6. 20. 02:57

오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했습니다. 오늘은 떡볶이 떡을 만드는 날입니다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않습니다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰줍니다. 절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단합니다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않습니다. 예를 들어 높이가 19, 14, 10, 17cm 인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것입니다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm입니다. 손님은 6cm만큼의 길이를 가져갑니다. 손님이 왔을 때 요청한 총 길이가 M일 때..

Python/이코테 2022. 6. 20. 01:52