글 읽기 - 재귀함수 때문에 속도가 느려지는 거 같아서 while문을 돌렸는데도 느리네요

wow056 5년 전 0

리스트를 이용해 피보나치 수열을 역연산하면서 0과 1의 개수를 세도록 만들어봤는데요

숫자가 20을 넘어가면 연산속도가 현저히 떨어지기 시작합니다.

아마도 피보나치 수열의 연산을 이용하면 연산속도가 2의 숫자 제곱에 비례할 것이라고 생각하는데요

O(2^n)이 아닌 O(n^2)이나 O(n)인 알고리즘이 존재하나요?

caseNum = int(input())
output = []
for i in range(caseNum):
    numList = [int(input())]
    countZero = 0
    countOne = 0
    while numList:
        for num in numList:
            if num == 0:
                countZero += 1
            elif num == 1:
                countOne += 1
            else:
                numList += [num - 1, num - 2]
            numList.remove(num)
    output.append((countZero, countOne))
for num in output:
    print("%d %d" % num)

kimsy96 5년 전 0

https://www.acmicpc.net/blog/v...

njw1204 5년 전 1

다이나믹 프로그래밍을 이용하면 O(n)으로 가능합니다.

아이디어는 fib(3)을 호출할 때 결과값을 저장해놓고,

다음에 fib(3)이 필요할때는 함수를 호출할 필요없이 저장된 값만 불러오면 된다는 것입니다.

이것을 메모이제이션이라고 부릅니다.

다이나믹 프로그래밍에서 아주 대표적인 문제이니 학습해보시는걸 추천합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

재귀함수 때문에 속도가 느려지는 거 같아서 while문을 돌렸는데도 느리네요

wow056 5년 전 0

kimsy96 5년 전 0

njw1204 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말