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

이번 정리는 다이나믹 프로그래밍에 관한 것이다. 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간을 효율적으로 줄이는 프로그래밍 기법을 의미한다. 다이나믹 프로그래밍을 할 경우, 동적 할당을 사용하는 경우가 종종 있다. 프로그램이 실행되는 도중에 메모리를 할당한다는 점에서 메모리 제한을 고려할 필요성이 있다.

다이나믹 프로그래밍

• 한번 푼 문제를 메모리에 저장하며, 중복되는 문제에 걸리는 수행시간을 줄이는 프로그래밍 기법.

• 최적 부분 구조와 중복되는 부분 문제에 관련

• 큰 문제를 작은 문제로 나눌 수 있으며, 동일한 작은 문제에 대한 정답은 큰 문제에서도 동일하게 사용할 수 있을 때 다이나믹 프로그래밍을 사용 가능

• 분할 정복 알고리즘과의 차이점은 부분 문제 중복 여부

• 작은 문제의 정답을 저장한 테이블은 DP 테이블

• 상향식 풀이와 하향식 풀이가 있으나, 보통은 하향식 풀이로 접근

최장 증가 부분 수열(LIS) 알고리즘

• 원소가 n개인 배열의 일부 원소를 추출하여 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고 그 길이가 최대인 부분 수열

• 이진 탐색과 다이나믹 프로그래밍으로 접근 가능하나, 이 절에서는 다이나믹 프로그래밍에 관해서 서술

• [10, 20, 10, 30, 20, 50]일 경우 LIS는 [10, 20, 30, 50]

• 풀이코드

  def LIS(array, N): # array는 배열, N은 원소의 개수
      dp = [0] * N # dp 테이블 생성
      for i in range(N):
          dp[i] = 1
          for j in range(i):
              if array[i] > array[j]:
                  dp[i] = max(dp[i], dp[j]+1)
      return dp
  

예시문제

백준 1309 우리

백준 2293 동전1

백준 2294 동전2

백준 2565 전깃줄

백준 11053 가장 긴 증가하는 부분 수열

백준 11722 가장 긴 감소하는 부분 수열

백준 14002 가장 긴 증가하는 부분 수열 4