99클럽 코테 스터디 21일차 TIL + 다이나믹 프로그래밍(DP)

[오늘의 학습 키워드 및 문제]
- 프로그래머스의 "피보나치 수" 문제를 풀었다.
- 이 문제는 본래 재귀 함수로도 DP로도 풀 수 있다. 근데 오늘 주제가 DP이므로 DP로 풀었다.
- DP는 그리디의 한 종류로 안 그래도 어렵고 싫은데, 코테에 자주 나오는 듯하여 슬프다...

[나의 코드]

def solution(n):
    d = [0] * (n + 1)
    d[1] = 1
    d[2] = 1
    
    for i in range(3, n + 1):
        d[i] = d[i - 2] + d[i - 1]
    return d[n] % 1234567

코드를 이해하기 위해서는 메모이제이션 기법을 알아야 한다.
메모이제이션 기법은 한 번 구한 결과를 메모리 공간에 메모해 두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다.

그래서 미리 결과를 저장해둘 배열 d를 n + 1 길이만큼 0으로 초기화한다.
그리고 F(0) = 0, F(1) = 1, F(2) = 1은 결과 값을 알고 있으므로 저장해 둔다. (실제로는 1까지만 저장해도 되는데, 속도가 2까지 저장해야 더 빨랐다.)

for문에서 값을 모르는 3부터 인덱스까지 돌면서 값을 구하면 된다.
마지막에 1234567을 나눈 값의 나머지를 반환하면 끝이다.

이번 문제는 대놓고 식이 주어졌는데, 그렇지 않은 문제들은 직접 점화식을 구해야 한다.
참 아름다운 세상이다.

def solution(n):
    if n == 1 or n == 2:
        return 1
    return solution(n - 1) + solution(n - 2)

이거는 단순 참고를 위해 재귀로 구현해 본 거다.
재귀로 구현하면 답은 맞으나 시간 초과가 뜰 것이다.
그리고 1234567로 나누지도 않아서 몇 개는 통과가 안 된다.

[오늘의 회고]
- 오늘은 너무 기본 중의 기본 문제가 나와서 엄청 빨리 풀었다. 이것보다 어려운 거 많은데...
- 오늘 푼 방식이 보텀업 방식인데, 이게 정석이다.
- 근데 내 방 달력은 아직도 6월이다. 끝!