즐겁게, 코드

혹시 피보나치의 수를 구하는 알고리즘을 알고 계신가요? 아마 많은 분들이 재귀함수를 사용하는 알고리즘을 떠올릴 것입니다. N = int(input()) def fib(N): if N == 0 or N == 1: return N return fib(N - 1) + fib(N - 2) print(fib(N)) # input output time # 10 55 0.00092s # 5 5 0.00018s # 100 한없이 긴 시간이 소요됩니다... 얼핏 보면 완벽해 보이는 알고리즘이지만 여기에는 함정이 하나 숨어있는데요, 잠깐 5번째 피보나치 수를 구하는 과정을 그림으로 소개하자면 아래와 같습니다. 5번째 피보나치 수는 4번째 피보나치 수와 3번째 피보나치 수를 더한 결과이며, 4번째 피보나치 수는 3번째 + ..

[백준 온라인 저지 - 문제 링크] 이 문제에는 시간 초과라는 무시무시한 함정이 깔려 있습니다. 따라서 여느 DP 문제처럼 DP 테이블을 그려 해결하되, 테이블을 조금 더 창의적으로 고안해야만 합니다! 처음 제가 구상한 알고리즘은 증가하는 인덱스 i ~ N까지의 원소 중 최댓값을 각 i 별로 구한 후, 이 중에서 최댓값을 찾는 방법이었습니다. 이를 기반으로 거친 생각과 불안한 마음을 안고 코드를 짜 봤으나... [실패 코드 (Python)] # 시간 초과 코드 T = int(input()) d = [0] * 100001 arr = list(map(int, input().split())) ans_list = [] temp_list = [] d[0] = arr[0] for i in range(1, T): t..