https://projecteuler.net/problem=74 이문제 푸는데 import time

import math;

st=time.time();

slf=[1,2,145];

ls169=[169, 363601, 1454];

ls871=[871,45361];

ls872=[872,45362];

dfc=dict();

for i in slf:

dfc[i]=i;

dfc[169]=363601;

dfc[1454]=169;

dfc[363601]=1454;

dfc[871]=45361;

dfc[45361]=871;

dfc[872]=45362;

dfc[45362]=872;

def dgtfac(n):

if n in dfc:

return dfc[n];

else:

s=sum(math.factorial(int(c)) for c in str(n));

dfc[n]=s;

return s;

n=10**6;

lst=[];

nxt=0;

ln=0;

cnt=0;

for i in range(1,n):

nxt=dgtfac(i)

while nxt not in lst:

lst.append(nxt);

nxt=dgtfac(nxt)

ln=len(lst)

lst=[];

if ln==60:

cnt+=1;

print(cnt);

print(time.time()-st) 이렇게 코드 짬

Gemini의 응답

Project Euler 74번은 자릿수 팩토리얼 합의 체인(Chain) 구조와 반복되는 루프(Loop) 지점을 찾는 문제임. 제시한 코드는 기본적인 로직을 갖추고 있으나, 실행 속도 측면에서 치명적인 병목 지점이 존재함.

1. 코드 성능 병목 분석

1. 리스트 탐색 (nxt not in lst):
   • while 루프 내에서 리스트에 값이 있는지 매번 확인하는 연산은 리스트 크기에 비례하는 시간 (O(N)) 이 소요됨. 체인 길이가 최대 60이므로 큰 수치는 아니나, 100만 번 반복되면 전체 속도가 크게 저하됨. set() 을 사용하거나 더 나은 캐싱 전략이 필요함.
2. 초기 리스트 초기화 (lst=[]):
   • 매 루프마다 리스트를 비우고 다시 채우는 방식은 이미 계산한 체인의 길이를 재활용하지 못함. 예를 들어, 어떤 숫자가 계산 과정에서 이미 알고 있는 체인에 진입했다면 거기서 즉시 멈춰야 함.
3. 데이터 캐싱 (dfc):
   • 자릿수 팩토리얼 합 자체(dgtfac)만 캐싱하고 있는데, '해당 숫자부터 시작했을 때의 최종 체인 길이' 를 캐싱하는 것이 훨씬 효율적임.

2. 최적화 제안: "메모이제이션(Memoization)"

각 숫자의 자릿수 팩토리얼 합을 구하는 것을 넘어, "이 숫자에서 시작하면 체인이 몇 개인가?" 에 대한 결과값 자체를 저장해야 함.

• 루프 지점 사전 정의: 문제에서 제시한 특수 루프들을 길이와 함께 미리 정의함.
  • 169, 363601, 1454 → 길이 3
  • 871, 45361 → 길이 2
  • 872, 45362 → 길이 2
  • 1, 2, 145 등 자기 자신 → 길이 1

3. 개선된 코드 구조 (개념)

Python

import math

# 각 자리 팩토리얼 미리 계산 (속도 향상)
fac = [math.factorial(i) for i in range(10)]

def get_next(n):
    s = 0
    while n > 0:
        s += fac[n % 10]
        n //= 10
    return s

memo = {169: 3, 363601: 3, 1454: 3, 871: 2, 45361: 2, 872: 2, 45362: 2,
        145: 1, 1: 1, 2: 1, 40585: 1}

def get_chain_length(n):
    if n in memo: return memo[n]
    
    # 현재 체인 경로 추적 (루프 방지)
    path = [n]
    curr = n
    while True:
        curr = get_next(curr)
        if curr in memo:
            res = len(path) + memo[curr]
            break
        if curr in path: # 새로운 루프 발견 (문제 정의상 드묾)
            res = len(path)
            break
        path.append(curr)
    
    # 경로상의 모든 숫자에 대해 길이 저장 (메모이제이션)
    for i, p_num in enumerate(path):
        if p_num < 10**6: # 범위 내 숫자만 저장하여 메모리 관리
            memo[p_num] = res - i
    return res

# 메인 루프 실행
cnt = 0
for i in range(1, 10**6):
    if get_chain_length(i) == 60:
        cnt += 1

4. 추가 가속 팁

• 문자열 변환 지양: str(n) 은 매우 느림. 위 코드의 while n > 0 처럼 산술 연산으로 자릿수를 분리하는 것이 훨씬 빠름.
• Pre-calculation: 0부터 9까지의 팩토리얼 값을 리스트에 미리 담아두고 인덱스로 접근하는 것이 math.factorial() 호출보다 유리함.

[결론]

현재 코드는 100만 번의 반복에서 중복 계산이 너무 많아 실행 시간이 수 분 이상 걸릴 수 있음. 체인 길이 자체를 메모리에 저장하는 방식으로 수정하면 1초 이내로 해결 가능함. 기존 코드의 while nxt not in lst 부분만이라도 이미 계산된 체인 정보와 대조하여 탈출하는 로직을 추가해볼 것. 분석을 마침.

말씀하신 내용

나도 무슨말인지 아는데 그냥 숫자가 적어서 강행한거 + 데이터 캐싱은 애매한게 이게 숫자에서 어느 리스트까지 도달할때까지의 길이를 잰다면 너말이 맞는거 같은데 반복시점까지를 타겟팅하면 링크리스트 방식의 딕셔너리를 유지해야될거같아서. 안하고 할방법이 있나 직관적으로 떠오르진 x

Gemini의 응답

사용자의 말대로 반복 시점(Loop) 이 고정되어 있지 않고 가변적이라면 단순 캐싱이 까다로울 수 있음. 하지만 이 문제의 핵심은 모든 체인은 결국 기착지(Known Loops)로 수렴한다는 점임.

링크드 리스트 방식의 복잡한 구조 없이도 재귀(Recursion) 또는 경로 저장(Path Tracking) 을 활용하면 직관적으로 캐싱이 가능함.

1. 딕셔너리 유지 없이 캐싱하는 논리

반복 시점을 타겟팅하면서도 효율을 챙기는 방법은 "이미 길이를 알고 있는 지점" 을 만날 때까지 가보는 것임.

1. 기착지 선언: 문제에서 준 루프들(169,871 등)과 자기 자신으로 돌아오는 수(1,145 등)의 최종 체인 길이를 미리 memo 딕셔너리에 넣어둠.
2. 탐색: 새로운 숫자 i 에서 시작해 다음 숫자를 구함.
3. 지점 확인:
   • 만약 다음 숫자가 memo에 있다면? → 현재까지 온 길이 + memo[지점] 이 정답임.
   • 만약 없다면? → 현재 숫자를 path 리스트에 넣고 다음으로 진행.
4. 역전파(Back-propagation): 정답을 구한 순간, path에 들어있는 모든 숫자들의 길이를 계산해 memo에 한꺼번에 등록함.

2. 직관적인 캐싱 흐름 예시

가령 540→145→145… 인 체인을 검사한다고 가정(예시임).

• 이미 memo[145] = 1 임을 알고 있음.
• 540 을 검사 시작 → path = [540]
• 다음 숫자인 145 를 보니 memo에 있음.
• 그러면 540 의 길이는 (path의 길이 1) + memo[145] 로 계산되어 2 가 됨.
• memo[540] = 2 를 기록.

이 방식은 루프의 시작점을 일일이 찾을 필요 없이, 이미 정의된 루프 지점들에 도달하는 순간 모든 계산이 끝남.

3. 왜 리스트 탐색보다 딕셔너리 캐싱인가?

사용자가 짠 코드의 while nxt not in lst 는 매번 "새로운 루프가 발생할지 모른다"는 가정하에 모든 숫자를 전수 조사함. 하지만 이 문제의 수들은 결국 정해진 몇 개의 루프로만 빨려 들어감.

• 기존 방식: 매번 빈 리스트에서 시작해 60번의 in 연산 수행.
• 개선 방식: 이미 아는 숫자를 만나는 순간 즉시 리턴. (대부분의 숫자가 10~20단계 안에 기존 체인에 합류함)

[결론]

"반복 시점까지의 경로"를 하나의 완성된 데이터로 보고, 그 경로에 발을 들이는 순간 나머지는 계산하지 않는 '합류 지점 기반 캐싱' 이 가장 직관적인 해법임. 100만까지 돌릴 때 이 방식을 쓰면 중복 연산이 90% 이상 제거됨. 분석을 마침.