Dynamic Programming

CHOYEAH·2023년 11월 1일
알고리즘
0
post-custom-banner

동적 계획법(DP)

동적 계획법(Dynamic Programming)은 복잡한 문제를 작은 부분 문제로 나누어 해결하는 알고리즘 설계 기법입니다. 이를 통해 중복되는 계산을 효율적으로 제거하고 최적의 해를 찾을 수 있습니다.

  • 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘
  • 상향식 접근법(Bottom Up)으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식
  • Memoization 기법을 사용함 (다이나믹 프로그램의 핵심)
    • Memoization (메모이제이션):한 번 계산된 값은 메모리에 저장해서 동일한 계산은 반복하지 않도록하여 전체 실행 속도를 빠르게 하는 기술
  • 문제를 잘게 쪼갤 때, 부분 문제는 중복되어, 재활용됨
    • 예: 피보나치 수열

장점

  • 중복되는 계산을 효율적으로 제거하여 시간 복잡도를 줄일 수 있습니다.
  • 작은 부분 문제의 해를 저장하고 재사용함으로써 속도를 향상시킬 수 있습니다.
  • 최적의 해를 구하는 경우에 사용할 수 있는 강력한 알고리즘 기법입니다.

단점

  • 모든 문제에 동적 계획법을 적용할 수 있는 것은 아닙니다.
  • 부분 문제들의 해를 저장하기 위한 추가적인 메모리 공간이 필요합니다.

사용에 적절한 상황

  • 문제가 중복 부분 문제 구조를 가지고 있을 때: 동적 계획법은 중복되는 부분 문제의 해를 계산하고 저장하여 중복 계산을 피할 수 있으므로, 중복 부분 문제 구조를 가진 문제에 적합합니다.
  • 작은 부분 문제로 분할 가능한 경우: 큰 문제를 작은 부분 문제로 분할하여 해결하는 동적 계획법은 작은 단계의 해를 조합하여 전체 문제의 해를 구할 수 있습니다.
    • 피보나치 수열 계산
    • 최장 공통 부분 수열(LCS) 문제
    • 배낭 문제(Knapsack Problem)
    • 그래프 알고리즘에서 최단 경로(Dijkstra's Algorithm) 등

사용에 부적절한 상황

  • 중복 부분 문제가 없는 경우: 동적 계획법은 부분 문제의 중복을 활용하여 효율적으로 해를 구하는 것이 주요한 특징입니다. 중복 부분 문제가 없는 경우에는 다른 알고리즘 기법을 고려해야 합니다.
  • 메모리 제약이 있는 경우: 동적 계획법은 부분 문제의 해를 저장하기 위해 메모리를 사용합니다. 따라서 메모리 제약이 있는 경우에는 고려해야 합니다.

동적 계획법은 주어진 문제에 대해 적합한 알고리즘인지를 판단하기 위해 문제의 특성을 고려해야 합니다. 중복 부분 문제 구조가 있고 작은 부분 문제로 분할 가능한 문제에 대해서 동적 계획법을 사용하는 것이 일반적으로 적절합니다.

주의사항

  • 부분 문제의 중복 여부를 판단하여 동적 계획법을 적용해야 합니다. 중복이 없는 경우에는 다른 알고리즘을 고려해야 합니다.
  • 동적 계획법은 메모리를 사용하여 부분 문제의 해를 저장하므로, 메모리 제약이 있는 경우에는 고려해야 합니다.

시간 복잡도

  • 동적 계획법의 시간 복잡도는 부분 문제의 개수에 따라 결정됩니다.
  • 일반적으로, 동적 계획법은 중복 계산을 제거하여 지수적인 시간 복잡도를 다항 시간 복잡도로 줄여줍니다. 따라서 효율적인 알고리즘으로 간주됩니다.

구현

피보나치 수열을 리턴하는 함수를 재귀호출 방식과 동적 계획법 방식으로 구현하여 비교

피보나치 수열은 n 을 입력받았을 때 n==0일 경우 0을 리턴, n==1일 경우 1을 리턴, 그 외에는 F(n-1) + f(n-2)를 리턴한다.

# ex)
fibonacci(0) => 0
fibonacci(1) => 1
fibonacci(2) => 1
fibonacci(3) => 2
fibonacci(4) => 3  
fibonacci(5) => 5
fibonacci(6) => 8
fibonacci(7) => 13
fibonacci(8) => 21
fibonacci(9) => 34

recursive call 활용

function fibo(num) {
	if(num <= 1) {
		return num;
	}

	return fibo(num-1) + fibo(num-2);
}
fibo(4)
3
def fibo(num):
    if num <= 1:
        return num
    return fibo(num - 1) + fibo(num - 2)

fibo(4)
3

재귀호출 방식을 사용하여 구현하면 하위 노드에 해당하는 값을 구하는 과정을 중복하여 계산하게된다.

동적 계획법 활용

function fibo(n) {
  if (n <= 1) {
    return 1;
  }

  let cache = new Array(n + 1);
  cache[0] = 0;
  cache[1] = 1;
  for (let i = 2; i <= n; i++) {
    cache[i] = cache[i - 1] + cache[i - 2];
  }

  return cache[n];
}

let f1 = fibo(2);
console.log(f1);
def fibo_dp(num):
    cache = [ 0 for index in range(num + 1)]
    cache[0] = 0
    cache[1] = 1
    
    for index in range(2, num + 1):
        cache[index] = cache[index - 1] + cache[index - 2]
    return cache[num]

fibo(10)
55

동적 계획법을 사용하면 한 번 구한 하위 노드 결과값을 재사용하므로 중복 계산이 발생하지 않는다. 재귀호출 방식으로 사용하게 된다면 시간 복잡도는 0(2n)0(2^n)이지만 DP를 사용 시 O(n)O(n)까지 낮출 수 있다.

코드분석

DP 연습문제

문제1 2×n 타일링

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

  • 입력

    • 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

  • 출력

    • 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

  • 풀이전략

    • 점화식 구하기

      • 점화식이란 이웃하는 두 개의 항 사이에 성립하는 관계를 나타낸 관계식을 의미한다.

        • 예) dp[n+3] = dp[n+1] + dp[n+2]

      • 일반적인 동적 계획법 문제는 보통 코드 자체는 간결하므로 가장 적은 경우의 수부터 계산을 해본 후 패턴을 찾아 점화식을 세우는 것이 핵심

    • 구현

      # 빈 리스트 만들기 
dp = [0] * 1001

# 초기값 설정
dp[1] = 1
dp[2] = 2

# 점화식 기반 계산값 적용하기
for index in range(3, 1001): 
    dp[index] = dp[index - 1] + dp[index - 2]

# 특정 입력값에 따른 계산값을 리스트에서 추출
print (dp[2] % 10007)
print (dp[9] % 10007)

문제2 - 파도반 수열

그림과 같이 삼각형이 나선 모양으로 놓여져 있다.

첫 삼각형은 정삼각형으로 변의 길이는 1이다.

그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다.

나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다.

P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

  • 입력
    • 첫째 줄에 n이 주어진다. (1 ≤ N ≤ 100)
  • 출력 (입력 ⇒ 출력)
2  => 1
6  => 3
12 => 16
  • 풀이
    • 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, ...
    • 점화식: dp[ i + 3 ] = dp [ i ] + dp [ i + 1 ]
  • 구현
function padovanSequence(n) {
  if (n < 1 || n > 100) {
    return false;
  }

  let seq = new Array(n + 1);
  seq[0] = 0;
  seq[1] = 1;
  seq[2] = 1;

  for (let i = 3; i <= n; i++) {
    seq[i] = seq[i - 2] + seq[i - 3];
    /**
    seq[i+3] = seq[i] + seq[i+1] 방식
    현재 항을 구하기 위해 앞선 항들을 사용하는 점화식으로, 앞서 계산한 항들을 재사용할 수 있습니다. 
    이 방식은  이전 항들을 따로 저장해두지 않고도 다음 항을 계산할 수 있습니다.
    재귀적인 구현에 적합하며, 더 간결한 코드로 구현할 수 있습니다.
    두 가지 방식의 선택은 사용하는 상황과 개발자의 선호도에 따라 달라집니다. 
    메모리 사용량과 계산 효율성을 고려할 때, 첫 번째 방식이 더 효율적일 수 있습니다. 
    그러나 코드의 가독성과 간결성을 중시한다면 두 번째 방식이 선호될 수 있습니다.
   */
  }

  return seq[n];
}
let p1 = padovanSequence(11);
console.log(p1);
# 빈 리스트 만들기 
dp = [0] * 101

# 초기값 설정
dp[1] = 1
dp[2] = 1
dp[3] = 1

# 점화식 기반 계산값 적용하기
for index in range(0, 98):
    dp[index + 3] = dp[index] + dp[index + 1]

# 특정 입력값에 따른 계산값을 리스트에서 추출
print (dp[6])
print (dp[12])

3
16
profile
CHOYEAH
Move fast & break things
이전 포스트

Graph

다음 포스트

BFS (Breadth-First Search)

post-custom-banner

0개의 댓글