[알고리즘] 동적 계획법(Dynamic Programming) 알아보기

안녕하세요😎 백엔드 개발자 제임스입니다 :)

이번에는 동적 계획법과 관련해서 포스팅하려고 합니다. 사실 동적 계획법은 어떠한 문제를 풀기 위한 전략 또는 기법에 가깝습니다. 따라서 추후 알고리즘을 다룰 때 해당 기법을 응용하여 개념을 정의하는 경우가 종종 있습니다. 이제 자세하게 알아보도록 하겠습니다.

---

---

동적계획법(Dynamic Programming, DP)

---

DP라고도 불리는 동적 계획법은 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 각 결과들을 저장한 뒤, 다시 큰 문제를 해결하는 방법입니다. 이것을 '상향식 접근법'이라고 하며, 가장 최하위 해답을 구한 후 이것을 활용하며, 상위 문제를 풀어가는 의미입니다.

• 캐시(cache) : 이미 계산한 값을 저장해 두는 메모리
• 중복되는 부분 문제(overlapping subproblems) : 두 번 이상 계산되는 부분

 

01. 피보나치 수열을 통해 동적 계획법 이해하기

동적 계획법은 피보나치 수열을 구현할 때 대표적으로 활용됩니다.

먼저 피보나치 수열에 대해서 간단하게 살펴보도록 하겠습니다.

* 피보나치 수열(Fibonacci sequence)
제 0항을 0, 제 1항을 1로 두고, 둘째 번 항부터는 바로 앞의 두 수를 더한 수로 놓는다.

피보나치 수열의 점화식을 먼저 알아보면, 아래와 같은 식을 알 수 있습니다.

F₀ = 0, F₁ = 1, Fₙ₊₂ = Fₙ₊₁ + Fₙ

예를 들어 이 식을 통해서 16번째 항까지만 나열하면 아래와 같습니다.

(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987)

그리고 이것을 그림으로 나타낸다면 아래와 같습니다. 아래 그림은 5번째 항을 구하기까지의 과정입니다.

제 5항까지 구하는 과정

위 그림을 보았을 때 어떤가요?
보다시피 반복되는 연산을 통해서 비효율적으로 계산하는 것을 볼 수 있습니다. 그렇다면 만약 앞에서 연산하여 나온 결과를 저장해두고, 필요할 때 재사용한다면 어떨까요?

위 그림과 같이 한번 연산을 진행했던 항은 저장해뒀던 값만 불러오면 되기 때문에 똑같은 과정을 반복할 필요가 없게 됩니다. 가령, F(0)과 F(1)을 통해서 F(2)를 구했다고 합시다. 다음 기존 방식으로 F(3)을 구하하기 위해서는 또 F(0)과 F(1)을 더해서 F(2)를 만든 이후 다시 F(1)과 더해야 하죠.
반면 저장해두는 방식이라면, F(3)을 구하기 위해서 이전에 저장한 F(2)의 값을 그냥 갖고와서 F(1)과 더하면 됩니다. 그리고 그렇게 나온 F(3)의 결과도 저장해둡니다.
이어서 F(4)를 구하려면 저장한 F(2)와 F(3)을 갖고와서 단순히 더해주기만 하면됩니다.

02. 코드를 통해서 동적 계획법 이해하기

피보나치 수열을 구하는 과정을 재귀 용법과 동적 계획법으로 코드로 작성하여 비교하겠습니다.

---

1) 재귀 용법으로 구현한 피보나치 함수

public int fibonacciFunc(int n) {

// 재귀 용법으로 작성된 방식

	if(n <= 1) {
    	return n;
    }
    
    return this.fibonacciFunc(n-2) + this.fibonacciFunc(n-1);
}

• 코드는 굉장히 짧아 보이지만, 입력받는 n 값이 클수록 돌아가는 내부는 어마어마하게 복잡해집니다.

 

2) 동적 계획법으로 구현한 피보나치 함수

public int dynamicFunc(int n) {
	
    // 입력받은 수 + 1 만큼 크기의 배열 생성
    Integer[] cache = new Integer[n+1];
    
    // 0항과 1항의 값은 미리 0과 1로 저장
    cache[0] = 0;
    cache[1] = 1;
    
    for(int i = 2; i <= n; i++) {
    
    	cache[i] = cache[i-1] + cache[i-2];
    }
    
    // n에 해당하는 위치에 저장된 값을 반환
    return cache[n];
    

}

• 배열의 인덱스에 맞게 값이 저장되기 때문에 배열은 n+1 만큼의 크기가 필요합니다. 예를 들어서 n이 5라면, 배열의 크기는 6이 되는 것이죠.
• 0항과 1항은 각각 0과 1이란 것을 알고있기 때문에 배열의 0번 인덱스와 1번 인덱스에 미리 선언해둡니다.
• 2항부터 값을 구하여 저장하면 되기 때문에 반복문의 초기값을 2로 시작합니다.
• 배열의 크기를 지정할 때와 동일하게, 해당 인덱스가 곧 입력받는 값과 같습니다. 따라서 반복문의 조건식에서 i는 n의 이하까지라고 지정합니다.
• 반복문을 진행하면서 나오는 결과값은 각 인덱스에 저장합니다.
• 저장된 값 중 우리가 원하는 결과값을 가진 배열의 값을 반환합니다.

*Tip ( 동적 계획법 구현 방식)
1) Bottom-up (Tabulation 방식) - 반복문 사용
- 아래에서 부터 계산을 수행하고 누적시켜서 전체 큰 문제를 해결하는 방식
2) Top-Down (Memoization) - 재귀 사용
- 위에서 부터 바로 호출을 시작
- arr[0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식

 

03. 시간 복잡도(공간 복잡도)

위에서 알아봤듯이 반복되는 과정을 제거함으로써 매우 효율적으로 문제를 해결할 수 있습니다.
따라서 시간 복잡도는 기존 방식에선 O(n^2) 이 발생할 것을 O(n) 으로 개선됩니다.
단, 사용하는 변수와 배열의 공간이 발생해서 공간 복잡도는 조금은 증가하게 됩니다.

 

---

---

다음 포스팅 내용

• 분할 정복 알고리즘 (Divide and Conquer)

https://kang-james.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B6%84%ED%95%A0-%EC%A0%95%EB%B3%B5Divide-and-Conquer-%EC%95%8C%EC%95%84%EB%B3%B4%EA%B8%B0

[알고리즘] 분할 정복(Divide and Conquer) 알아보기