사이트 여기저기를 뒤져보니까 dp[3]으로 해서 그때그때만 저장하는 식으로 하면 된다고 했는데 어떻게 해야하죠?????

아래 코드는 메모리 초과가 나는 코드입니다...........한마디로 dp[3]으로 어떻게 풀죠????

lsc4719   4달 전

순서대로 알려드리면,

0. 어떤 문제의 답 a가 어떤 sequence S의 n번째 항이라는 것을 캐치합니다.

1. 먼저 S의 recurrence relation R을 적습니다.

EX.

F(1)=F(2)=1(initial condition) and

F(i)=F(i-1)+F(i-2) for 3<=i

2. R을 이용해 S[0], S[1], ... S[n] = a 를 계산합니다.

Ex. 그런데 이 때, 위의 F를 예로 보면,  필요한 메모리가 O(n)이 아닌 O(1)임을 알 수 있습니다. 메모리를 재활용하면 되기 때문입니다.

lsc4719님이 설명하신대로면 메모리가 n아니에요????

1 1 2 3 5 8 13 ........ n번쨰

arr[0], arr[1]......arr[n - 1]

처럼 가기 때문에????????

1 1 2

1 2 3

2 3 5

3 5 8

이렇게 밀어야 하나요????

lsc4719   4달 전

설명이 부족했어요.

2에서 바텀업으로 푸시되 메모리를 재활용하시면 되요.

Ex.

int F[3]

...

해결!

lsc4719   4달 전

네 맞아요!

그러면 dp[3]으로 한뒤 계속 다른 값으로 채우면 되나요????

lsc4719   4달 전

% 연산을 적절히 활용하시면 편하게 구현하실 수 있어여

lsc4719   4달 전

음, 메모리를 재활용할 수 있는 이유는 어떤 항이 이전 몇 항들의 함수이기 때문입니다. 어떤 항이 이전의 모든 항들에 대한 함수라면 메모리 재활용은 쓰일 수 없어요

감사합니다............이제 풀수있을 것 같아요................

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