[DP 개념] #2_동적계획법(1)

인프런 사이트의 영리한 프로그래밍을 위한 알고리즘 강좌를 참고하여 글을 작성하였습니다.

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%95%EC%A2%8C/lecture/4126?tab=note 

영리한 프로그래밍을 위한 알고리즘 강좌 - 인프런 | 학습 페이지

 

동적계획법

---

 

순환식을 계산의 중복없이 효과적으로 푸는 방법

 

동적계획법의 특징

---

 

- 일반적으로 최적화 문제 혹은 카운팅 문제에 적용됨

- 주어진 문제에 대한 순환식을 정의한다.

- 순환식을 memoization 혹은 bottom-up 방식으로 푼다

 

동적계획법의 조건

---

큰 문제를 작은 문제로 나누어 푸는 문제를 일컫는 말이다.

분할정복과 비슷한 것 같지만 동적계획법의 차이점은 작은 문제들의 중복이 일어난다.

하지만 분할정복은 큰 문제를 해결하기 어려워 단지 작은 문제로 나누어 푸는 방법이다.

 

동적계획법의 조건을 정리하자면

 

- 작은 문제들의 반복이 일어남

- 같은 문제는 구할 때마다 정답이 같다.

 

참고자료

---

 

https://galid1.tistory.com/507

알고리즘 - Dynamic Programming(동적프로그래밍)이란?

 

예제를 통해 알아보기

---

정수들이 저장된 n * n 행렬이 있다. 단, 오른쪽이나 아래쪽 방향으로만 이동할 수 있고, 방문하는 칸에 있는 정수들의 합이 최소화되도록 하라. 

문제를 푸는 키

---

(i,j)에 도달하기 위해서는 (i,j-1) 혹은 (i-1,j)를 거쳐야 한다. 또한 (i,j-1) 혹은 (i-1,j)까지는 최선의 방법으로 이동해야한다.

 

여기서 mij는 ij 위치에 있는 정수이다.

 

이것을 자바 코드로 바꿔보겠다. 여기서 함수 mat은 L(i,j)를 구하는 함수이다. 

하지만 이렇게 코드를 짜면, 중복되는 계산이 생겨나게 돼서 굉장히 비효율적이게 된다. 

 

Memoization

---

public class DP {
    public int [][]m;
    public int [][]L;
 
    public int mat(int i, int j) {
        if(m[i][j]!=-1) {
            return L[i][j];
        }
        else if(i==1&&j==1) {
            L[i][j]= m[i][j];
        }
        else if(i==1) {
            L[i][j]= mat(1,j-1)+m[i][j];
        }
        else if(j==1) {
            L[i][j]=mat(i-1,1)+m[i][j];
        }
        else {
            L[i][j]= Math.min(mat(i-1,j), mat(i,j-1))+m[i][j];
        }
        return L[i][j];
    }
 
}

2차원 배열인 L을 만들어 값을 저장해 놓는다. 2차원 배열인 L을 -1로 초기화해 놓았다고 가정한 것이다.

앞코드는 계산된 결과를 return 했지만, 메모이제이션 코드는 게산된 결과를 저장하기 때문에, 나중에 연산에서 계산된 결과가 필요할 때 다시 계산하는 것이 아닌 배열에 있는 수를 갖다쓰면 된다.

 

Bottom - up

---

 

특정한 순서가 있는게 아닌 순환식의 오른쪽의 값이 왼쪽값보다 항상 먼저 계산되어야한다.

 

위에 사진처럼, 28을 계산하려면 25와 31이 먼저 계산되어야 한다. 위 사진은 '행 우선' 순서로 계산한 것이다.

 

 

public class DP {
    public int [][]m;
    public int [][]L;
 
    public int mat() {
        int n=4;
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=n;j++) {
                if(i==1&&j==1) {
                    L[i][j]= m[i][j];
                }
                else if(i==1) {
                    L[i][j]=L[i][j-1]+m[i][j];
                }
                else if(j==1) {
                    L[i][j]=L[i-1][j]+m[i][j];
                }
                else {
                    L[i][j]= Math.min(L[i-1][j], L[i][j-1])+m[i][j];
                }
                
            }
        }
        
        
        return L[n][n];
    }
 
}

직접 풀어보기

---

아래와 같은 3*3 배열이 있다.  (1,1) 부터 (2,3) 까지 갈 때, 가장 최소의 정수 합은?

 

나는 Memoization 방식으로 문제를 해결해봤는데, L은 최소 정수의 합을 저장해놓는 배열로 생각했고, m은 배열의 위치를 보는데 사용했다. 

예를 들어 L[1][2] 이면 (1,1) 부터 (1,2)까지 갈 때  최소 정수의 합은 3이고, m[1][2]이면 (1,2)에 들어있는 숫자인 2이다.

 

 

L[2][3] = Math.min(L[1][3],L[2][2]) +m[2][3]이다. m[2][3]은 6이므로

 

Math.min(L[1][3],L[2][2])+6이 된다.

 

L[1][3]=L[1][2]+m[1][3]  즉, L[1][2]+3 

L[1][2]=L[1][1]+m[1][2]이므로 m[1][1]+m[1][2]이다 

결론적으로 L[1][3]=m[1][1]+m[1][2]+m[1][3] 이므로 6이 된다.

 

L[2][2]=Math.min(L[1][2],L[2][1])+m[2][2] 

L[1][2]는 3이고, L[2][1]는 5이므로 최소값은 3이다.

3+m[2][2] =8이 된다.

 

6과 8 중에서 작은 수는 6이고, 6에서 6을 더하면 12, 최소 값은 12가 된다.

---

 

글을 쓰면서 틀린부분이 있을 수 있습니다.

만약에 틀린부분이 있다면 댓글로 알려주세요!(공부하는데 많은 도움이 될 것 같아요!!)

글 읽어주셔서 감사합니다!!