Daily Algorithm - Day 25

Reciprocal Cycles

A unit fraction contains $1$ in the numerator. The decimal representation of the unit fractions with denominators $2$ to $10$ are given:
$1/2 = 0.5\\ 1/3 =0.(3)\\ 1/4 =0.25\\ 1/5 = 0.2\\ 1/6 = 0.1(6)\\ 1/7 = 0.(142857)\\ 1/8 = 0.125\\ 1/9 = 0.(1)\\ 1/10 = 0.1$
where $0.1(6)$ means $0.166666\cdots$, and has a $1$-digit recurring cycle. It can be seen that $1/7$ has a $6$-digit recurring cylce.

Find the value of $d<1000$ for which $1/d$ contains the longest recurring cycle in its decimal fraction part.```
코드를 입력하세요

$d$를 1000 미만의 자연수라고 할 때 $1/d$의 순환마디가 가장 긴 $d$를 구하는 문제이다.

내가 생각한 구현 방식은 다음과 같다.

1. $1/d$를 자릿수별로 진행하며 나오는 나머지를 이용해 순환마디의 길이를 출력하는 함수를 작성한다.
   (동일한 나머지가 나오는 길이가 순환마디의 길이가 될 것이다.)
2. $d < n$일 때 $1/d$의 순환마디가 가장 긴 $d$와 그 길이를 출력해주는 함수를 작성한다.

우선 $1/d$의 순환마디의 길이를 출력하는 함수다.

//Python

def recurring_cycle_length(d):
    remainder = 1
    remainder_list = []
    index = 0
    
    while remainder != 0:
    	# 같은 나머지가 나온다면 사이의 길이를 구해서 출력
        if remainder_list.count(remainder):
            remainder_list.append(remainder)
            return index - remainder_list.index(remainder)
        # 같은 나머지가 나올 때 까지 자리수를 내려가며 나머지를 구해준다.
        remainder_list.append(remainder)
        remainder = (remainder * 10) % d
        index += 1
        
    # 순환 주기가 없을 경우 (=나머지가 0이 나올 경우)
    return 0

다음은 $d < n$일 때 $1/d$의 순환마디가 가장 긴 $d$와 그 길이를 출력해주는 함수다.

def reciprocal_cycle(d):
    length = 0
    longest_number = 0
    for i in range(1, d):
        length = max(length, recurring_cycle_length(i))
        if length == recurring_cycle_length(i):
            longest_number = i
            
    return (f"d = {longest_number}, length = {length}")
    
print(reciprocal_cycle(1000))

>>> d = 983, length = 982   #correct

일단 답은 구해졌지만 아직 할 일이 남았다.

오늘부터 내가 작성한 코드를 chat-gpt 등의 LLM에게 리뷰받을 예정이다.
혼자서 코드를 작성하다보니 코드의 개선점을 찾는데에 한계가 많았기 때문이다.
리뷰를 나의 코드가 어떤 문제점이 있는지, 어떻게 개선할 수 있는지 학습이 가능할 것으로 기대된다.

바로 리뷰를 받아보자.

• 개선된 코드

def recurring_cycle_length(d):
    remainder = 1
    seen_remainders = {}
    position = 0

    while remainder != 0:
        if remainder in seen_remainders:
            return position - seen_remainders[remainder]
        seen_remainders[remainder] = position
        remainder = (remainder * 10) % d
        position += 1

    return 0

def reciprocal_cycle(limit):
    max_length = 0
    number = 0

    for i in range(1, limit):
        length = recurring_cycle_length(i)
        if length > max_length:
            max_length = length
            number = i

    return (f"d = {longest_number}, length = {length}")

print(reciprocal_cycle(1000))

과연... list의 경우 count과 index는 활용하려면 list를 전부 순회해야해서 시간 복잡도가 $O(n)$인 반면,
dictionary를 이용해서 key에 나머지 값을, value에 자릿수를 저장해준다면 시간 복잡도를 $O(1)$로 줄이면서 가독성까지 좋아진다.

그리고 같은 입력값을 가진 recurring_cycle_length(i)를 1번만 호출한다면 불필요한 계산도 방지할 수 있다. 다음부터 주의하도록 하자.

오늘은 여기까지.
-2025.01.15-