DP - TRIANGLEPATH, 스티커

DP - TRIANGLEPATH, 스티커

TRIANGLEPATH

(i, j) 번째 노드에서 아래쪽, 또는 오른쪽 아래로 내려가는 Path가 만들어지고, 최종적으로 n번째 depth에 다다랐을 때, 경로의 최댓값을 찾는 문제.

첫 시도에 풀지 못한 이유 :

문제분석을 제대로 못함. : 문제 이해를 잘못함 문제분석을 제대로 한 이후에는 완전탐색으로 문제를 풀려고 했음. 완전탐색으로 푸는 방법밖에 없다고 생각했는데, 굳이 겹치는 경로가 없기 때문에 memoization을 적용할 필요가 없다고 생각했기 때문이다. 어찌되었든 문제에 대한 이해가 잘못되어있었다. 겹치는 경로는 존재했으며, memoization을 적용시켜야 했다.

생각의 관점을 달리하면?

memoization으로 풀지 못할거라고 생각한 이유는 다음과 같다.

빨간 부분의 Path를

점화식 memo[i][j] = max(memo[i-1][j] + array[i][j], memo[i-1][j - 1] + array[i][j]) 에 의해 구한다고 하자.

재귀함수의 실행 순서를 생각하면..

반복적으로 다시 사용하게 되는 속성은, 아래에서 위로 올라가면서 계산되는 부분합을 사용하게 된다.

밑으로 내려가면서 sum에 대한 memoization을 굳이 할 필요가 없고, 밑으로 내려갔다가 올라올 때 계산되는 부분합이 필요하다.

예를들어, partial_sum[3][1] 은 (3,0)과 (3,1)에서 sum을 구하기 위해 사용된다.

따라서, memoization을 위에서 아래로 내려오는 부분들에 대한 sum이 아닌, 앞으로 계산해야 될 부분의 아랫부분까지의 partial sum으로 저장하고 있는다면, 재귀에 의해 sum을 계산할 때, 중복되는 계산을 피할 수 있을 것이다.

앞으로 기억해야 할 점

DP는 완전탐색으로 시작한다. DP는 점화식으로 생각한다. 중복되는 계산이 있는지 생각한다. 문제의 예시를 생각하고, 따라가면서 점화관계를 유도해본다.

#include #include #include int memo[100][100]; int arr[100][100]; int sub_path(int x, int y, int size) { int max_path; int path1; int path2; if (y == size - 1) return (arr[y][x]); if (memo[y][x] != 0) return (memo[y][x]); else { path1 = arr[y][x] + sub_path(x, y + 1, size); path2 = arr[y][x] + sub_path(x + 1, y + 1, size); max_path = std::max(path1, path2); memo[y][x] = max_path; return (max_path); } } using namespace std; int main() { int tc; int n; int i,j; cin >> tc; while (tc--) { cin >> n; for (i = 0; i < n; i++) for (j = 0; j <= i; j++) memo[i][j] = 0; for (i = 0; i < n; i++) { for (j = 0; j <= i; j++) cin >> arr[i][j]; } cout << sub_path(0, 0, n) << endl; } return (0); }

백준 스티커

문제 분석

선택한 스티커와 변을 공유하는 스티커는 선택할 수 없음. 즉, weight 100을 택했다면 좌, 우, 아래는 선택할 수 없음. 위 조건으로 스티커들을 선택해 가장 큰 합을 찾는 문제.

주어진 그림으로 완전탐색하여 그림을 그려가면서 풀어봄.

50 + 50 + 100 + 10 + 40 일 줄 알았으나, 50 + 50 + 100 + 60이 가장 큰 합이었음.

문제를 일반화해서 생각해봤다.

왼쪽에서 오른쪽으로 진행하면서, 각 칸으로 가는 최대 Path의 길을 계산한다고 가정한다.

A로 가는 path의 최대값을 구하고 싶다면, X 로 마킹된 칸은 A와 변을 공유하니 사용하지 못하고 3을 사용하던가, 2를 사용해야 한다. 1을 사용하고자 하면, 3번칸이 이미 1을 지나오면서 Path를 계산했기 때문에 1번 칸을 사용하여 A로 가는 Path의 최대값을 계산하는 것은 의미가 없다.

따라서, A로 가는 Path의 최대값을 계산하기 위해서는 2와 3 둘 중 하나와 A칸의 weight를 더한 다음 그 둘의 최대값으로 해야한다.

A의 아래칸인 B도 마찬가지로 x와 1을 비교한 뒤, 둘의 최대값과 B의 weight를 더하여 B로 가는 Path의 최대값을 구한다.

이 과정에서 memoization을 사용해야 한다.

계산한 칸을 최대 두번이상 사용하지는 않는다.

점화식도 나왔겠다 문제를 풀었는데 문제를 풀지 못했고 그 이유는 재귀함수를 사용하여 base case를 만든 뒤 문제를 풀려고 했었다.

문제를 재귀적으로 풀려고 하다 문제가 n개의 부분문제로 나뉘지 않는다는것을 깨달았고, 바로 Bottom up 방식으로 바꾸어 차례로 왼쪽부터 오른쪽으로 풀어나가면서 칸을 채워나가 문제를 풀었다.

int sticker_1(int x, int y, int n) { //path1, path2 : memo[.][.] + weight[y][x] int path1; int path2; //base case if (x == n) return memo[y][x-1]; if (memo[y][x] != -1) return memo[y][x]; //algorithm w/ recursive relation return (max(path1, path2)); //return 을 어떤 식으로 해야할 지 감을 잡지 못했다. }

부분문제는 있긴 했다. 특정 칸의 path값을 계산해주기 위해서는 이전 Path 2개를 알아야 했지만,

아래 그림처럼 부분문제가 생기는 형태가 아니었기 때문에, 재귀적으로 문제를 풀지 못했다.

from http://pjeongja.tistory.com/100 by ccl(A) rewrite - 2021-08-20 01:00:22