3주차 코딩테스트 퀴즈

어떤 문제가 나오는지는 말하지 못하지만 과제로 내준 문제들 모두 확실히 알고 있다면 무리 없이 해낼 수 있는 수준이다. 필자는 골드 2인데 3문제 50분 정도 걸렸던 것 같다.

DP

경우의 수를 쪼개서 완전탐색으로 먼저 생각하고 top-down DP 및 bottom-up DP로 모두 풀어보는 연습을 했다. 4문제를 풀었는데 완전 탐색으로 코드를 짜는 것은 크게 어렵지 않지만 DP로 최적화 하는 과정에서 LLM의 많은 도움을 받았다.. 그래도 조금은 감 잡은 것 같다.
대표적으로 피보나치 수열을 알아보자.

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

n = int(input())

def fibo(n):
    if n <= 1:
        return n

    return fibo(n-1) + fibo(n-2)

print(fibo(n))

기본적으로 가장 빠르게 떠오르는 방식이 아닐까 싶다.
DP 문제를 해결하기 위해선 중복 계산 부분을 제거하는 것이 중요하다.
따라서 다음과 같이 코드를 개선할 수 있다.

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

n = int(input())
dp = [-1] * (n + 1)
def fibo(n):
    if n <= 1:
        return n

    if dp[n] != -1:
        return dp[n]

    dp[n] = fibo(n-1) + fibo(n-2)

    return dp[n]

print(fibo(n))

여기까지 했다면 bottom-up DP로 바꾸는 것은 많은 연습을 통해 금방 체화시킬 수 있을 것이라 생각한다. 아래는 bottom-up DP로 바꾼 예시이다.

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

n = int(input())

dp = [0] * (n+1)

for n in range(n+1):
    if n <= 1:
        dp[n] = n
    else:
        dp[n] = dp[n-1] + dp[n-2]

print(dp[n])