[알고리즘] 동적 계획법 / Dynamic Programming

드디어 첫 알고리즘과 관련된 게시글을 작성한다! (짝짝짝)

동적 계획법, 말만 들으면 무슨말인지 모르겠다. 느낌적으로는 뭔가 활발하게(?) 바뀌는 느낌인데, 다음과 같은 프로그래밍을 칭한다.

하나의 문제를 여러 문제로 나누어 푸는 방법

예를 들어서, 우리가 1~10까지의 합을 계산할 때, 하나의 문제는 다음과 같이 존재한다.

1+2+3+...+8+9+10 = 55
- 물론 n*(n+1) / 2 로 풀 수도 있다. 그치만 그게 중요한게 아니니까!

이를 여러 문제로 나누게 되면, 다음과 같이 바뀌게 된다.

1+2 = 3
1+2+3 = 3+3 = 6
1+2+3+4 = 6 + 4 = 10
1+2+3+4+5 = 10 + 5 = 15
1+2+3+4+5+6 = 15 + 6 = 21
...
1+2+3+...+8+9+10 = 45 + 10 = 55

---

왜?

동적 계획법은 문제를 빠르게 풀 수 있다는 장점이 존재한다. 위에서 예로 든 1~10까지의 합을 계산 할 때, 마지막 합을 계산할 때 이미 앞 단계의 합은 계산되어 있는것을 알 수 있다. 즉 1~N까지의 합을 구하기 위해 O(n)만에 풀 수 있는 것이다.

동적 계획법을 이미 알고 있는 사람이라면, 어? 예시가 잘못 된거 아니야? 원래 1~N까지의 합은 O(n)안에 풀리는데? 라고 생각할 수 있다.

물론 맞는말이다! 하지만, 동적 계획법을 모르는 사람이 공부를 시작한다면, 처음부터 피보나치, 연속 합, 합 만들기, 파도반 수열, 길 찾기, ... 등으로 예시를 든다면, 처음부터 이해가 안갈 것이고, 따라서 정~~말 쉬운 것부터 풀어보고자 위의 예시를 들었다.

N단계를 풀 때, 이미 N-1단계는 계산되어 있다.

---

피보나치 수열

항: (0) 1 2 3 4 5 6  7   8 ...
수: (0) 1 1 2 3 5 8 13 21 ...
점화식 F
Fn+2​= Fn+1​+ Fn​ = Fn-2 + Fn-1

피보나치 수는 앞 선 두 항의 합이 현재 항이 되는 수열을 나타낸다. 다시말해 F(6)을 풀기 위해서는 F(6) = F(5)+F(4)에 대한 연산을 수행해야 한다. 이를 동적계획법을 사용하지 않고 나타낸다면, 다음과 같은 연산이 필요하다.

F(6)에 대한 연산

사람같은 경우에 F(5) = 5라는 것을 직감적으로 알 수 있지만, 컴퓨터는 모른다. 따라서 매 번 요청 할 때마다 연산을 수행해야 한다.

잘 보면 겹치는 항들이 많다.

해당 트리를 잘 보면, 2를 연산하기 위해 1, 0을 호출하고, 3을 연산하기 위해 2, 1을 호출하고, ..., 겹치는 연산이, 재귀적인 호출이 굉장히 많다. 또한 이 연산을 위한 시간 복잡도를 계산해 보면 O(2^n)이라는 큰 복잡도를 가진다.

Tree의 Height = Depth = 5
Tree의 Level이 증가함에 따라(Height가 감소함에 따라) Fib(N)의 N이 하나씩 줄어들고, 결국 N을 계산하기 위해 각 레벨에서 N - 1씩 연속적으로 호출한다.
N => N-1, N-2 => (N-2, N-3), (N-3, N-4) => ( (N-3, N-4), (N-4, N-5) ), ( (N-4, N-5), (N-5, N-6) ) ...
→ N에 대하여 2^n 만큼 증가!

이러한 시간복잡도를 줄이기 위해(문제를 해결하기 위해) 동적 계획법을 사용하면 꽤나 빠른 시간 안에 연산할 수 있다.

불필요한 연산이 사라졌다.

동적계획법을 활용하지 않으면, 사라진 노드들에 대해 일일히 모두 계산해줘야 하지만, 동적계획법을 사용함으로써 fib(3)의 값이 2임을 이미 알고있고, 따라서 fib(3)의 연산을 추가적으로 하지 않은 것을 확인할 수 있다.

// fibonacci 연산 값을 저장할 배열
int[] fibonacci;

// fibonacci 값을 연산하는 함수
func setfib(limit)
  fibonacci[0] = 0;
  fibonacci[1] = 1;
  for i -> 2 to limit
    fibonacci[i] = fibonacci[i-2] + fibonacci[i-1];
  end for
end func

// 찾고자 하는 피보나치 수를 반환하는 함수
func getfib(N)
  return fibonacci[N]

시간복잡도는 O(n)안에 풀 수 있다.

그 이유는..위 트리를 보세요..ㅎㅋㅎㅋ

---

정리하면서,

우선

동적 계획법을 사용하려면, 풀고자하는 문제의 점화식(규칙)을 찾아야한다. 위에서 예로 든 피보나치의 경우, F(N) = F(N-2) + F(N-1)과 같은 식 말이다.

문제마다 식이 다르기 나오기에, 어떻게 해라! 라는게 딱히 없다. 다만, 규칙을 찾을 때 까지 수를 나열해 보거나, 문제로부터 힌트를 얻는 방법 밖에 없다.

피보나치와 같은 문제는 수를 나열하며 규칙을 찾을 수 있을 것이고, Working Days Problem과 같은 경우에는, 문제로부터 힌트를 얻을 수 밖에 없다. (하루 건너 일할 때 가장 돈을 많이 버는 경우는 마지막 날에 일을 하냐 안하냐로 판단할 수 있는것 처럼.)

끝으로

동적 계획법은 다음과 같은 문제를 풀 때 사용하면 좋다.

1. 중복되는 풀이를 할 때
2. 재귀로 풀면 시간 복잡도가 클 때