오늘의 문제
https://www.acmicpc.net/problem/2748 피보나치 함수 문제에서는 재귀를 이용하여 푸는 것이 관건이었다면
이번 문제는 다이나믹 프로그래밍(DP) 에 분류되어 있는 만큼, 재귀를 사용하지 않고 푸는 방법들을 찾아보았다.
포인트 쳌쳌
Dynamic Programming 이란 큰 문제를 작은 문제들로 조각내어 풀어내는 기법이다.
작은 단위의 반복문이나 조건문을 통해 추출된 결과를 배열과 같은 저장공간에 저장해둠으로써 동일한 반복적인 계산을 피하게 하는 기술 을 메모이제이션 이라고 한다.
메모이제이션은 DP와 함께 자주 사용된다. 아래 코드 또한 메모이제이션을 이용한 것이다.
피보나치는 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 와 같이 이어지는데
아래 코드는 미리 0~55가 들어갈 크기의 리스트를 할당한 후 각 원소의 계산 결과를 배열마다 저장해주도록 한다.
풀이 코드
import sys
n = int(sys.stdin.readline())
step = [0]*(n+1)
step[1] = 1
for i in range(2, n+1):
step[i] = step[i-1] + step[i-2]
sys.stdout.write(str(step[-1]))
채점 결과
