[Algorithm] DP(다이나믹 프로그래밍)

01 다이나믹 프로그래밍**Dynamic Programming**이란?

• 큰 문제를 작은 문제들로 나누어 해결한 후, 그 결과를 저장하여 중복 계산을 줄이는 최적화 기법(알고리즘)이다.
  • 분할정복(Divied and Conquer)도 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다.
  • 다이나믹 프로그래밍과 분할 정복의 차이는 큰 문제를 작은 문제로 나눴을 때, 중복이 가능한지 불가능한지이다.
    • DP는 작은 문제의 중복이 된다.
    • 분할정복은 작은 문제의 중복이 안된다.
  • 10을 나눌 때 분할 정복이라면 5/5, 6/4, 7/3, 3/7과 같이 중복이 되지 않게 나눈다.
  • 10을 나눌 때 다이나믹 프로그래밍이라면 5,5,3,과 같이 중복이 되게 나눈다.
• 다이나믹 프로그래밍이란 이름 자체엔 아무런 의미가 없다.

 

02 다이나믹 프로그래밍 특징

1. 중복 계산 감소 : 이미 계산한 결과를 저장하고, 필요할 때 마다 재활용하여 중복된 계산을 피한다.
2. 점화식 : 주어진 문제의 해를 작은 문제의 해를 통해 표현하는 식을 정의, 이를 점화식이라고 부른다.
3. 최적 부분 구조 : 큰 문제의 최적해가 작은 문제들의 최적해를 통해 구할 수 있어야 한다.

 

03 다이나믹 프로그래밍으로 풀 수 있는 문제의 속성

• 모든 해결책을 다 탐색해보는 `완전탐색`은 기본적으로 높은 시간 복잡도를 가진다. 이를 체계적이고 효율적으로 탐색하기 위해서는 아래의 조건을 갖춰야 한다.
  • Overlapping Subproblem - 중복 하위 문제
    • 중복 계싼해야하는 하위 문제가 존재한다.
  • Optimal Substructure - 최적 부분 구조
    • 하위 문제에서 구한 최적의 답이 큰 문제의 최적의 답을 구할 수 있는 구조여야 한다.

 

04 예시 - 피보나치 수열 (Overlapping Subproblem)

피보나치 수열

• F(1) = 1
• F(2) = 1
• F(n) = F(n-1) + F(n-2) (n >= 3)

이때 시간 복잡도는 매번 2개의 함수를 호출함으로 O(2^n)​의 시간 복잡도를 가진다. 아무래도 완전 탐색이다보니, 높은 시간복잡도를 가지게 된다.

const fibonacci = (n) => {
	if(n == 1 || n == 2) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

 

피보나치 수열의 큰 문제를 작은 문제로 나누기

• 큰 문제 : N번째 피보나치 수를 구하는 문제
• 작은 문제 : N-1번째 피보나치 수를 구하는 문제, N-2번째 피보나치 수를 구하는 문제
• 큰 문제2: N-1번째 피보나치 수를 구하는 문제
• 작은 문제2 : N-2번째 피보나치 수를 구하는 문제, N-3번째 피보나치 수를 구하는 문제
• 큰 문제3 : N-2번째 피보나치 수를 구하는 문제
• 작은 문제3 : N-3번째 피보나치 수를 구하는 문제, N-4번째 피보나치 수를 구하는 문제

주로 이러한 경우에는 재귀를 사용한다.

 

 

05 예시 - dp를 이용해 피보나치 수 구현하기

예시로 f(7)를 보면,

위의 이미지와 같이 상당한 중복이 발생하는 것을 볼 수 있다.

 

하지만, 전에 계산했던 것을 기억한다면, 위와 같은 중복 문제를 피할 수 있을 것이다.

 

[설명]

• f(5)를 전에 계산 했으면, 후에 같은 과정으로 f(5)를 계산할 필요 없이 값을 저장해준다는 것이다. 

이렇게 되면 시간 복잡도는 O(n)으로 획기적으로 줄어들게 된다.

 

Top-down 방식과 Bottom-up 방식

• Top-down 방식
  • 큰 문제붜 문제를 쪼개가며 작은 문제로 만들고 다시 합쳐가며 원래 문제를 푸는 방식

let memo = [0];

const fibonacci = (n) => {
    if (n == 1 || n == 2) {
        memo[n] = 1;
    }
    if (!memo[n]) {
        memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
    }
    return memo[n];
}

 

시간복잡도 비교

• n = 7 일 경우
• 메모이제이션 없는 재귀함수의 총 함수 호출 횟수
  • n = 1일 때
    • 계산 없음, 1 반환
    • 계산 1회
  • n = 2일 때
    • 계산 없음, 1 반환
    • 계산 1회
  • n = 3일 때
    • n = 1일 때 계산 1회
    • n = 2일 때 계산 1회
    • n = 1 일 때와 n =2일 때를 더해주는 연산 1회
    • 총 3회
  • n = 4일 때
    • n = 2일 때 계산 1회
    • n = 3일 때 계산 3회
    • n = 2일 때와 n = 1일 때를 더해주는 연산 1회
    • 총 5회
  • n = 5일 때
    • n = 3일 때 계산 3회
    • n = 4일 때 계산 5회
    • n = 3일 때와 n = 4일때를 더해주는 연산 1회
    • 총 9회
  • n = 6일 때
    • n = 4일 때 계산 5회
    • n = 5일 때 계산 9회
    • n = 4일 때와 n = 5일 때를 더해주는 연산 1회
    • 총 15회
  • n = 7일 때
    • n = 5일 때 계산 9회
    • n = 6일 때 계산 15회
    • n = 5일 때와 n = 6일 때를 더해주는 연산 1회
    • 총 25회

위와 같은 횟수의 연산을 계속한다.

규칙을 보면 n - 1의 연산횟수 + n - 2의 연산 횟수 + 1회 가 추가된다.

n = 7 일 때, 메모제이션이 없는 재귀함수는 총 25회의 콜이 발생하게 된다.

 

• 메모제이션이 있는 재귀함수
  • n=1일 때
    • 1반환
    • n[1] = 1
    • 1회
  • n=2일 때
    • 1반환
    • n[1] = 1
    • 1회
  • n=3일 때
    • n[3] = n[2] + n [1]
    • n[1]일 때 1회 + n[2]일 때 1회 + 둘을 더하는 1회
  • n=4일 때
    • n[4] = n[3] + n[2]
    • n[2]일 때 1회 + n[3]일 때 1회 + 둘을 더하는 1회
  • ...

이처럼 n이 몇이든 함수호출은 3번씩만 일어나게 된다.

그래서 총 n=7일 경우 총 함수호출이 17번만큼 이루어진다.

 

• Bottom-up 방식
  • 작은 문제들을 모아서 큰 문제를 만들어 쌓아 올려가는 방식

const d = new Array(100);

const fibona = (n) => { 
    d[1] = 1;
    d[2] = 1;

    for (let i = 3; i <= n; i++) { 
        d[i] = d[i - 1] + d[i - 2];
    }

    return d[n];
}

 

정리,

Top-down 방식은 재귀(recursion)로 구현되는 반면,

Bottom-up 방식은 반복문(iteration)을 통해 구현된다.

 

06 dp 꿀팁

언제 dp를 사용해야 할까?

1. dfs/bfs로 풀 수 있지만 경우의 수가 너무 많은 문제
2. 경우의 수들에 중복적인 연산이 많은 경우 (피보나치 수열 같은 문제)

 

중복 연산을 줄이는 방법은 생각하기 어렵지만 최소한 중복 연산이 많다는 것은 dp문제를 풀다보면 쉽게 감을 잡을 수 있다.

따라서 문제를 많이 풀어보면서 어떤 문제를 dp로 풀어야하는지 감을 잡는 연습을 해봐야한다.

 

07 문제 해결 접근 방법

특정 문제를 dp로 풀어야겠다고 방향을 잡았다면?

우선 dp는 최대한 많은 문제들을 풀어보고 dp식 사고하는 법을 습득해야 한다.
연습 없이 dp식 사고방식을 터득하는 것은 매우 어려우니 dp 유형은 다른 유형보다 더욱 많은 문제를 풀어봐야 합니다.

 

dp식 사고방식

1️⃣ 어떻게 하면 중복연산을 피할 수 있을까?

2️⃣ 중복연산을 하지않으려면 어떤 정보를 남겨야할까?

3️⃣ 어떤 식으로 정보를 누적해야하지?

 

위와 같은 사고 방식을 가지고 연습하면서 터득해야 한다.

그리고 dp알고리즘에서 중요한 점은 점화식을 세우는 것이다. 여러 예제문제를 풀면서 점화식 세우는 연습을 해보자