dp (dynamic programming)

Konseo·2023년 9월 4일
0

알고리즘

목록 보기
14/21
post-custom-banner

다이나믹 프로그래밍

개요

  • 동적 계획법 으로도 불린다

    🙋🏻‍♀️ 일반적인 프로그래밍 분야에서의 동적(Dynamic)이란 어떤 의미일까?

    자료구조에서 동적 할당(Dynamic allocation)은 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법 을 의미한다.

    그러나 다이나믹 프로그래밍에서의 다이나믹은 별 의미 없이 사용된 단어 라고 한다😅

  • 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다

  • 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.

    • 메모이제이션 (Memoization)
      • 한 번 계산한 결과를 메모리 공간에 메모(저장)하는 기법
      • 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다
      • 값을 기록해둔다는 점에서 캐싱(caching)이라고도 한다
  • 두 가지 방식이 존재

    • 바텀 업(bottom up) 방식
    • 탑 다운(top down) 방식

조건

다이나믹 프로그래밍은 아래의 2가지 조건을 만족할 때 사용할 수 있다.

  1. 최적 부분 구조 (Optimal Substructure)

    • 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
  2. 중복되는 부분 문제 (Overlapping Subproblem)

    • 동일한 작은 문제를 반복적으로 해결해야 한다.

따라서 보통 규칙을 잘 파악하여 dp 테이블의 점화식을 도출해내는 것이 dp의 핵심이다.

바텀업 vs 탑다운

피보나치수열을 바텀업 방식과 탑다운 방식으로 각각 구현해보자
참고로 결과 저장용 리스트는 DP 테이블 이라고 불린다.

  1. 바텀업 방식

    • 상향식으로도 불린다.
    • 다이나믹 프로그래밍의 전형적인 형태이다.
    • 피보나치 수열 코드 (bottom up)
    dp=[0]*100
    
    dp[1]=1
    dp[2]=1
    n=99
    
    for i in range(3,n+1):
    	dp[n]=dp[n-1]+dp[n-2]
    
    print(d[n]))
  2. 탑다운 방식

    • 상향식으로도 불린다.
    • 피보나치 수열 코드 (top down)
    dp=[0]*100
    
    dp[1]=1
    dp[2]=1
    n=99
    
    def fibo(n):
    	if n==1 or n==2:
      	dp[n]=1
      if dp[n]!=0:
      	return dp[n]
      dp[n]=fibo[n-1]+fibo[n-2]
      return dp[n]
    
    print(fibo(n)))

다이나믹 프로그래밍 vs 분할 정복

  1. 공통점
  • 최적 부분 구조를 가질 때 사용할 수 있다
    • 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황
  1. 차이점
  • 부분 문제의 중복
    • 다이나믹 프로그래밍 문제에서는 각 부분의 문제들이 서로 영향을 미치며 부분 문제가 중복된다.
    • 분할 정복 문제에서는 동일 부분 문제가 반복적으로 계산되지 않는다.
      • 예시 : 퀵정렬
        • 한 번 기준 원소(pivot)가 자리를 변경해서 자리를 잡으면 그 기준 원소의 위치는 바뀌지 않음
        • 분할 이후에 해당 피벗을 다시 처리하는 부분 문제는 호출하지 않음

다이나믹 프로그래밍 문제에 접근하는 방법

  • 주어진 문제가 다이나믹 프로그래밍 문제인 지 파악을 하는 것이 중요하다
  • 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는 지 검토한다
    • 다른 알고리즘으로 풀이 방법이 떠오르지 않는다면 다이나민 프로그래밍 고려해본다
  • 보통은 바텀업 방식으로 점화식을 활용해 dp 풀이를 진행한다
  • 탑다운 방식의 경우 일단 재귀로 (비효율적인) 완전 탐색 코드를 작성한 뒤에 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있다면 dp 테이블 등을 활용해 코드를 개선하는 방법을 사용할 수 있다

reference

profile
둔한 붓이 총명함을 이긴다
post-custom-banner

0개의 댓글