[알고리즘] 다이나믹 프로그래밍 : 작은 것부터 시작하자!

작은 것.... 밍기적....

1. 동적 프로그래밍(DP) 소개

동적 프로그래밍은 복잡한 문제를 작은 부분 문제로 나누어 해결하는 방법입니다. 주로 최적화 문제에 사용되며, 메모이제이션 또는 테이블 방식으로 중복 계산을 줄입니다. 워낙 유명한 해결법이라 저 보다 잘 설명된 글이 굉장히 많습니다. 여기서는 재미로 대략적인 내용을 파악하는 걸로 보고 가시면 좋을 듯 합니다.

2. 가장 긴 증가하는 부분 수열(LIS) 문제 해결

2.1 LIS의 정의 및 문제 설명

LIS는 주어진 수열에서 순서를 유지하면서 가장 긴 증가하는 부분 수열을 찾는 문제입니다.

2.2 동적 프로그래밍을 이용한 LIS 알고리즘

동적 프로그래밍을 사용한 LIS 알고리즘은 O(n^2)의 시간 복잡도를 가집니다. 각 요소에 대해 그 이전 요소들과 비교하여 dp 테이블을 갱신합니다. 생각보다 시간 복잡도가 낮지는 않습니다. 뿐만 아니라 dp 테이블으로 공간 복잡도도 가지고 있는 것도 있습니다. 그럼에도 불구하고 사용하는 이유는 뒤에 보시면 알 수 있습니다.

2.3 이분 탐색을 이용한 LIS 최적화 알고리즘

추가적으로 이분 탐색을 활용한 LIS 알고리즘은 O(n \log n)의 시간 복잡도를 가집니다. 각 요소를 올바른 위치에 삽입하여 LIS를 유지합니다. 이 부분은 다음 포스팅에 설명해보도록 하겠습니다.

2.4 파이썬 코드 예제 및 설명

def longest_increasing_subsequence(arr):
    n = len(arr)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

3. 연속된 부분 수열의 최대 합 문제 해결 (카데인 알고리즘)

3.1 문제 설명 및 접근 방법

주어진 수열에서 연속된 부분 수열 중 그 합이 가장 큰 것을 찾는 문제입니다.

3.2 카데인 알고리즘의 원리 및 파이썬 코드

카데인 알고리즘은 선형 시간복잡도 O(n)로 문제를 해결합니다. 어찌보면 정말 단순한 코드였습니다. 간략하게 설명해보면 숫자 배열에서 앞에서부터 하나씩 더해보면서 그 순간에서 가장 큰 값과 max_global값과 비교하며 찾는 것입니다.

def max_subarray_sum(arr):
    max_current = max_global = arr[0]
    for num in arr[1:]:
        max_current = max(num, max_current + num)
        if max_current > max_global:
            max_global = max_current
    return max_global

4. 제곱수의 합 문제 해결

4.1 문제 설명 및 접근 방법

주어진 자연수를 제곱수들의 합으로 나타낼 때, 그 제곱수들의 최소 개수를 구하는 문제입니다.

4.2 동적 프로그래밍을 이용한 제곱수의 합 알고리즘

동적 프로그래밍을 사용하여 제곱수들의 최소 개수를 계산합니다. 여기서 주의해야할 점은 최소 갯수와 가장 큰 제곱수들로 포함하는 것이 같지 않다는 것입니다.

저는 처음에 N에서 가장 큰 제곱수를 빼면서 찾아가는 게 최소 갯수로 생각했었는데 이것이 아님을 분명히 알고 있어야합니다. 추가적으로 이에 관해서 많은 질문 역시 있었기에 궁금하시다면 질문 게시판의 내용을 한번 참고해는 것도 좋은 방법 같습니다.

def min_square_sum(n):
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = i
        j = 1
        while j * j <= i:
            dp[i] = min(dp[i], dp[i - j * j] + 1)
            j += 1
    return dp[n]

5. 정수를 정수들로 분할하는 문제 해결

5.1 문제 설명 및 접근 방법

정수 n을 k개의 정수로 나타내는 방법의 수를 구하는 문제입니다.

5.2 동적 프로그래밍을 이용한 분할 문제 알고리즘

동적 프로그래밍을 사용하여 n을 k개의 정수로 나타내는 방법의 수를 계산합니다. 

def number_of_ways(n, k):
    dp = [[0] * (n + 1) for _ in range(k + 1)]
    for j in range(n + 1):
        dp[1][j] = 1
    for i in range(2, k + 1):
        for j in range(n + 1):
            dp[i][j] = dp[i-1][j]
            if j > 0:
                dp[i][j] += dp[i][j-1]
    return dp[k][n] % 1000000000

6. 결론 및 추가 문제 추천

6.1 동적 프로그래밍을 통한 문제 해결의 장점

동적 프로그래밍은 복잡한 문제를 효율적으로 해결할 수 있는 강력한 도구입니다. 메모이제이션과 테이블 방식으로 중복 계산을 줄여 최적화된 해를 제공합니다. 앞에서 시간, 공간 복잡도가 낮지는 않다고 말씀드렸는데 DP가 아니면 그마저도 지키기 힘든 시간, 공간 복잡도이기에 잘 알아둘 필요가 있는 해결방법입니다.

다만 동적 프로그래밍을 이용하기 위해서 필요한 조건들이 있지만 제일 단순하게는 큰 문제들이 작은 숫자의 문제들로 쪼개질 수 있다는 것만 확인했다면 바로 DP를 이용해서 풀 수 있을 것입니다. 

6.2 추가로 도전해볼 만한 동적 프로그래밍 문제들

• 동전 교환 문제
• 배낭 문제
• 최장 공통 부분 수열 (LCS)
• 계단 오르기 문제