사용자 도구

사이트 도구


ps:다이나믹_프로그래밍

동적 계획법 (Dynamic Programming)

  • 기본 개념은 wikipedia 참고
  • 정확히는 최적 부분 구조(Optimal Substructure)를 지닌 중복된 하위 문제들(Overlapping Subproblems)을 분할 정복으로 풀이하는 문제해결 패러다임이다.
  • 대충 답에 대한 공식을 점화식으로 표현해서 그걸 갖고 계산하면 DP라고 생각해도 별 문제 없고, 어떤 문제가 DP로 풀어야 하는 문제라는 것을 알게 되면 점화식을 세워보려고 시도하면 된다. 키워드는 '점화식'이다.

상향식과 하향식

  • 상향식 - bottom-up - Tabulation
  • 하향식 - top-down - Memoization
  • 기본적으로는 상향식이 빠르고 코드도 심플하니, 디폴트로는 상향식을 쓰는걸로 하자.
  • 하향식을 쓰는게 나을때
    • 점화식의 인덱스가 자연수들로 평범하게 떨어지지 않아서 어디서부터 시작해야 할지 고민하기 복잡할때.
      • 집합이나 트리에 대한 DP등..
    • 본 문제를 푸는 데에 부분문제중 일부만이 필요할 때. 상향식은 모든 부분문제에 대한 테이블을 전부 채워가면서 올라가는데, 사실 모든 테이블을 전부 채우지 않고도 문제가 풀릴수 있는 경우

1차원 DP

인접 k항에 대한 점화식

  • 슬라이딩 윈도우라 불리는 방법으로 공간복잡도를 O(k)에 처리할수 있다.
    • 하향식에서는 이 기법이 불가능하다
  • k=1일 경우는 클로즈드 폼으로 변환될 수 있어서 DP조차 필요없는 경우가 대부분이라 보통 접하게 되는 것은 k>=2일 때
  • 이런 형태에 대해서는 변수명을 통일해서 쓰려 한다.
    • k=1일때는, dp_cur과 dp_prev를 사용한다. A(n) = f(A(n-1)) 이면 dp_cur = func(dp_prev) 이렇게 적는 식이다
    • k>=2일때는, dp_cur과 dp 리스트를 사용한다. A(n) = f(A(n-1), A(n-2))이면 dp_cur = func(dp[-1], dp[-2]) 이렇게..
      • k가 커지면 리스트 대신 deque를 쓰는게 더 편할수도 있다
  • 그래서 코드는 보통 이렇게 된다
    • dp, dp_cur = [A_0, A_1], A_2
      for _ in range(N-1):
          dp[-1], dp[-2] = dp_cur, dp[-1]
          dp_cur = func(dp[-1], dp[-2])    
      return dp_cur    # A(N) == dp_cur
    • dp, dp_cur = colletion.deque([A_0, A_1, ..., A_(i-1)]), A_i
      for _ in range(N-i):
          dp.popleft()
          dp.append(dp_cur)
          dp_cur = func(dp[-1], dp[-2])    
      return dp_cur    # A(N) == dp_cur

선형 동차 점화식

  • 만약 f가 선형 함수라면, DP로 푸는 대신, 행렬의 거듭제곱으로 변환하여 더 빠르게 계산 가능.
    • 보통 최댓값이나 최솟값을 찾는 문제라면, f에 min이나 max가 들어가므로 해당이 안되지만, 모든 가짓수를 찾는 문제라면 f가 선형 함수가 되어서 이 방식을 적용할 수 있는 경우가 많다. 선형 점화식 참고

2차원 DP

  • 2개의 변수에 대한 식으로 표현되는 경우. 이 경우의 구현은 2차원 배열을 채워나가는 식으로 계산하게 된다.

행 순서대로 채우는 DP

  • 흔한 경우.
  • 어떤 행에 대한 값이 이전 행에 대한 값들로 계산되는 형태
    • dp[i][j] = f(g(dp[0][0]), …, g(dp[0][N]), g(dp[1][0]), …, g(dp[1][N]), …, g(dp[i-1][0]), …, g(dp[i-1][N]))
  • 대충 이렇게 된다.
    • dp = [[0] * M for _ in range(N)]
          for i in range(N):
              for j in range(M):
                  dp[i][j] = some_func(dp[:i], dp[i][:j])
          
          print(dp[N - 1][M - 1])

인접 k개 행에 대한 점화식

  • i번째 행에 대한 값이 i-1, i-2, …, i-k 행만 갖고 계산 가능한 상황. 이때는 N*M의 테이블을 만들 필요 없이, K*M의 테이블만으로 충분하다
  • 대부분은 k=1인 경우인데, 이때는 그냥 1차원 배열만으로 된다.
  • k=1 일때, 코드는 대충 이렇게 된다.
    • dp_cur = [0] * M
          for _ in range(N):
              dp_cur, dp_prev = [0] * M, dp_cur
              for i in range(M):
                  for j in range(N):
                      val = update(val, func(dp_prev[j]))
                  dp_cur[i] = val
          
          print(dp_cur[M - 1])

테이블이 sparse한 경우

  • 몇개의 셀에만 값이 채워져있고 나머지는 0으로 채워져 있는 상태에서, 값이 채워진 칸의 주변에서만 업데이트가 일어나는 형태.
  • 이때는 테이블을 다 만들고 모든 셀을 iterate하는 것보다 그냥 map을 이용해서 값이 채워진 셀만 유지하는 것이 속도면에서 효율적인 경우가 있다
  • 대표적인 예로는 0-1 knapsack 문제가 있다.
    • 이 문제의 BOJ 버전인 평범한 배낭에서 좀더 구체적인 예시가 설명되어있다
  • 대충 코드는 이런 식이다
    • dp_cur = {0: 0}
          for i in range(N):
              dp_cur, dp_prev = dp_cur.copy(), dp_cur
              for prev_i, prev_v in dp_prev.items():
                  cur_i, cur_v = func(prev_i, prev_v)
                  dp_cur[cur_i] = cur_v
          
          print(dp_cur[M-1])

구간 분할 방식에 관한 DP

  • 2개의 변수가 어떤 구간의 시작 인덱스와 끝 인덱스인 경우. 어떤 구간에 대한 값이 그 안에 포함된 더 짧은 구간에 대한 값들로 계산되는 형태. 말하자면 점화식이 다음처럼 생긴 형태.
    • dp[i][j] = f_k(g(dp[i][k], dp[k][j], i, k, j))

집합에 대한 DP

  • 어떤 집합 S에 대한 함수값이, 그 부분집합들에 값에 대한 식으로 계산되는 경우들이다.
  • 전체집합의 부분집합들을 표현하는 것을 비트마스킹으로 처리하는 것은 유명한 테크닉이다. 집합을 정수형으로 표현하는 것도 가능하고, 집합과 그 부분집합간의 관계가 키값의 대소관계로 유지되는 것도 상향식 재귀를 가능하게 해준다. 하지만, 그냥 집합의 튜플 자체를 key로 잡고 재귀로 표현하는 것이 가독성에서는 오히려 나은 점도 있다보니, 아직은 그때그때 내키는대로 쓰는 중.. 어느쪽을 확정적으로 사용할지는 아직 고민중.

퍼뮤테이션에 대한 DP

  • n개의 원소를 배열하는 순서에 따라 값이 결정되는 함수의 최대값을 구하는 형태.
  • 그냥 전부 다 해보려면 n!가지의 배열법을 다 해봐야 하지만, 남은 원소에 대한 함수값이 앞선 배치 순서에 영향을 받지 않는다면, dp[S] = max(f(x) + dp[S - x]) 와 같이 쓸 수 있고, 이것은 S의 모든 부분집합 2^|S|개에 대한 테이블을 만들고, 각각을 O(|S|)에 채우면 되므로 O(|S| * 2^|S|)로 풀수 있다.

SOS DP

  • 링크 참고
  • 이름이 거창한데, 그냥 Sum over Subsets의 약자로.. f[S] = sum(g[S - x] for x in S) 와 같은 형태로 된 f를 모든 집합에 대해서 구하는 방법이다
    • 예를 들면 f[{x,y,z}] = g[{y,z}] + g[{x,y}] + g[{y,z}] 같은 형태..
  • 비트마스크로 바꿔서 생각해보면, N 이하 모든 자연수 i에 대해서, i & x = i 인 모든 x의 함수값의 합을 구하는 것과도 동일하다
  • DP를 이용해서, {전체 원소의 갯수} * {집합의 갯수} 만큼의 테이블을 이용해서 O(NlogN)에 풀 수 있다 (N은 집합의 갯수). 그리고 이터레이션 순서를 잘 조절하면 공간복잡도 O(N)에 굉장히 깔끔한 코드로 정리할 수 있다. (코드는 깔끔하지만 파이썬에서의 실행속도는 매우 느리다..)
  • for i in range(n.bit_length() + 1):
        for num in range(n + 1):
            if num & (1 << i):
                dp[num] += dp[num ^ (1 << i)]

관련 문제

최적화 테크닉

토론

댓글을 입력하세요:
L R R P Z
 
ps/다이나믹_프로그래밍.txt · 마지막으로 수정됨: 2021/03/02 04:55 저자 teferi