Project Euler 1–100 풀이 노트
Project Euler 1번부터 100번까지, 하루에 한 문제씩 풉니다. 문제마다 필요한 배경 지식, 풀이를 끌어내는 과정, 복잡도, C++17과 Python 3 구현을 함께 정리합니다.
글마다 풀이 과정과 정답이 들어 있습니다. 커뮤니티의 관례에 따라 이 시리즈는 1–100번 문제만 다룹니다.
문제는 Project Euler에서 가져왔고 CC BY-NC-SA 4.0 라이선스를 따릅니다. Motitory는 Project Euler와 관련이 없습니다.
Project Euler 1: 3 또는 5의 배수의 합을 O(1)로
1000 미만에서 3이나 5로 나누어떨어지는 수의 합을, 반복문 대신 포함-배제와 등차수열의 합으로 구합니다. C++17과 Python 3 구현, 정확성 증명, 정수 범위까지 다룹니다.
Project Euler 2: 짝수 피보나치 수만 골라 더하기
피보나치 수열에서 짝수 항이 세 칸마다 나온다는 사실을 증명하고, 짝수 항끼리의 점화식 E(k) = 4E(k−1) + E(k−2)를 유도해 사백만 이하의 짝수 항만 더합니다. C++17과 Python 3 구현, 정확성 증명, 정수 범위까지 다룹니다.
Project Euler 3: 나눌 수 있는 만큼 나눠서 가장 큰 소인수 찾기
작은 수부터 나눌 수 있는 만큼 나누는 시행 나눗셈으로 12자리 정수의 가장 큰 소인수를 구합니다. 남은 값이 왜 소수인지 증명하고, √n 반복 상한과 64비트 정수 범위, C++17과 Python 3 구현까지 다룹니다.
Project Euler 4: 세 자리 수 두 개의 곱에서 가장 큰 회문수를 위에서부터 찾기
두 세 자리 수의 곱 중 가장 큰 회문수를 큰 곱부터 탐색하고 가지치기해서 구합니다. 가지치기가 왜 답을 놓치지 않는지 증명하고, 짝수 자리 회문수와 11의 관계, 정수 범위, C++17과 Python 3 구현까지 다룹니다.
Project Euler 5: 1부터 20까지 모두로 나누어떨어지는 가장 작은 수를 최소공배수로 바로 만들기
1부터 20까지의 모든 수로 나누어떨어지는 가장 작은 양의 정수를, 하나씩 찾아보는 대신 유클리드 호제법과 lcm(a, b) = a / gcd(a, b) × b를 거듭 적용해 만듭니다. 이 방법이 왜 정확히 최소공배수를 주는지 증명하고, 정수 범위와 C++17·Python 3 구현까지 다룹니다.