코테 스터디 7주차 - Dynamic Programming

이번 코테 스터디의 7주차 주제는 DP, 즉 다이나믹 프로그래밍이다!!! 처음에 DP 문제를 풀어보았을 때 항상 DP를 사용하지 않고 풀어 시간 초과가 자주 발생했던 기억이 있다ㅠㅠ 백준 문제를 풀어보면서 시간 초과나는 경우 DP를 사용해야하는 경우가 많았던 것 같다. 따라서 이번 정리를 통해 DP가 무엇이고 왜 사용하는지를 알아보면서 내 것으로 만들어 보자!!!😁😁



우선 DP의 개념부터 짚고 넘어가보자

DP란?

• 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것!!!
• 특정한 알고리즘이 이닌 하나의 문제 해결 패러다임으로 볼 수 있다.

DP의 개념이 무엇인지 알아봤고 이제 왜 사용하고 어떻게 사용하는지 정리해보자

1. DP를 사용하는 이유

DP를 사용하는 이유는 무엇일까? 일반적인 재귀 방식 또한 DP와 매우 유사하다. 하지만 둘의 가장 큰 차이점은 재귀만 단순히 사용 시 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수 있다는 것이다!!!

피보나치 수열을 예로 알아보자
피보나치 수열을 단순히 재귀만 사용하면 다음과 같이 구현 할 수 있다.

int fibonacci(int n) {
	if(n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

여기서 코드를 자세히 살펴보면 f(n - 1)에서 구한 값을 f(n - 2)에서 또 다시 구하는 과정을 반복하게 된다. 즉, 아래 그림처럼 n = 5인 경우 이전에 구했던 값들을 다시 호출하는 것을 볼 수 있다.

하지만 한 번 구한 작은 문제의 결과 값을 저장해두고 재사용하게 되면 이전에 계산된 값을 다시 계산할 필요가 없어 계산 수가 확 줄일 수 있다. 다음 그림과 같이 호출되는 함수가 줄어든 것을 볼 수 있다.

즉, 매우 효율적으로 문제를 해결할 수 있게 되고 시간복잡도를 생각해보면 O(n^2) → O(n)으로 개선됨을 알 수 있다.

이제 DP를 왜 사용해야하는지 가볍게 알아보았고 언제 어떻게 사용하는지를 알아보자😛😛

2. DP를 사용하는 경우

어떠한 문제에서 DP를 이용하여 풀어야하는지 알아보자. DP가 적용되기 위해서는 다음 2가지 조건을 만족해야한다.

1) Overlapping Subproblems(부분 문제 반복)

• DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용하여 최종 결과를 도출해낸다. 따라서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다.
• 즉, DP는 부분 문제의 결과를 저장하여 재 계산하지 않을 수 있어야 하는데, 해당 _부분 문제가 반복적으로 나타나지 않는다면 재사용이 불가능하니 부분 문제가 중복되지 않는 경우에는 사용할 수 없다.

위에서 보았던 피보나치 수열을 예로 들면 f(3), f(2), f(1)과 같이 동일한 부분 문제가 중복되어 나타나기 때문에 DP를 사용하여 저장된 값을 재활용할 수 있게 된다.

2) Optimal Substructure(최적 부분 구조)

• 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미한다. 그래서 특정 문제의 정답은 문제의 크기에 상관없이 항상 동일하다!!

아래와 같은 경로가 존재할 때 A에서 B까지의 최단 경로를 찾고자하는 경우를 보자. A에서 X까지의 경로 중 최단 경로와 X에서 B까지의 최단 경로를 선택하게 되면 A에서 B까지의 최단 경로가 된다.

이와 같이, 부분 문제에서 구한 최적 결과가 전체 문제에서도 동일하게 적용되어 결과가 변하지 않을 때 DP를 사용할 수 있다.

3. DP 사용하는 방법

지금까지 DP를 사용할 수 있는 조건에 대해 알아봤고 이제는 DP를 사용하기 전에 거쳐야할 과정을 알아보자

일반적으로 DP를 사용하기 전에는 아래의 과정을 거쳐 진행한다.

1) DP로 풀 수 있는 문제인지 파악
2) 문제의 변수 파악
3) 변수 간 관계식 만들기(점화식)
4) 메모하기(memoization or tabulation)
5) 기저 상태 파악하기
6) 구현하기


그럼 하나씩 차근차근 살펴보자

1) DP로 풀 수 있는 문제인지 파악

• DP 문제를 많이 풀어보면서 느꼈지만 이 과정이 가장 어렵다고 생각한다. 현재 풀어야 할 문제가 DP로 풀 수 있는지 파악하는 것이 젤 중요하고 어렵다.

• 결국 위에서 알아본 DP를 사용하는 경우의 조건에 충족되는 문제인지 확인해 보는 것이 좋다.

• 또한, DP 문제를 많이 풀어보면서 감을 익히는 것이 원초적으로 가장 좋은 방법일 수 있다.
  
  
  

2) 문제의 변수 파악

• DP는 현재 변수에 따라 그 결과 값을 찾고 그것을 전달하여 재사용한다. 즉, 문제 내 변수의 개수를 알아내야 한다.

• 예를 들어, 피보나치 수열에서는 n번째 숫자를 구하는 것이므로 n이 변수가 되고 이 변수가 얼마이냐에 따라 결과 값이 다르지만 그 결과를 다른 계산에서 재사용한다.
  
  
  

3) 변수 간 관계식 만들기

• DP문제들은 변수들에 의해 결과 값이 다르지만 동일한 변수값인 경우 결과는 동일하다. 그러므로 우리는 이 결과값을 그대로 이용하기 때문에 관계식을 만들어 낼 수 있어야 한다.

• 그러한 식을 점화식이라 부르며 피보나치 수열에서의 점화식은 f(n) = f(n - 1) + f(n - 2)로 볼 수 있다.

• 점화식은 변수의 개수, 문제의 상황마다 모두 다를 수 있다.

DP 문제들을 반복적으로 풀어보면서 관계식 만드는 것에 익숙해지자!!!

4) 메모하기

• 메모하기는 말 그대로 변수의 값에 따른 결과를 저장하는 과정이다. 이를 메모한다고 하여 Memoization이라고 부른다.

• 이를 수행하기 위해 우리는 주로 배열을 사용하여 결과값을 저장한다!!!

5) 기저 상태 파악하기

• 기저 상태란 가장 작은 문제의 상태를 지칭하고 이는 보통 값을 알기 때문에 미리 배열에 저장한다.

• 피보나치 수열을 예로 들면, f(0) = 0, f(1) = 1이 가장 작은 문제이고 이를 배열에 미리 저장하여 문제를 해결한다.

6) 구현하기

• DP를 문제를 해결하는 마지막 과정으로 DP는 2가지 방식으로 구현할 수 있다.
  
  
  (1) Bottom-Up(Tabulation 방식) - 반복문 사용
  (2) Top-Down(Memoizaiton 방식) - 재귀 사용
  
  

(1) Bottom-Up 방식

• 아래에서 부터 계산을 수행하고 누적시켜서 전체 큰 문제를 해결하는 방식

• 즉, dp[0]의 기저 상태에서 목표 상태인 dp[n]까지 값을 전이시켜 재활용하는 방식이다.

(2) Top-Down 방식

• dp[0]의 기저 상태에서 출발하는 대신 dp[n]의 값을 찾기 위해 위에서 부터 바로 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식
  
  
  
  

솔직히 이렇게 적어놔도 형들은 '그래서 어떻게 구현하는데...'라면서 뭐라할 거 같다.😂😂😂

그래서 피보나치 수열을 두 가지 방법을 사용한 코드를 통해 감만 잡아보자

int bottomup_table[n + 1] = {0, };
int topDown_memo[n + 1] = {0, };
vector<int> topDown_memo(n+1)


// DP Bottom-Up을 사용해 피보나치를 구하는 경우
int bottomUp(int n) {
	// 기저 상태의 경우 사전에 미리 저장
    bottomup_table[0] = 0;
    bottomup_table[1] = 1;
	
    // 반복문을 사용하여 계산
    for(int i = 2; i <= n ; i++) {
    	bottomup_table[i] = bottomup_table[i-1] + bottomup_table[i-2];
    }
    return bottomup_table[n];
}



// DP Top-Down을 사용해 피보나치 구하는 경우
int topDown(int n) {
	// 기저 상태 도달 시, 0, 1로 초기화
    if(n < 2) return topDown_memo[n] = n;
    
    // 메모에 계산된 값이 있으면 바로 반환
    if(topDown_memo[n] > 0) return topDown_memo[n];
    
    // 재귀를 사용하여 계산
    return topDown(n - 1) + topDown(n - 2);
}

알아두면 좋은 것!!!

Q : Top-Down vs Bottom-Up

A : 두 방법 중 어느 것이 더 효율적인지는 '알수 없다'이다. 그리고 2가지 방법 중 하나만 사용해서 풀어야하는 문제도 있다. 따라서 이는 문제를 많이 풀어가면서 어느 경우에서 어떤 방식이 효율적인지를 찾아보자!!!

Q : 분할정복과 뭐가 다르지?

A : 분할정복과 DP는 주어진 문제를 작게 쪼개서 하위 문제로 해결하고 큰 문제를 해결한다는 점에서 유사하지만, 분할 정복은 하위 문제가 동일하게 중복이 일어나지 않는 경우에 사용되고, 동일한 중복이 일어나면 DP를 사용한다!!!

지금까지 매우 간단한 예시인 피보나치 예시를 통해서 DP를 배워보았다. 사실 경험상 변수랑 점화식 잘 찾는 게 젤 중요하고 이를 위해서는 결국 문제를 많이 풀어봐야하는데 몇 문제만 풀어봐도 감이 금방 잡혀 쉽게 풀 수 있을 것이다!!!👍👍👍 (8주차 DP 문제들 올릴테니 많이 풀어봐 형들ㅡㅡ)

참고 사이트
https://hongjw1938.tistory.com/47
https://didu-story.tistory.com/220
https://hyeinisfree.tistory.com/25