프로젝트 오일러 002

안녕하세요 DEV



프로젝트 오일러는 제가 좋아하는 도전적인 수학/컴퓨터 프로그래밍 문제 시리즈입니다. 저는 저에게 배울 것이 많을 것이라고 확신하며 여기 DEV에서 제 솔루션을 공유하고 싶습니다.

❓ 문제 002는 다음과 같습니다.

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.



💡 이 문제를 해결하기 위해 Modulo 연산과 Addition의 조합을 사용할 수 있습니다.

❗ 프로그래밍에서 피보나치 시퀀스 또는 기타 유사한 개념으로 작업할 때 생각할 수 있는 첫 번째 솔루션은 확실합니다.
재귀적 접근법. 그러나 우리는 항상 이러한 함수가 천 번 호출될 수 있으며 이는 단순히
당신은 그러한 오류 중 하나Maximum call stack size exceeded에 직면하게 될 것입니다!

이것은 💀 이러한 알고리즘의 공간 복잡성( Have a 👀 at this article on this topic ) 때문에 발생하므로 여기서 대신 반복 접근 방식을 사용합니다.

피보나치 수열의 공식은 다음과 같습니다.

fib(n) = fib(n-1) + fib(n-2) → for n > 1
fib(n) = 1 → for n = 0, 1


다음과 같은 변수가 있다고 가정할 수 있습니다.

MAX = 4000000

first_number = 1
second_number = 1

sum = 0


그런 다음 단순히 2개의 다른 변수에 저장하는 이전 항으로 다음 항을 계산하여 답을 계산합니다!
그런 다음 짝수를 필터링하고 모두 합산합니다.

💻 따라서 Python에서 내 솔루션은 다음과 같습니다.

while second_number <= MAX:
    temp = second_number
    second_number += first_number
    first_number = temp

    if second_number % 2 == 0:
        sum += second_number
print(sum)


이것은 이 문제에 대한 최선의 답이 아닐 수 있지만 이 문제에 대해 32개의 숫자(홀수도 포함됨)만 계산합니다.
재귀 접근 방식보다 훨씬 낫습니다. 홀수를 전혀 계산하지 않는 방법을 찾을 수 있다면 분명합니다! 저것
완벽한 개선이 될 것입니다. 이에 대한 아이디어가 있는지 기다릴 수 없습니다.

✅ 이 문제의 정답은 4613732 입니다.

감사합니다 ❤️



프로그래밍의 세계를 처음 접하는 사람이나 호기심이 있는 사람 🧐에게 제 글이 도움이 되었으면 합니다!
콘텐츠가 유용하다고 생각되면 의견을 댓글로 남겨주세요. 여러분 모두에게서 배우고 싶습니다.

당신의 애정 어린 지시에 감사드립니다.

좋은 웹페이지 즐겨찾기