[2024 하계모각코] 2주차 결과

Dynamic Programming-1

*Richard Bellman이 만들었다.

 

피보나치 수열

1 1 2 3 5 8 13

f(n)=f(n-2)+f(n-2) n>2

f(1)=f(2)=1

 

int fib(int n)

{ if(n==1 || n==2) return 1;

else return fib(n-2)+fib(n-2);}

 

->순환으로 하면 매우 비효율적

---

Memoization

Memoization으로 풀면, 1차원 배열인 cashe에 저장하기 때문에, 동일한 피보나치 수열을 중복 계산 안 해도 된다.

---

 

순환식을 bottom-up방식으로 풀면,  중복 계산을 피할 수 있다. -> Dynamic Programming

---

 

 

base case가 있을 때, base case가 아닌 경우에 순환을 할 때 마지막엔 base case를 꼭 거치도록 해야 한다.

이때, n>=k일 때 여야 한다. 이때, 역시 많은 계산이 중복되므로 Memoization을 해야 한다.

---

 

 

2차원 배열을 만들고, n>=k일때, 대각선 위는 무시, 대각선 아래만 의미있는 값으로 본다.

중간 계산 결과를 cash에 저장한다.

---

 

 

bottom-up방식: binom[i][j] = binom[i-1][j-1] + binom[i-1][j] 순환식의 오른쪽 식이 왼쪽 식보다 먼저 계산된다.

행우선 순서로 계산한다.

---

 

Memoization vs Dynamic Programming

• 순환식의 값을 계산하는 기법들이다.
• 둘 다 동적계획법의 일종으로 보기도 한다.
• Memoization은 top-down 방식임, 실제로 필요한 subproblem만을 푼다.
• 동적계획법은 bottom-up 방식이며, recursion에 수반되는 overhead가 없다.

---

Dynamic Programming-2

1. 행렬 경로 문제

2차원 배열에 정수 값들이 저장되어 있을 때, 좌상단부터 우하단까지 이동하며, 오른쪽이나 아래쪽 방향으로만 이동할 수 있다. 왼쪽이나 위쪽 방향으로는 이동할 수 없다. 방문한 칸에 있는 정수들의 합이 최소가 되도록 해야 한다.

 

먼저 순환식을 세우고 그다음 계산을 하면 된다.

---

 

• (i,j)에 도달하기 위해서는 (i,j-1)혹은 (i-1,j)를 거쳐야 한다. 오른쪽이나 아래쪽 방향으로만 이동할 수 있기때문에 거꾸로 생각했을 때 이렇게 되는 것이다.
• 또한, (i,j-1)혹은 (i-1,j)까지는 최선의 방법으로 이동해야 한다.

---

L[i,j]가 (1,1)에서 (i,j)까지 이르는 최소합을 의미한다.

 

이때, 만약 i=1,j=1이면(2차원 배열에서 첫번째 값이면), 그 값이 최소합이 된다.

만약 j=1이면(첫번째 열의 가장 하단의 값까지 이동), i-1(최하단 행에서 하나 윗 행)까지 이동했을때의 L값에 mij를 합하면 그 값이 최소합이 된다.

마찬가지로 i=1일 때는 j=1일 때와 같이 외길로만 이동한다.

마지막 case에서는 L[i-1,j]+mij와 L[i,j-1]+mij중 최솟값이 답이 된다.

---

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

앞의 식을 코드로 짠 것이다. 하지만 이럴 경우 중복이 있을 수 있다.

---

mat(3,3)같은 경우 중복이 처음으로 발생한다. 이처럼 중복이 발생하므로 Memoization방법을 써주도록 하자.

---

int mat(int i, int j)
{	
	if(L[i][j] != -1 return L[i][j];
	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];
 }

Memoization방법을 써서 계산의 중복을 피했다. 

2차원 배열 L을 만들어 미리 계산된 값(-1)을 저장해준다. 

미리 저장된 -1이 아니면 L[i][j]를 리턴한다.

 

전에는 값을 저장하지 않고 바로 리턴했는데, 이 방법에서는 값을 저장한 다음 마지막에 리턴하여 중복을 피한다.

---

Bottom-Up 방식으로 문제를 풀게 되면, 행 우선으로 계산한다.

 

---

int mat()
{	
	for(int i=1; i<=n ;i++{
    	for(int j=1; j<=n; j++) {
			if(i==1 && j==1)
    			L[i][j] = m[1][1];
   		 	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];
 }

위 함수의 시간복잡도는 O(n의 제곱)이다.

---

Common Trick

/*initialise L with L[0][j]=L[i][0]=무한대 for all i and j*/

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

위 함수의 시간복잡도는 O(n의 제곱)이다.

---

경로 구하기

28을 계산할 때 위의 값인 25 또는 왼쪽의 값인 31 중 작은 값에 원래 있던 값인 3을 더해서 28이 된 것이다.

이러한 과정을 화살표로 표현한 것이 P행렬이다.

---

/*initialise L with L[0][j]=L[i][0]=무한대 for all i and j*/

int mat()
{
	for(int i=1;i<=n;i++){
		for(int j=1; j<=n;j++){
        	if(i==1 && j==1)
            	L[i][j]==m[1][1];
                P[i][j] = '-';
            else
            	if(L[i-1][j]<L[i][j-1]){
            		L[i][j] = m[i][j] + L[i-1][j];
                    P[i][j] = '^' /*위쪽 화살표*/
                }
                else{
                	L[i][j] = m[i][j] + L[i][j-1];
                    P[i][j] = '<-' /*왼쪽 화살표*/
                }
            }
        }
     }
     return L[n][n];
}

 위 함수의 시간복잡도는 O(n의 제곱)이다.

---

void printPath()
{
	int i=n, j=n;
    while(P[i][j] != '-'){
    	print(i+" "+j);
        if(P[i][j]=='<-')
        	j=j-1;
        else
        	i=i-1;
     }
     print(i+" "+j);
 }

우측 최하단(목적지)에서 좌측 최상단까지 경로가 거꾸로 출력된다.

그렇다면 반대로 경로가 처음 있었던 곳에서 목적지까지일 경우 함수는 어떻게 작성할까?

---

void printPathRecursive(int i, int j)
{
	if(P[i][j] == '-')
    	print(i+" "+j);
    else{
        if(P[i][j]=='<-')
        	printPathRecursive(i,j-1);
        else
        	printPathRecursive(i-1,j);
        print(i+" "+j);
     }
 }

(1,1)에서 (i,j)까지의 최소합경로인 출발점에서부터 목적지까지의 경로를 출력한다.