11,719 판독값

동적 프로그래밍을 이해하여 효과적으로 사용할 수 있습니다.

~에 의해 inDrive.Tech11m2023/09/04

너무 오래; 읽다

이 기사는 프로덕션 개발과 관련이 없지만 프로그래밍과 관련이 있습니다. DP(동적 프로그래밍)와 이전 계산 경험을 효과적으로 활용하는 방법에 대해 논의하겠습니다. 나는 당신이 그것을 흥미로울 것이라고 생각합니다.

People Mentioned

featured image - 동적 프로그래밍을 이해하여 효과적으로 사용할 수 있습니다.

동적 프로그래밍 소개

동적 프로그래밍이라는 용어는 1950년대 미국의 유명한 수학자이자 컴퓨터 기술 분야의 선도적인 전문가 중 한 명인 Richard Bellman이 처음 사용했습니다 . DP(동적 프로그래밍)는 복잡한 작업을 더 작은 하위 문제로 나누어 해결하는 방법입니다.

DP가 해결할 수 있는 문제의 종류는 두 가지 기준을 충족해야 합니다.

1. 최적의 하부구조 . 동적 프로그래밍은 작은 하위 문제에 대한 솔루션을 사용하여 초기 문제를 해결할 수 있음을 의미합니다. 최적의 하부 구조는 "분할 정복" 패러다임의 주요 특징입니다.

구현의 전형적인 예는 병합 정렬 알고리즘입니다. 이 알고리즘에서는 문제를 가장 간단한 하위 문제(크기 1 배열)로 재귀적으로 분류한 후 각 문제를 기반으로 계산을 수행합니다. 결과는 초기 레이어가 달성될 때까지 다음 레이어(더 큰 하위 문제)를 해결하는 데 사용됩니다.

2. 중복되는 하위 문제 . 컴퓨터 과학에서는 문제를 여러 번 재사용할 수 있는 하위 문제로 나눌 수 있는 경우 문제에 중첩된 하위 문제가 있다고 말합니다. 즉, 동일한 입력 데이터와 동일한 결과로 동일한 코드를 실행하는 것입니다. 이 문제의 전형적인 예는 아래에서 살펴보게 될 피보나치 수열의 N번째 요소 계산입니다.

DP는 Divide and Conquer 패러다임을 사용하는 특별한 경우이거나 그보다 더 복잡한 버전이라고 말할 수 있습니다. 이 패턴은 다양한 조합이 계산되는 조합론과 관련된 작업을 해결하는 데 매우 적합하지만 요소의 N개 수량은 단조롭고 동일한 경우가 많습니다.

최적의 하부 구조 문제와 중첩되는 하위 문제의 경우 무차별 접근 방식을 적용하면 수많은 반복 계산과 연산이 발생합니다. DP는 메모화와 표 작성이라는 두 가지 주요 접근 방식을 사용하여 솔루션을 최적화하고 계산이 두 배로 늘어나는 것을 방지하는 데 도움이 됩니다.

1. 메모이제이션(하향식 접근 방식)은 재귀를 통해 구현됩니다. 작업은 더 작은 하위 문제로 분류되고, 그 결과는 메모리에 입력되어 반복 사용을 통해 원래 문제를 해결하기 위해 결합됩니다.

단점: 이 접근 방식은 재귀 메서드 호출을 통해 스택 메모리를 사용합니다.
장점: DP 작업에 대한 유연성.

2. 표 작성(상향식 접근 방식)은 반복 방법을 사용하여 구현됩니다. 가장 작은 문제부터 초기 문제까지 하위 문제가 연속해서 반복적으로 계산됩니다.

단점: 적용 범위가 제한적입니다. 이 접근 방식을 사용하려면 하위 문제의 전체 순서에 대한 초기 이해가 필요합니다. 그러나 일부 문제에서는 이것이 가능하지 않습니다.
장점: 모든 것이 단일 함수 내에서 실행되므로 메모리를 효율적으로 사용합니다.

이론은 지루하고 이해하기 어려울 수도 있습니다. 몇 가지 예를 살펴보겠습니다.

문제: 피보나치 수열

DP의 전형적인 예는 피보나치 수열에서 N번째 요소를 계산하는 것입니다. 여기서 각 요소는 이전 두 요소의 합이고 첫 번째 요소와 두 번째 요소는 0과 1과 같습니다.

가설에 따라, 하나의 값을 계산하려면 이전 값을 찾아야 하므로 처음에는 최적의 하위 구조의 특성에 초점을 맞춥니다. 이전 값을 계산하려면 그 이전에 나온 값을 찾아야 합니다. 겹치는 하위 작업의 특성은 아래 다이어그램에 설명되어 있습니다.

이 작업을 위해 다음 세 가지 사례를 살펴보겠습니다.

간단한 접근 방식: 단점은 무엇입니까?
메모이제이션을 활용한 최적화된 솔루션
도표화를 이용한 최적화된 솔루션

간단한/무차별 접근 방식

가장 먼저 생각할 수 있는 것은 재귀를 입력하고 앞의 두 요소를 합산하여 그 결과를 제공하는 것입니다.

 /** * Straightforward(Brute force) approach */ fun fibBruteForce(n: Int): Int { return when (n) { 1 -> 0 2 -> 1 else -> fibBruteForce(n - 1) + fibBruteForce(n - 2) } }

아래 화면에서는 시퀀스의 다섯 번째 요소를 계산하기 위한 함수 호출 스택을 볼 수 있습니다.

fib(1) 함수는 5번 호출되고 fib(2) 3번 호출된다는 점에 유의하십시오. 하나의 시그니처와 동일한 매개변수를 가진 함수는 반복적으로 실행되어 동일한 작업을 수행합니다. N 수가 증가하면 트리가 선형이 아닌 기하급수적으로 증가하므로 계산이 엄청나게 중복됩니다.

수학 분석:

시간 복잡도: O(2^n),

공간 복잡도: O(n) -> 재귀 트리의 최대 깊이에 비례합니다. 이는 암시적 함수 호출 스택에 존재할 수 있는 요소의 최대 개수이기 때문입니다.

결과: 이 접근 방식은 매우 비효율적입니다. 예를 들어 30번째 요소를 계산하려면 1,073,741,824번의 연산이 필요합니다.

메모화(하향식 접근 방식)

이 접근 방식에서 구현은 메모리 할당을 제외하면 앞서 언급한 "무차별 대입" 솔루션과 크게 다르지 않습니다. 스택에서 완성된 fib() 함수의 계산 결과를 수집하는 변수 메모라고 하겠습니다.

정수 배열을 갖고 이를 인덱스로 참조하는 것만으로도 충분했지만 개념적 명확성을 위해 해시 맵이 생성되었습니다.

 /** * Memoization(Top-down) approach */ val memo = HashMap<Int, Int>().apply { this[1] = 0 this[2] = 1 } fun fibMemo(n: Int): Int { if (!memo.containsKey(n)) { val result = fibMemo(n - 1) + fibMemo(n - 2) memo[n] = result } return memo[n]!! }

함수 호출 스택에 다시 초점을 맞춰 보겠습니다.

메모에 결과를 기록하는 첫 번째 완성된 함수는 강조 표시된 fib(2) 입니다. 강조 표시된 fib(3) 에 제어권을 반환합니다.
강조 표시된 fib(3) fib(2) 및 fib(1) 호출의 결과를 합산한 후 해당 값을 찾아 메모에 솔루션을 입력하고 제어권을 fib(4) 에 반환합니다.
이전 경험을 재사용할 수 있는 단계에 도달했습니다. 제어권이 fib(4) 로 반환되면 fib(2) 호출이 그 차례를 기다립니다. fib(2) 는 ( fib(1) + fib(0) )을 호출하는 대신 메모에서 완성된 솔루션 전체를 사용하고 즉시 반환합니다.
fib(4) 는 계산되어 fib(5) 에 제어권을 반환합니다. fib(5) 는 fib(3) 만 실행하면 됩니다. 마지막 비유에서 fib(3) 계산 없이 메모의 값을 즉시 반환합니다.

함수 호출 및 계산 횟수가 감소하는 것을 볼 수 있습니다. 또한 N이 증가하면 감소량이 기하급수적으로 줄어듭니다.

수학 분석:

시간 복잡도: O(n)

공간 복잡도: O(n)

결과: 점근적 복잡성에는 분명한 차이가 있습니다. 이 접근 방식은 기본 솔루션과 비교하여 시간이 선형으로 줄어들었고 메모리가 증가하지 않았습니다.

표 작성(상향식 접근 방식)

위에서 언급했듯이 이 접근 방식에는 더 작은 하위 문제에서 더 큰 하위 문제로 반복 계산이 포함됩니다. 피보나치의 경우 가장 작은 "하위 문제"는 수열의 첫 번째 요소와 두 번째 요소인 각각 0과 1입니다.

우리는 fib(n) = fib(n-1) + fib(n-2) 공식으로 표현되는 요소들이 서로 어떻게 관련되어 있는지 잘 알고 있습니다. 우리는 이전 요소를 알고 있기 때문에 다음 요소, 그 다음 요소 등을 쉽게 해결할 수 있습니다.

우리가 알고 있는 값을 합산하면 다음 요소를 찾을 수 있습니다. 원하는 값을 찾을 때까지 이 작업을 주기적으로 구현합니다.

 /** * Tabulation(Bottom-up) approach fun fibTab(n: Int): Int { var element = 0 var nextElement = 1 for (i in 2 until n) { val newNext = element + nextElement element = nextElement nextElement = newNext } return nextElement }

수학 분석:

시간 복잡도: O(n)

공간 복잡도: O(1)

결과: 이 접근 방식은 속도 측면에서 메모와 마찬가지로 효과적이지만 일정한 양의 메모리를 사용합니다.

문제: 고유한 이진 트리

더 복잡한 문제를 살펴보겠습니다. N 노드에서 생성될 수 있는 구조적으로 고유한 모든 이진 트리의 수를 찾아야 합니다.

이진 트리는 각 노드가 2개 이하의 자손을 갖는 계층적 데이터 구조입니다. 일반적으로 첫 번째 노드는 부모 노드라고 불리며 두 개의 자식, 즉 왼쪽 자식과 오른쪽 자식이 있습니다.

N = 3에 대한 해를 찾아야 한다고 가정해 봅시다. 3개의 노드에 대해 구조적으로 고유한 5개의 트리가 있습니다. 머리로는 셀 수 있지만 N이 증가하면 변형이 엄청나게 확대되어 머리로 시각화하는 것이 불가능합니다.

이 작업은 조합론에 기인할 수 있습니다. 어떤 조합이 형성될 수 있는지, 그리고 그 조합의 형성 패턴을 어떻게 찾을 수 있는지 알아봅시다.

각 트리는 최상위 노드(트리의 정점)에서 시작됩니다. 그러면 트리가 깊이 확장됩니다.
화면에 표시된 대로 각 노드는 새로운 하위 트리(하위 트리)의 시작입니다. 왼쪽 하위 트리는 녹색으로 표시되고 오른쪽은 빨간색으로 표시됩니다. 각각은 자신의 꼭지점을 가지고 있습니다.

개념적 수준에서 N = 6인 작업의 예를 살펴보겠습니다. 계산 함수를 numOfUniqueTrees(n: Int) 라고 부르겠습니다.

이 예에서는 6개의 노드가 제공되며, 그 중 하나는 앞서 언급한 원리에 따라 트리의 정점을 형성하고 다른 5개는 나머지를 형성합니다.

이제부터 나머지 노드와 상호작용합니다. 이는 다양한 방법으로 수행될 수 있습니다. 예를 들어 5개 노드를 모두 사용하여 왼쪽 하위 트리를 형성하거나 5개 노드를 모두 오른쪽 하위 트리로 보냅니다. 또는 노드를 왼쪽에 2개, 오른쪽에 3개(아래 화면 참조)로 나누어 이러한 변형의 수가 제한됩니다.

numOfUniqueTrees(6) 결과를 얻으려면 노드를 배포하기 위한 모든 변형을 고려해야 합니다. 표에 나와 있습니다.

표는 노드의 6가지 다른 분포를 보여줍니다. 각 분포마다 몇 개의 고유 트리를 생성할 수 있는지 찾아 이를 합산하면 최종 결과를 얻을 수 있습니다.

배포할 고유 트리 수를 찾는 방법은 무엇입니까?

왼쪽 노드와 오른쪽 노드(표의 왼쪽 및 오른쪽 열)라는 두 개의 매개변수가 있습니다.

결과는 numOfUniqueTrees(leftNodes) * numOfUniqueTrees(rightNodes) 와 같습니다 .

왜? 왼쪽에는 X개의 고유한 나무가 있고, 각각에 대해 오른쪽에는 Y개의 고유한 나무 변형을 배치할 수 있습니다. 결과를 얻기 위해 이를 곱합니다.

그럼 첫 번째 분포의 변형을 찾아보겠습니다(왼쪽 5개, 오른쪽 0개).

numOfUniqueTrees(5) * numOfUniqueTrees(0) , 오른쪽에 노드가 없기 때문입니다. 결과는 numOfUniqueTrees(5) 입니다. 즉, 오른쪽이 상수인 왼쪽의 고유 하위 트리 수입니다.

numOfUniqueTrees(5) 계산 중.

이제 가장 작은 하위 문제가 생겼습니다. 우리는 더 큰 규모의 작업과 마찬가지로 작업을 수행할 것입니다. 이 단계에서 DP 작업의 특징은 최적의 하위 구조, 재귀적 동작이라는 것이 분명합니다.

하나의 노드(녹색 노드)가 정점으로 전송됩니다. 나머지(4개) 노드는 이전 경험(4:0), (3:1), (2:2), (1:3), (0:4)과 유사한 방식으로 배포합니다.

첫 번째 분포(4:0)를 계산합니다. 이전 비유에서는 numOfUniqueTrees(4) * numOfUniqueTrees(0) -> numOfUniqueTrees(4) 같습니다.

numOfUniqueTrees(4) 계산 중. 정점에 노드를 할당하면 3개가 남습니다.

분포(3:0), (2:1), (1:2), (0:3).

2개의 노드에는 1-1개의 고유한 이진 트리가 두 개만 있습니다. 이전에 우리는 세 개의 노드에 대해 고유한 이진 트리의 5가지 변형이 있다는 것을 이미 언급했습니다.

결과적으로 — 분포(3:0), (0:3)은 5, (2:1), (1:2) — 2와 같습니다. 5 + 2 + 2 + 5를 합하면 14가 됩니다. numOfUniqueTrees(4) = 14.

메모한 경험에 따라 계산 결과를 변수 메모에 입력해 봅시다. 4개의 노드에 대한 변형을 찾아야 할 때마다 이를 다시 계산하지 않고 이전 경험을 재사용합니다.

다시 계산(5:0)으로 돌아가 보겠습니다. 이는 분포(4:0), (3:1), (2:2), (1:3), (0:4)의 합과 같습니다. 우리는 (4:0) = 14라는 것을 알고 있습니다. 메모로 넘어가면, (3:1) = 5, (2:2) = 4 (왼쪽 변주 2개 * 오른쪽 2개), (1:3) = 5, (0:4) = 14. 이를 합산하면 42, numOfUniqueTrees(5) = 42가 됩니다.

분포의 합과 동일한 numOfUniqueTrees(6) 계산으로 돌아가 보겠습니다.

(5:0) = 42, (4:1) = 14, (3:2) =10 (왼쪽 5 * 오른쪽 2), (2:3) = 10, (1:4) = 14, (0: 5) = 42. 이를 합산하면 132, numOfUniqueTrees(5) = 132 가 됩니다.

작업이 해결되었습니다!

결과: N = 6인 솔루션에서 중복되는 하위 문제를 기록해 보겠습니다. 간단한 솔루션에서 numOfUniqueTrees(3) 18번 호출됩니다(아래 화면). N이 증가하면 동일한 계산의 반복이 훨씬 커집니다.

(왼쪽 5개, 오른쪽 0개) 및 (왼쪽 0개, 오른쪽 5개)에 대한 고유 트리 수가 동일하다는 점을 강조합니다. 한 경우에만 왼쪽에 있고 다른 경우에는 오른쪽에 있습니다. 이는 (왼쪽 4개, 오른쪽 1개) 및 (왼쪽 1개, 오른쪽 4개)에도 적용됩니다.

동적 프로그래밍의 접근 방식인 메모화를 통해 우리는 이러한 복잡한 작업에 대한 솔루션을 최적화할 수 있었습니다.

구현

 class Solution { fun calculateTees(n: Int, memo:Array<Int?>): Int { var treesNum = 0 if(n < 1) return 0 if(n == 2) return 2 if(n == 1) return 1 if(memo[n]!=null) return memo[n]!! for (i in 1..n){ val leftSubTrees = calculateTees( i - 1, memo) val rightSubTrees = calculateTees(n - i, memo) treesNum += if(leftSubTrees>0 && rightSubTrees>0){ leftSubTrees*rightSubTrees } else leftSubTrees+leftSubTrees } memo[n] = treesNum return treesNum } }