동적계획법

수민·2022년 12월 15일
0

알고리즘

목록 보기
8/22

🍔재귀란?

재귀:어떤 함수가 스스로를 호출하는 것.
exam:5x4x3x2x1

문제 : 자연수를 입력받고, 입력받은 수부터 1까지의 자연수를 모두 곱한 값을 리턴하는 재귀 함수 fac 을 작성하세요.
예1) fac(5) === 5 4 3 2 1 === 120
예2) fac(3) === 3 2 1 === 6


function Fac(n)
	


![](https://velog.velcdn.com/images/qwa1822/post/753bad87-069c-4a1d-b79d-ef68413d023e/image.png)

    번째 수는 n-1번째와 n-2번째 수를 합하여 나타내는
피보나치 수열(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...)을 구하는 함수를 구해보았다.


```javascript
function fibonacci(n) {
  // TODO: 여기에 코드를 작성합니다.

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

}
위와같이 재귀형태로 두 번 함수를 호출하는 형식이다.
이렇게 불필요한 중복호출이 많을 경우 런타임이 길어진다.

어떠한 문제를 풀 때, 작성한 소스가 입력된 값에 대해 문제를 해결하는 데 필요한 시간을 시간복잡도라고 하며, 위의 문제와 같이 풀 경우 이 시간복잡도가 가파르게 증가하게 된다.

n번째 피보나치 항을 여러 번 계산한다고 해서 그 값이 달라지지 않는다. 즉, 한번 구한 항을 기록(memoization) 해 둔 다음, 그 값이 필요할 때 꺼내쓸 수 있다면 굉장히 효율적일 것이다.

동적계획법의 알고리즘은 아래와 같다.
1. 문제를 부분 문제로 나눈다.
2. 가장 작은 문제를 해를 구한 뒤, 테이블에 저장한다.
3. 테이블에 저장되어있는 데이터로 전체의 문제의 해를 구한다.

따라서 재귀함수를 한 번만 호출하는 방식으로 함수를 다르게 작성해볼 수 있다.

function fibonacci(n) {
  // TODO: 여기에 코드를 작성합니다.
 //일단 초기 배열이 [0, 1]에서 시작하여 배열의 요소를 누적해 나가는 방법
 //그리고 이미 구해놓은 것은 배열의 요소로 저장해놓기..!!! 그래야 런타임이 초과되지 않는다

 let newArr = [0, 1]; //0번째 1번째 요소는 고정시켜두고 
 
  let fib = (n) => { //함수 한개를 선언해주고
    if (newArr[n] !== undefined){ 
      return newArr[n]; //이미 있는 건 그대로 리턴
    }
    newArr[n] = fib(n - 1) + fib(n - 2); //없는 건 새로 만들어서 저장!!!*****
    return newArr[n];
  };
  
  return fib(n); 
}

`

문제를 풀 때 반복문 사용이 금지된다고 하여,,,

전달인자 n번째로 배열의 요소가 이미 있는 경우
없는 경우: 새로 만들어서 그 값을 배열에 넣어주기(-->피보나치 수열을 '메모'하는 캐시 배열을 만들어서 값을 채워주는 것)
이렇게 간단한 로직으로 나타내어 보았다.

참고자료:https://velog.io/@devjade/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%88%98%EC%97%B4-%ED%9A%A8%EC%9C%A8%EC%A0%81%EC%9C%BC%EB%A1%9C-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0Dynamic-programming

동적 계획법(Dynamic Programming)

동적 계획법(Dynamic Programming, DP)은 큰 문제를 작은 문제로 나누어서 푸는 방식의 알고리즘이다. 동적 계획법은 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 낸다는 점에서 분할 정복(Divide & Conquer, D&C)과 비슷하다. 하지만 가장 큰 차이점은 동적 계획법에서는 쪼개진 작은 문제가 중복되지만, 분할 정복은 절대로 중복될수가 없다는 점이다.

다시 말하면, 동적 계획법과 분할 정복의 차이는 문제를 나누는 방식이다. 동적 계획법에서는 어떤 부분 문제는 두 개 이상의 문제를 푸는데 사용될 수 있기 때문에, 이 문제의 답을 여러 번 계산하는 대신 한 번만 계산하고 그 결과를 재활용함으로써 속도의 향상을 시킬 수 있다. 이때 이미 계산한 값을 저장해 두는 메모리를 캐시(cache)라고 부르며, 두 번 이상 계산되는 부분 문제를 중복되는 부분 문제(overlapping subproblems)라고 부른다.

1. 동적 계획법의 조건

  • 두 가지 속성을 만족해야 동적 계획법으로 문제를 풀 수 있다.
  1. Overlapping Subproblem : 겹치는 부분(작은) 문제
  2. Optimal Substructure : 최적 부분구조

1.1. Overlapping Subproblem

겹치는 부분 문제(overlapping subproblem) 는 어떤 문제가 여러개의 부분문제(subproblem)으로 쪼개질 수 있을때 사용하는 용어이다. 이때 '부분 문제'란, 항상 새로운 부분 문제를 생성해내기 보다는 계속해서 같은 부분 문제가 여러번 재사용되거나 재귀 알고리즘을 통해 해결되는 문제를 가리킨다.

대표적인 예로 피보나치 수열이 있다.
0 1 1 2 3 5 8 13 21 34 55 89 ...

  • 피보나치 수열은 앞의 두 수를 더한 수가 다음 수가 되는 수열이다.
  • F0 = 0
  • F1 = 1
  • Fn = Fn-1 + Fn-2 (n ≥ 2)

겹치는 부분 문제가 있다면, 큰 문제는 작은 문제들을 통해 정답을 구할 수 있다. 큰 문제는 작은 문제와 같은 방법으로 풀 수 있으며, 모든 문제를 작은 문제로 쪼갤 수 있기 때문이다. (기저 사례를 제외한 모든 문제)

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

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

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

1.2. Optimal Substructure

최적 부분구조(optimal substructure)는 어떤 문제의 최적의 해결책이 그 부분 문제의 최적의 해결책으로 부터 설계될 수 있는 경우를 말한다. 즉, 최적 부분구조 일때 문제의 정답을 작은 문제의 정답에서 부터 구할 수 있다. 이 속성은 동적 계획법이나 그리디 알고리즘의 유용성을 판별하는데 사용되기도 한다.

(예시)
• 서울에서 부산을 가는 가장 빠른 길이 대전과 대구를 순서대로 거쳐야 한다면
• 대전에서 부산을 가는 가장 빠른 길은 대구를 거쳐야 한다.

서울->대전->대구->부산 : 가장 빠른 경로

Q) 대전->부산
A) 대전->대구->부산 : 가장 빠른 경로

만약 가장 빠른 경로가 서울->대전->울산->부산 이라면

Q) 대전->부산
A) 대전->울산->부산 : 가장 빠른 경로

다시 피보나치 문제로 돌아와보면

• 문제: N번째 피보나치 수를 구하는 문제
• 작은 문제: N-1번째 피보나치 수를 구하는 문제, N-2번째 피보나치 수를 구하는 문제
-> 문제의 정답을 작은 문제의 정답을 합하는 것으로 구할 수 있다.

• 문제: N-1번째 피보나치 수를 구하는 문제
• 작은 문제: N-2번째 피보나치 수를 구하는 문제, N-3번째 피보나치 수를 구하는 문제
-> 문제의 정답을 작은 문제의 정답을 합하는 것으로 구할 수 있다.

• 문제: N-2번째 피보나치 수를 구하는 문제
• 작은 문제: N-3번째 피보나치 수를 구하는 문제, N-4번째 피보나치 수를 구하는 문제
-> 문제의 정답을 작은 문제의 정답을 합하는 것으로 구할 수 있다.

• Optimal Substructure를 만족한다면, 문제의 크기에 상관없이 어떤 한 문제의 정답은
일정하다.
• 10번째 피보나치 수를 구하면서 구한 4번째 피보나치 수
• 9번째 피보나치 수를 구하면서 구한 4번째 피보나치 수
• …
• 5번째 피보나치 수를 구하면서 구한 4번째 피보나치 수
• 4번째 피보나치 수를 구하면서 구한 4번째 피보나치 수
• 4번째 피보나치 수는 항상 같다. -> 겹치는 부분문제의 정답이 항상 같다!

이처럼 같은 값을 매번 구하는 것은 매우 비효율적이다. 이때 이를 해결할 수 있는 방법이 바로 메모이제이션(Memoization)이다.

  1. 메모이제이션(Memoization)

동적 계획법에서 각 문제는 한 번만 풀어야 한다. 중복되는 부분 문제를 여러번 풀지 않는다는 뜻이다. Optimal Substructure를 만족하기 때문에 같은 문제는 구할 때마다 정답이 같다. 따라서 정답을 한 번 구했으면 그 정답을 캐시에 메모해놓는다. 이렇게 메모하는 것을 코드의 구현에서는 배열에 저장하는 것으로 할 수 있다. 이를 메모이제이션(Memoization)이라고 한다.


int fibonacci(int n) {
    if (n <= 1) {	// F(0) = 0, F(1) = 1
        return n;
    } else {
	return fibonacci(n-1) + fibonacci(n-2);
    }
}

위의 코드는 피보나치 수를 구하는 함수이다. 점화식을 그대로 표현하여 재귀호출을 하고 있다. F(0)과 F(1)은 더 이상 쪼갤 수 없으므로, 그냥 n을 리턴한다. 이것을 재귀호출 그대로 실행한다면 시간복잡도는 함수의 깊이가 N일때 O(2^N)이다. 이 경우에는 이진트리의 탐색속도와 같다. 다음은 fibonacci(5)를 호출했을때의 그림이다.

  • 이때 f(3)과 f(2)는 겹치는 부분문제이고 정답이 같으므로, 미리 캐시에 저장해두고 활용할 수 있다. 그래서 메모이제이션하면 부분문제에서 또 파생되는 부분문제의 가지를 모두 생략할 수 있다. (중복되므로) 즉, 모든 문제를 한 번씩만 푼다. 때문에 시간복잡도는 (문제의 개수 x 문제 1개를 푸는시간) 이 되는데, 문제의 개수가 N -> O(N), 문제 1개를 푸는 시간은 +연산 하나(함수의 시간복잡도) -> O(1)이므로, 전체 시간복잡도는 O(N) 이다. 이를 구현한 코드는 다음과 같다.
int memo[100];
int fibonacci(int n) {
    if (n <= 1) {
    	return n;
    } else {
    	memo[n] = fibonacci(n-1) + fibonacci(n-2);
    	return memo[n];
    }
}

이런식을 구현하면 될텐데, 여기에서 이미 계산한 부분문제의 경우 그 값을 그대로 사용하는 코드를 추가해야 한다. memo배열에 값이 0이면 답을 구하지 않았다는 뜻이고, 0이 아니면 답을 구한적이 있다(이전의 호출에서 해당 값을 구함)는 뜻이므로, 이를 활용하면 된다.

int memo[100];
int fibonacci(int n) {
    if (n <= 1) {
    	return n;
    } else {
        if (memo[n] > 0) {	// memo의 값이 0이 아니면
            return memo[n];	// 그 값을 그대로 사용
        }
        memo[n] = fibonacci(n-1) + fibonacci(n-2);
        return memo[n];
    }
}

🌭3. 동적 계획법 구현 방식

동적 계획법의 구현 방식에는 두 가지 방법이 있다.

  1. Top-down : 큰 문제를 작은 문제로 쪼개면서 푼다. 재귀로 구현
  2. Bottom-up : 작은 문제부터 차례대로 푼다. 반복문으로 구현
    Top-down과 Botton-up의 시간복잡도 차이는 문제에 따라 다를 수 있으므로 정확히 알 수는 없다. Top-down은 재귀호출을 하기때문에 스택의 사용으로 시간이 더 걸릴 것이라고 생각할 수 있겠지만, 실제로 그 차이는 크지 않다. 다만, 파이썬의 경우 재귀 호출 시 스택 오버 플로우(stack overflow)가 발생할 수 있기때문에, Bottom-up으로 구현하는 것이 좋다. C++과 JAVA에서는 재귀로 구현하는 것이 크게 문제가 되지 않는다.

어떠한 상황에서는 오히려 재귀로 구현하는 것이 간단하게 보이는 경우도 있다. 예를 들면, Fn = Fn-10 + Fn-20 이라는 문제가 있다고 하자. 재귀에서 이를 구하려면 F(20)을 호출하면 F(10)+F(0)으로 두번의 호출만에 정답이 구해진다. 하지만 반복문으로 구현하면 F(1),F(2),... 과 같이 반복횟수가 많아진다.

하지만 Top-down으로만 해결가능하거나 Bottom-up으로만 해결가능한 문제는 극히 드문 경우이므로, 아무거나 선택해서 사용하면 된다.

3.1. Top-down

  1. 큰 문제를 작은 문제로 나눈다.
  2. 작은 문제를 푼다.
  3. 작은 문제를 풀었으니, 이제 큰 문제를 푼다.

피보나치 문제로 예를 들면,

fibonacci(n)라는 문제를 풀기위해서
1. 문제를 작은 문제로 나눈다.
• fibonacci(n-1)과 fibonacci(n-2)로 문제를 나눈다.
2. 작은 문제를 푼다.
• fibonacci(n-1)과 fibonacci(n-2)를 호출해 문제를 푼다.
3. 작은 문제를 풀었으니, 이제 문제를 푼다.
• fibonacci(n-1)의 값과 fibonacci(n-2)의 값을 더해 문제를 푼다.

코드는 앞에서 설명한것과 같이 재귀호출로 구현할 수 있다.

int d[100];
int fibonacci(int n) {
    if (n <= 1) {
    	return n;
    } else {
        if (d[n] > 0) {		// d의 값이 0이 아니면
            return d[n];	// 그 값을 그대로 사용
        }
        d[n] = fibonacci(n-1) + fibonacci(n-2);
        return d[n];
    }
}

3.2. Bottom-up
1. 문제를 크기가 작은 문제부터 차례대로 푼다.
2. 문제의 크기를 조금씩 크게 만들면서 문제를 점점 푼다.
3. 작은 문제를 풀면서 왔기 때문에, 큰 문제는 항상 풀 수 있다.
4. 반복하다 보면 가장 큰 문제를 풀 수 있다.
똑같이 피보나치 문제로 예를 들면,

  1. 문제를 크기가 작은 문제부터 차례대로 푼다.
    • for (int i=2; i<=n; i++)
  2. 문제의 크기를 조금씩 크게 만들면서 문제를 점점 푼다.
    • for (int i=2; i<=n; i++)
  3. 작은 문제를 풀면서 왔기 때문에, 큰 문제는 항상 풀 수 있다.
    • d[i] = d[i-1] + d[i-2];
  4. 반복하다 보면 가장 큰 문제를 풀 수 있다.
    • d[n]을 구하게 된다.
    따라서 다음과 같이 반복문으로 코드를 작성할 수 있다.


```javascript
int d[100];
int fibonacci(int n) {
    d[0] = 0;
    d[1] = 1;
    for (int i=2; i<=n; i++) {	// 2에서 부터 시작해서 n까지 반복
    	d[i] = d[i-1] + d[i-2];
    }
    return d[n];
}

참고: https://velog.io/@polynomeer/%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming

profile
수민
헬창목표
이전 포스트

최빈값 구하기(프로그래머스

다음 포스트

재귀(Recursion)

0개의 댓글