say1116   6달 전

제가 재귀로 풀어서 답은 맞았는데요!

저는 DP가 값을 미리 저장해서 그 값은 다시 계산안할수있도록

cache 배열을 따로 두어서 사용하는 방법이라고 생각하는데요 아닌가요? 정확한의미를 모르겠습니다. ㅜㅜ

혹시 알려주실수있나요?


그리고  제가 푼 코드에 cache 배열을 이용해서

int &ret = cache[color][i];

if (ret != -1)
{
sum = ret;
return;
}

이런식으로 검사해서 사용하려고 했는데 잘안되서요 혹시 어떻게 해야하는지 알려주실수있을까요?

plzrun   6달 전

지금 이해하고 있는게 얼추 맞긴한데, 그런걸 메모이제이션(memoization)이라 하죠. DP문제를 해결하는데, 메모이제이션을 씁니다. ㅎ
다이나믹 프로그래밍에서 다이나믹과 프로그래밍이라는 것은 아무런 뜻이 없습니다.
컴퓨터도 없던 시절에 만들어진 단어들의 조합인데... 뭐 연구비를 받으려면 이름이 까리해야 돼서 그렇게 지었다고 합니다. ㅋㅋ (레알 dp정의한 사람이 아무 의미 없댔음)

dp문제 라는 거는...
큰 문제를 작은 단위의 문제로 나눠서 풀 수 있는 문제를 말합니다.
그런데, 이 정의만으로는 dp문제라 할 수 없어요. 저건 분할정복으로도 풀리는 거죠. dp문제는 중복되는것도 있어야 해요. 즉, 겹치는 부분문제가 있고, 큰 문제를 작은 단위의 부분 문제로 쪼갤 수 있는 문제를 우리는 DP문제라고 합니다.

DP문제를 풀기 위해서는 아시다시피 점화식을 세워야 합니다.

점화식을 다 세웠으면 이제 코딩만 하면 되는데요, 코딩할 때 Top-Down 방식으로 풀 때, 재귀식을 쓰는데요. 이때 중복되는 호출로 인해 반복 연산되는것을 막기 위해 memoization을 합니다.

그리고 레퍼런스 ret 쓰신거 뭐 안된다고 하셨는데, 전 정확히 어떤 코드가 안된다는건지 잘 모르겠어요. sum += ret; 인데 sum = ret;으로 실수 하신걸 물어보시는거 같진 않고...; ㅎㅎ;

plzrun   6달 전

지금 이해하고 있는게 얼추 맞긴한데, 그런걸 메모이제이션(memoization)이라 하죠. DP문제를 해결하는데, 메모이제이션을 씁니다. ㅎ
다이나믹 프로그래밍에서 다이나믹과 프로그래밍이라는 것은 아무런 뜻이 없습니다.
컴퓨터도 없던 시절에 만들어진 단어들의 조합인데... 뭐 연구비를 받으려면 이름이 까리해야 돼서 그렇게 지었다고 합니다. ㅋㅋ (레알 dp정의한 사람이 아무 의미 없댔음)

dp문제 라는 거는...
큰 문제를 작은 단위의 문제로 나눠서 풀 수 있는 문제를 말합니다.
그런데, 이 정의만으로는 dp문제라 할 수 없어요. 저건 분할정복으로도 풀리는 거죠. dp문제는 중복되는것도 있어야 해요. 즉, 겹치는 부분문제가 있고, 큰 문제를 작은 단위의 부분 문제로 쪼갤 수 있는 문제를 우리는 DP문제라고 합니다.

DP문제를 풀기 위해서는 아시다시피 점화식을 세워야 합니다.

점화식을 다 세웠으면 이제 코딩만 하면 되죠.ㅎ 코딩시에 Top-Down 방식을 선택하게 되면 재귀함수를 작성하게 되는데, 이때 중복되는 호출로 인해 반복 연산하는 것을 피하기 위해 memoization을 합니다.

그리고 레퍼런스 ret 쓰신거 뭐 안된다고 하셨는데, 전 정확히 어떤 코드가 안된다는건지 잘 모르겠어요. sum += ret; 인데 sum = ret;으로 실수 하신걸 물어보시는거 같진 않고...; ㅎㅎ;

댓글을 작성하려면 로그인해야 합니다.