꼭 알아야하는 코딩 테스트 유형: 3) #Dynamic_Programming

• 이번에는 코딩 테스트에서 중요한 유형인 'Dynamic Programming(다이나믹 프로그래밍)'에 대해 알아보겠습니다. 다이나믹 프로그래밍은 큰 문제를 작은 부분 문제로 나누어 해결하는 방법으로, 중복되는 계산을 피하면서 효율적으로 문제를 해결합니다. 다이나믹 프로그래밍은 많은 종류의 문제에서 사용되며, 최적화와 관련된 문제에 자주 활용됩니다.

 

Dynamic Programming이란?

• 다이나믹 프로그래밍은 큰 문제를 작은 부분 문제로 나누어 해결하는 방법입니다. 작은 부분 문제의 결과를 저장하고 활용하여 전체 문제의 해답을 도출합니다. 이 때, 중복되는 부분 문제가 있을 경우 해당 결과를 메모리에 저장하여 중복 계산을 피할 수 있습니다.
• 다이나믹 프로그래밍은 최적 부분 구조(Optimal Substructure)와 중복되는 부분 문제(Overlapping Subproblems)라는 두 가지 조건을 만족해야 합니다.

 

Dynamic Programming 접근법

1. 문제 이해와 제약 사항 파악: 주어진 문제를 정확하게 이해하고, 입력 조건과 제약 사항을 파악해야 합니다.
2. 점화식 도출: 큰 문제를 작은 부분 문제로 나누기 위한 점화식(Recurrence Relation)을 도출합니다. 작은 부분 문제들 간의 관계식으로서 현재 상태와 이전 상태들 사이의 관계를 정의합니다.
3. 메모리 제작과 초기화: 작은 부분 문제들의 결과 값을 저장하기 위한 메모리(일반적으로 배열 또는 맵)를 생성하고 초기값으로 설정합니다.
4. 작은 부분 문제 해결: 가장 작은 크기부터 시작하여 작은 부분문자열부터 차례대로 계산하여 전체 결과 값을 얻습니다.
5. 상향식(bottom-up) 또는 하향식(top-down): 다이나믹 프로그래밍 알고리즘은 상향식(bottom-up) 또는 하향식(top-down)으로 구현할 수 있습니다. 상향식은 작은 부분 문제부터 차례대로 해결하면서 결과를 저장하는 방식이며, 하향식은 큰 문제를 작은 부분 문제로 나누어 해결하는 재귀적인 방식입니다.
6. 메모이제이션(Memoization): 중복되는 부분 문제의 결과를 메모리에 저장하여 중복 계산을 피할 수 있습니다. 이전에 계산한 값을 활용하여 필요한 경우 다시 계산하지 않고 저장된 값을 사용합니다.
7. 최적화 기법: 다이나믹 프로그래밍 알고리즘을 최적화하기 위해 필요한 기법들을 활용할 수 있습니다. 예를 들어, 공간 복잡도를 줄이기 위해 슬라이딩 윈도우(Sliding Window) 기법을 사용하거나, 점화식에서 필요한 부분만 계산하는 등의 최적화가 가능합니다.
8. 시간 복잡도 분석과 최적화: 다이나믹 프로그래밍 알고리즘의 시간 복잡도는 부분 문제의 개수와 각 부분 문제의 계산 시간에 의해 결정됩니다. 따라서 어떤 접근 방법과 최적화 기법을 선택하느냐에 따라 성능 개선 여부가 결정됩니다.

•  예시로 몇 가지 관련된 문제 유형과 접근 방법을 살펴보겠습니다.

 

피보나치 수열

•  주어진 숫자 n에 대해 피보나치 수열의 n번째 항을 구하는 문제입니다.

def fibonacci(n):
    if n <= 1:
        return n
    
    memo = [0] * (n + 1)
    memo[1] = 1
    
    for i in range(2, n + 1):
        memo[i] = memo[i - 1] + memo[i - 2]
    
    return memo[n]

• 위 코드는 주어진 n에 대해 피보나치 수열의 n번째 항을 구하는 함수입니다. 보텀-업 방식으로 작은 부분 문제들을 순차적으로 해결하며, 중간 결과 값을 저장하기 위해 memo 리스트를 사용합니다.

 

배낭(Knapsack) 문제

• 주어진 무게 제한과 각 물건의 가치와 무게가 주어졌을 때, 배낭에 넣을 수 있는 최대 가치를 구하는 문제입니다.

def knapsack(weights, values, capacity):
    n = len(weights)
    
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for j in range(1, capacity + 1):
            if weights[i - 1] > j:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]])
    
    return dp[n][capacity]

• 위 코드에서 weights 리스트는 각 물건의 무게 정보가 담겨있고, values 리스트는 각 물건의 가치 정보가 담겨 있습니다. 함수 실행 시 주어진 용량인 capacity에 따라 배낭에 넣을 수 있는 최대 가치인 dp[n][capacity] 값을 반환합니다.

 

1912번: 연속합

  문제   

• n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.
• 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

 

  해결 방법   

• 이 문제는 동적 프로그래밍을 활용해 해결할 수 있는 문제입니다. 연속된 합의 최댓값을 구하는 것이 목표이므로, DP 테이블에 각 위치에서 연속된 합의 최댓값을 저장하고, 이를 통해 전체 최댓값을 구할 수 있습니다.
  

# 입력
n = int(input())
seq = list(map(int, input().split()))

# DP 테이블 초기화 및 첫 번째 값 설정
dp = [0] * n
dp[0] = seq[0]

# DP 수행
for i in range(1, n):
    dp[i] = max(seq[i], dp[i-1] + seq[i])

# 결과 출력
print(max(dp))

• 이 문제는 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하는 문제입니다. DP를 사용하여 해결하기 위해서는 이전에 계산한 합(dp[i-1] + array[i])과 현재의 수(array[i]) 중 더 큰 값을 dp[i]에 저장합니다. 이렇게 하면 dp 배열은 각 위치에서 가능한 최대의 연속합을 저장하게 됩니다.
• 이 문제에서 점화식은 다음과 같습니다.

dp[i] = max(dp[i-1] + array[i], array[i])

• 첫 번째 원소에 대한 초깃값 설정은 다음과 같습니다.

dp[0] = array[0]

• 그리고 반복문을 통해 각 위치에서 가능한 최대 연속합을 구합니다.

 

11055번: 가장 큰 증가하는 부분 수열

  문제   

• 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.
• 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

 

  해결 방법  

• 이 문제도 동적 프로그래밍을 활용해 해결할 수 있습니다. 가장 큰 증가하는 부분 수열의 합을 구하는 것이 목표이므로, DP 테이블에 각 위치에서의 증가하는 부분 수열의 최대 합을 저장할 수 있습니다.

# 입력
n = int(input())
seq = list(map(int, input().split()))

# DP 테이블 초기화
dp = [x for x in seq]

# DP 수행
for i in range(n):
    for j in range(i):
        if seq[i] > seq[j]:
            dp[i] = max(dp[i], dp[j] + seq[i])

# 결과 출력
print(max(dp))

• 이 문제는 주어진 배열에서 증가하는 부분 수열 중 가장 큰 합을 구하는 문제입니다. 이전 값들과 비교하여 현재 값이 더 클 경우, 해당 인덱스의 DP 값과 비교하여 더 큰 값을 DP 값으로 설정합니다.
•  점화식은 다음과 같습니다.

if array[j] < array[i]: 
    dp[i]=max(dp[j]+array[j], dp[j])

• 첫 번째 원소에 대한 초깃값 설정은 다음과 같습니다.

dp[0] = array[0]

• 그리고 반복문을 통해 각 위치에서 가능한 가장 큰 증가하는 부분 수열의 합을 구합니다.

 

• DP는 복잡하고 어려워 보일 수 있지만, 한번 이해하면 많은 도움이 되는 알고리즘 기법입니다. 작은 부분부터 시작해서 전체 해결책으로 나아가는 방법, 그것이 바로 DP입니다.