https://www.acmicpc.net/problem/13699
[동적 계획법]
dp는 이전 문제들의 답을 메모해두는 알고리즘이다. 피보나치 수열과 같이 이전에 계산한 문제의 해가 계속 필요할 때 유용하다. 그래서 동적 계획법의 핵심은 "Memoization"이다. 메모리제이션은 이전에 계산한 값들을 저장해두고, 동일한 계산이 필요할 때 불러와서 계속 사용을 하는 기법
[피보나치 수열_동적계획법]
fibo(0) = 0
fibo(1) = 1
fibo(2) = fibo(1) + fibo(0)
fibo(3) = fibo(2) + fibo(1)
...
fibo(n) = fibo(n-1) + fibo(n-2)
def f(n) :
temp = 0
c = [0, 1]
for i in range(2, n+1) :
temp += c[i-1] + c[i-2]
c.append(temp)
# print(c)
return c
print(f(5))
위 코드를 실행하면 배열에 저장된 값들을 활용하여 피보나치 수열을 계산할 수 있다.
[최종코드]
n = int(input())
t = [1, 1, 2]
for i in range(3, n+1) :
ans = 0
for j in range(i) :
ans += t[j] * t[i-j-1]
t.append(ans)
print(t)
print(t[n])
내가 처음에 생각 했던 코드는 ans += [t[i]*t[n-(i+1)]인데 이렇게 작성하면 점화식 인덱싱은 제대로 하지만, 배열에 저장되에 있는 값이 없기 때문에, 연산을 할 수가 없는 코드다. 😅
⭐️⭐️⭐️ 3>2>1>0 이렇게 변화하는 부분을 이중포문으로 작성할 수 있다는 걸 배웠다. ⭐️⭐️⭐️
Reference
되게 쉽고 자세하게 잘써두셔서 두고두고 보려고 같이 기록..
https://star7sss.tistory.com/157
'PS > BOJ&Programmers' 카테고리의 다른 글
[백준/1312] 소수 | 런타임에러? | 부동소수점과 컴퓨터 연산에 대한 이해 (1) | 2023.03.26 |
---|---|
[백준/15686] 치킨 배달 | 시뮬레이션 | 2차원 공간 좌표 다루기 (0) | 2023.03.21 |
[백준/17202] 핸드폰 번호 궁합 | 배열을 통해서 연산 갱신하기 |011223.. 인덱싱 (0) | 2023.03.19 |
[백준/18111] 마인크래프트 (1) | 2023.03.12 |
[백준/16283] Farm (2) | 2023.03.10 |