[자료구조] 동적 계획법 - dp 2차원 배열로 좌표 이동하기 / Python 파이썬

 

동적계획법 (다이나믹 프로그래밍)에 대해서 코딩 문제는 많이 푼 것 같지만 여러 유형의 dp 에 대해 다뤄보지 못한 것 같아 포스팅한다.

 

본 게시글은 해당 게시글의 내용 파이썬으로 변경하였다. 

 

예를 들어 정수들이 저장된 nXn의 좌상단에서 우 하단 까지 이동하는 문제에서 오른쪽이나 하단으로만 이동이 가능하다는 조건으로 지나간 값들의 합이 최소가 되도록 하는 최적의 경로를 찾아보자.

 

 

 

 

0,0에서 i,j 까지 가는 방법은 2가지가 있다.

 

 i, (j-1)를 거쳐서 오거나 (i-1), j 로 오는 방법이다.

이렇게 거쳐서 오는 값들을 수식으로 확인해보면 다음과 같다.

그럼 파이썬으로 프로그래밍 하자.

 

 

def mat(i,j):
    if i == 1 and j == 1:
        return m[i][j]; # 외길로 판단하여 하나의 경우만 적용하여 계산
    elif i == 1:
        return mat(1,j-1) + m[i][j] # 왼쪽으로 이동
    elif j == 1:
        return mat(i-1,1) + m[i][j]
    else:
        min(mat(i-1,j),mat(i,j-1)) + m[i][j]

이와 같은 알고리즘에서 슈도 코드는 위와 같다.

방금전에 본 순환식을 그대로 코드로 옮긴 것이다.

물론 이렇게 하면 올바로 계산이 되겠지만, 상당히 비효율적인 코드이다.

왜냐하면 값을 구하기 위해 중복되는 요소가 많이 발생하기 때문이다.

따라서 메모이제이션이나 bottom up 방식을 사용해서 보다 효율적인 코딩을 할 수 있다.

 

def mat(i,j):
    if L[i][j]!= 1:
        return L[i][j];
    if i == 1 and j == 1:
        L[i][j] = m[i][j]
    elif i == 1:
        L[i][j] = mat(1,j-1) + m[i][j]
    elif j == 1:
        L[i][j] = mat(i-1,1) + m[i][j]
    else:
        L[i][j] = min(mat(i-1,j),mat(i,j-1)) + m[i][j]
        return L[i][j]

메모이제이션을 활용하여 보다 개선된 코드가 만들어진다.

메모이제이션 기법에서 항상 사용하듯, 배열로 캐시를 만든다.

이렇게 만들어진 캐시는 -1로 초기화 되며, 조건문은 -1이 라면 캐싱이 안된 상태이므로 연산을 진행하고,

-1이 아니라 다른 값이 들어 있다면 연산 없이 기존에 배열에 저장된 값을 리턴하게 된다.

 

위의 비효율적인 코드와 비교해 보자면

기존의 코드는 저장 없이 리턴을 바로 하게되는 것이며, 메모이제이션은 캐시에 저장하여 리턴하므로

중복된 계산이 사라지며 깔끔하고 효율적으로 변한다는 것이다.

 

- 바텀업

기본적인 순환식 설계 후 dp를 for문으로 돌림

 

reference

https://new93helloworld.tistory.com/221

[알고리즘] 동적 계획법(Dynamic Programming) - 2