algorithm
동적 프로그래밍의 응용
수색…
소개
동적 프로그래밍의 기본 아이디어는 복잡한 문제를 몇 가지 작고 간단한 문제로 반복하여 반복하는 것입니다. 반복적으로 계산되는 간단한 하위 문제를 식별 할 수있는 경우 문제에 대한 동적 프로그래밍 방식이 있습니다.
이 주제는 동적 프로그래밍의 응용 프로그램 이라는 제목을 가지므로 동적 프로그래밍 알고리즘을 만드는 프로세스보다는 응용 프로그램에 더 중점을 둡니다.
비고
정의
Memoization - 비싼 함수 호출의 결과를 저장하고 동일한 입력이 다시 발생할 때 캐시 된 결과를 반환하여 컴퓨터 프로그램 속도를 높이는 데 주로 사용되는 최적화 기술입니다.
동적 프로그래밍 (Dynamic Programming) - 복잡한 문제를 간단한 하위 문제 모음으로 분해하여 각 하위 문제를 한 번만 해결하고 솔루션을 저장함으로써 해결합니다.
피보나치 수
피보나치 수 는 동적 계산을위한 주요한 주제입니다. 전통적인 재귀 적 접근 방식은 반복 계산을 많이합니다. 이 예제에서 나는 f(0) = f(1) = 1 의 기본 경우를 사용할 것이다.
다음은 fibonacci(4) 대한 반복적 인 트리 예제입니다. 반복 된 계산을 참고하십시오. 
비 동적 프로그래밍 O(2^n) 런타임 복잡성, O(n) 스택 복잡성
def fibonacci(n):
if n < 2:
return 1
return fibonacci(n-1) + fibonacci(n-2)
이것은 문제를 작성하는 가장 직관적 인 방법입니다. 기 본 케이스 n < 2 도달 할 때까지 fibonacci(n-1) 대한 첫 번째 재귀 분기를 호출 할 때 스택 공간은 O(n) 됩니다.
여기에서 볼 수있는 O(2^n) 런타임 복잡성 증명 : 피보나치 시퀀스의 계산 복잡성 . 주목해야 할 주된 점은 런타임이 지수 함수라는 것입니다. 즉,이 런타임은 모든 후속 용어에 대해 두 배가되며 fibonacci(15) 는 fibonacci(14) 두 배가 소요됩니다.
메모 O(n) 런타임 복잡성, O(n) 공간 복잡성, O(n) 스택 복잡성
memo = []
memo.append(1) # f(1) = 1
memo.append(1) # f(2) = 1
def fibonacci(n):
if len(memo) > n:
return memo[n]
result = fibonacci(n-1) + fibonacci(n-2)
memo.append(result) # f(n) = f(n-1) + f(n-2)
return result
메모 기법을 사용하여 모든 이전 함수 호출로 생각할 수있는 배열을 소개합니다. location memo[n] 은 함수 호출 fibonacci(n) 의 결과입니다. 이것은 우리의 공간 복잡성 거래하지 할 수 있습니다 O(n) A에 대한 O(n) 우리가 더 이상 중복 된 함수 호출을 계산하기 위해 필요로하는 런타임.
반복 동적 프로그래밍 O(n) 런타임 복잡성, O(n) 공간 복잡성, 재귀 적 스택 없음
def fibonacci(n):
memo = [1,1] # f(0) = 1, f(1) = 1
for i in range(2, n+1):
memo.append(memo[i-1] + memo[i-2])
return memo[n]
문제를 핵심 요소로 분해하면 fibonacci(n) 을 계산하기 위해 fibonacci(n-1) 와 fibonacci(n-2) 가 필요하다는 것을 알 수 있습니다. 또한 우리는 기본 케이스가 위에 보이는 재귀 트리의 끝에 나타날 것이라는 것을 알 수 있습니다.
이 정보를 사용하여 이제는 기본 사례에서 시작하여 위쪽으로 작업하여 솔루션을 역으로 계산하는 것이 좋습니다. 이제 계산하기 위해 fibonacci(n) 먼저와를 통해 모든 피보나치 수를 계산 n .
이 주요 이점은 O(n) 런타임을 유지하면서 재귀 적 스택을 제거했기 때문입니다. 불행히도, 우리는 여전히 O(n) 공간 복잡성을 가지지 만 변경 될 수 있습니다.
고급 반복 동적 프로그래밍 O(n) 런타임 복잡성, O(1) 공간 복잡성, 재귀 적 스택 없음
def fibonacci(n):
memo = [1,1] # f(1) = 1, f(2) = 1
for i in range (2, n):
memo[i%2] = memo[0] + memo[1]
return memo[n%2]
위에서 언급했듯이 반복적 인 동적 프로그래밍 접근법은 기본 사례에서 출발하여 최종 결과에 도달합니다. 공간의 복잡성을 O(1) (상수)에 도달하기 위해 만드는 핵심 관측은 재귀 적 스택에 대해 수행 한 것과 동일한 관찰이다. 우리는 fibonacci(n-1) 와 fibonacci(n-2) 만 빌드하면된다. fibonacci(n) . 즉, 반복의 어느 시점에서든 fibonacci(n-1) 및 fibonacci(n-2) 에 대한 결과 만 저장하면됩니다.
이 마지막 2 개의 결과를 저장하기 위해 크기 2의 배열을 사용하고 i % 2 를 사용하여 할당 할 색인을 플립합니다 (예 : 0, 1, 0, 1, 0, 1, ..., i % 2 .
추가가 교환 가능하다는 것을 알기 때문에 ( 5 + 6 = 11 및 6 + 5 == 11 ) 배열의 두 인덱스를 모두 추가합니다. 그 결과는 두 지점 중 오래된 것에 할당됩니다 ( i % 2 로 표시됨). 최종 결과는 n%2 위치에 저장됩니다.
노트
- 함수 호출에 대한 응답의 캐시를 구축 할 때 반복적으로 큰 계산을 수행하는 함수에 대해 반복적 인 메모 솔루션을 제안하는 것이 가장 중요 할 수 있으며 이후 호출은 다음과 같은 경우
O(1)일 수 있습니다. 그것은 이미 계산되었습니다.