동적 계획법(DP) 알고리즘: 10분 만에 이해하기 (정수 삼각형 문제풀이)

자세한 내용은 영상으로 확인하세요! :)

프로그래밍을 배우면서 동적 계획법(Dynamic Programming, DP)에 대해 들어보셨을 겁니다. DP는 알고리즘 문제 해결에 매우 유용한 접근 방식입니다. 오늘은 정수 삼각형 문제를 예시로 들어 DP 알고리즘을 10분 만에 이해할 수 있도록 설명해 드리겠습니다.

동적 계획법(DP)이란?

동적 계획법은 복잡한 문제를 더 간단한 하위 문제로 나누어 해결하는 방법입니다. 이는 하위 문제들의 결과를 저장하고, 이를 바탕으로 전체 문제를 해결하는 방식입니다. DP는 중복 계산을 피하고, 효율적으로 문제를 해결할 수 있게 합니다.

다이나믹 프로그래밍의 필요성

다이나믹 프로그래밍은 수많은 경우의 수를 모두 고려해야 하는 문제의 수행 시간을 단축하기 위해 고안된 알고리즘입니다. 예를 들어, 최단 경로를 찾거나 최고 점수를 만들기 위한 문제를 풀 때 모든 조합을 다 따져보는 완전 탐색 방식은 시간이 많이 걸립니다. 하지만 DP를 사용하면 이러한 문제를 효율적으로 해결할 수 있습니다.

정수 삼각형 문제

정수 삼각형 문제는 다음과 같은 삼각형 형태의 숫자 배열이 주어졌을 때, 위에서부터 아래로 내려가면서 숫자를 더해 최대 합을 구하는 문제입니다.

예시 삼각형:
```
    7
   3 8
  8 1 0
2 7 4 4
4 5 2 6 5
```

DP를 활용한 문제 해결

1. 문제 구조 변환: 삼각형 모양의 배열을 직각 삼각형 형태로 변환하여 컴퓨터가 쉽게 이해할 수 있도록 합니다.
2. 중복 연산 줄이기: DP 배열을 만들어 각 위치까지 올 수 있는 최대 값을 저장합니다. 예를 들어, 첫 번째 숫자 7에서 시작하여 아래로 내려가면서 각 경로의 최대 값을 계산해 저장합니다.
3. 최적의 값 갱신: 한 번 계산한 결과를 배열에 저장하여 동일한 연산을 다시 하지 않도록 합니다. 예를 들어, 7에서 3을 더한 값 10을 저장하고, 다른 경로에서 7과 3을 다시 더하지 않습니다.

문제 해결 전략

1. 하위 문제 정의:

   각 위치에서의 최대 합을 계산합니다. 예를 들어, 삼각형의 맨 아래부터 시작하여 각 위치에서 위로 올라가며 최대 합을 계산합니다.

2. 점화식 설정:

   각 위치에서의 최대 합은 해당 위치의 값과 그 아래 두 위치의 값 중 큰 값을 더한 것입니다. 이를 점화식으로 표현하면 다음과 같습니다:
   ```
   dp[i][j] = triangle[i][j] + max(dp[i+1][j], dp[i+1][j+1])
   ```
   여기서 `dp[i][j]`는 위치 (i, j)에서의 최대 합을 의미합니다.

3. 초기화:

   삼각형의 맨 아래 행을 초기화합니다. 맨 아래 행의 값들은 그대로 dp 배열의 초기값이 됩니다.

4. 상향식 접근:

   맨 아래 행부터 시작하여 위로 올라가며 각 위치에서의 최대 합을 계산합니다.

예제 코드

다음은 파이썬으로 구현한 정수 삼각형 문제 해결 코드입니다:
```python
def max_path_sum(triangle):
    # 맨 아래 행을 초기화
    dp = triangle[-1]
    
    # 아래 행부터 위로 올라가며 계산
    for i in range(len(triangle) - 2, -1, -1):
        for j in range(len(triangle[i])):
            dp[j] = triangle[i][j] + max(dp[j], dp[j + 1])
    
    # 맨 위의 최대 합 반환
    return dp[0]

# 삼각형 예시
triangle = [
    [7],
    [3, 8],
    [8, 1, 0],
    [2, 7, 4, 4],
    [4, 5, 2, 6, 5]
]

print(max_path_sum(triangle))  # 출력: 30
```

다이나믹 프로그래밍을 적용해야 하는 문제 유형

다이나믹 프로그래밍은 특정 유형의 문제에만 국한되지 않고, 다양한 문제를 최적화할 때 고려될 수 있는 알고리즘입니다. 코딩 테스트나 알고리즘 문제를 보고 이게 DP로 풀어야 할 문제인지 판단하는 기준을 두 가지로 정리해보았습니다.

1. 경우의 수가 너무 많은 문제

첫 번째 기준은 DFS나 BFS로 풀 수는 있지만 경우의 수가 너무 많은 문제입니다. 예를 들어, 정수 삼각형 문제를 생각해보세요. 작은 크기의 삼각형이라면 DFS로도 풀 수 있지만, 삼각형의 크기가 커지면 경우의 수가 기하급수적으로 늘어나기 때문에 사실상 불가능해집니다. 이런 문제를 풀 때 최악의 경우의 수를 개선하는 가장 쉬운 방법은 직접 계산해보는 것입니다.

정수 삼각형 문제의 경우, 한 줄짜리 삼각형부터 경우의 수를 계산해보면, 한 줄일 때는 1가지, 두 줄일 때는 2가지, 세 줄일 때는 4가지, 네 줄일 때는 8가지의 조합이 존재합니다. 이를 통해 경우의 수가 2의 제곱수로 증가한다는 패턴을 확인할 수 있습니다. 만약 삼각형의 줄 수가 500이라면 최악의 경우의 수는 2^499가 되고, 이는 어마어마한 값이 됩니다. 이 정도의 경우의 수는 DFS나 BFS로는 절대 해결할 수 없기 때문에 DP를 사용해야 합니다.

2. 중복 연산이 많은 문제

두 번째 기준은 경우의 수들의 중복 계산이 많은 문제입니다. 이런 문제는 DFS로 풀게 되면 모든 조합을 매번 다 시도해봐야 하기 때문에 시간이 많이 소요됩니다. 그렇기 때문에 각 위치까지 올 수 있는 최적의 값만 남겨놓고 나머지 조합은 버리는 방식으로 접근해야 합니다. 이렇게 하면 중복 연산을 줄일 수 있습니다. DP 문제를 몇 개 풀다 보면 중복 연산이 많은 문제를 쉽게 감지할 수 있게 됩니다.

다이나믹 프로그래밍 문제 해결 접근 방법

문제가 DP로 풀어야 할 문제라고 판단했다면 이제 풀기만 하면 되는데, 이것도 만만치 않습니다. DP는 최대한 많은 문제를 풀어보고, 다른 사람들의 풀이를 참고하면서 사고방식을 습득하는 것이 중요합니다. 처음부터 혼자서 해결하려고 하기보다는 30분 정도 고민해보고, 답이 나오지 않으면 다른 사람의 풀이를 참고하는 것을 추천드립니다.

DP를 풀 때는 현재 단계까지의 연산을 잘 기록해두고, 그 연산을 다시 하지 않으려면 어떤 정보를 남겨야 할지 고민하는 것이 중요합니다. 예를 들어, 정수 삼각형 문제에서는 각 위치까지 올 수 있는 최적의 값을 기록해두고, 이전 단계로 돌아가지 않도록 해야 합니다. 이렇게 최적의 답을 쌓아간다는 마음으로 프로그래밍을 하다 보면 자연스럽게 DP 사고방식을 익힐 수 있습니다.

DP는 스택이나 큐처럼 정형화된 알고리즘이 아닙니다. 따라서 같은 문제를 풀더라도 사람마다 다른 방식으로 구현할 수 있습니다. DP는 수행 시간을 단축할 수 있는 기법이기 때문에 그 기법을 구현하는 방법은 무궁무진합니다. 많은 문제와 풀이를 참고하고, 꾸준히 연습하다 보면 어느 순간 DP의 개념이 명확해질 것입니다.

결론

DP는 어려운 알고리즘입니다. 여러분만 어려운 것이 아니니 너무 낙담하지 마시고, 꾸준히 연습하시길 바랍니다. DP의 사고방식을 받아들이고, 문제를 많이 풀어보면서 경험을 쌓다 보면 어느 순간 이해할 수 있는 날이 올 것입니다. 끝까지 포기하지 마시고 도전해 보세요!

이 블로그 포스트가 여러분의 알고리즘 공부에 도움이 되길 바랍니다. 추가 질문이나 더 알고 싶은 내용이 있다면 댓글로 남겨 주세요!