Python | 동적계획법(Dynamic Programming)

복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법입니다.

 

장점:

- 효율성: 중복 감소

- 명확한 구조: 문제 분할

- 범용성: 최적화 문제에 적용 가능

 

단점:

- 메모리 사용량: 중간 계산 결과 저장을 위한 메모리 사용

- 초기 설계 복잡성: 부분 문제 해결 방법 설계에 대한 복잡성

- 적용 제한성: 최적 부분 구조 + 중복되는 부분 문제의 특성일 때 사용 가능

 

# 아래 풀이는 상향식 접근법(Bottom-Up Approach)을 사용하여 가장 작은 하위 문제를 반복문으로 저장해가며 문제를 풀이했습니다.

 

# 동적 계획법의 예

- 피보나치 수열

# 프로그래머스 정수 삼각형

def solution(triangle):
    idx = len(triangle) - 1
    
    while idx:
        for i in range(idx):
            triangle[idx-1][i] += max(triangle[idx][i], triangle[idx][i+1])
        idx -= 1
     
    return triangle[0][0]

 

> 문제를 읽을 때 위에서부터 아래로 생각해보게 되어서 처음에 헤맸는데 아래로부터 푸는 방법이 훨씬 간단하고 쉬웠습니다.

 

1. 그림은 삼각형 모양을 보여주는 반면, 코드를 그대로 적어보면 아래와 같은 배열의 구조를 지닙니다.

[7]
[3, 8]
[8, 1, 0]
[2, 7, 4, 4]
[4, 5, 2, 6, 5]

 

2. 그래서 다음의 단서를 반대로 생각해보면, 맨 밑에서 두 값 중 가장 큰 값을 위의 값과 더해나가면 최대값을 구해나갈 수 있습니다.

아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능

 

3. for 반복문은 같은 층에서의 인접한 값들 중 최대값과 윗층의 값을 더합니다.

4. while 반복문은 한 층씩 올라가는 역할을 합니다.

5. 최종적으로 최대값을 순차적으로 구할 수 있습니다.