오일러 프로젝트 26

오일러 프로젝트 26 번은 단위분수에서 가장 긴 순환마디를 갖게 만드는 분자의 값을 구하는 문제이다. 20번대 문제라 하기에는 많이 쉽다.

분자가 1인 분수를 단위분수라고 합니다.

분모가 2에서 10까지의 단위분수는 아래와 같습니다.

숫자 위에 찍힌 점은 순환마디를 나타내는데, 1/6의 경우 순환마디는 “6”으로 0.166666…처럼 6이 무한히 반복됨을 뜻합니다. 같은 식으로 1/7은 6자리의 순환마디(142857)를 가집니다. d 를 1000 이하의 정수라고 할 때, 단위분수 1/d 의 순환마디가 가장 긴 수는 무엇입니까?

http://euler.synap.co.kr/prob_detail.php?id=26

접근

분모/분자 형태로 표기한 값을 소수로 표현하기 위해서는 실제로 분자를 분모로 나눠보면 된다. 소수점 이하의 나누기를 손으로 하는 경우, 자리수를 계속 내려가면서 나누는데, 앞자리의 나머지가 다음자리의 몫이되는 것이 반복된다. 순환마디가 나타나는 것은 특정 단계의 몫과 나머지가 반복되는 시점이다. 따라서 매 순간의 (몫, 나머지) 쌍을 기록하다가, 방금 나온 결과가 이전에 나온 적이 있는지, 그리고 그게 몇 번 전에 나왔는지를 알면 그게 바로 순환마디의 길이가 된다.

def test(d):
  n = 1 ## 몫
  paths: list[(int, int)] = []
  while True:
    result = divmod(n, d)
    if result[1] is 0: ## 나눠져버렸...
      return 0
    if result in paths: ## 몫, 나머지가 동일했던 패턴찾기
      return len(paths[paths.index(result):])
    else:
      paths.append(result)
    n = result[1] * 10 ## 다음 나누기의 몫은 지금의 나머지임

xs = [(x, test(x)) for x in range(2, 1001)]
print(max(xs, key=lambda x: x[1])[0])

보너스 : Swift 풀이

사실 로직이 간단해서 따로 쓰지 않으려고 했는데, 몇가지 노트할 만한 것이 있다.

  • Swift의 튜플은 파이썬과 달리 배열/사전의 키가 될 수 없고, 그 자체로는 Equatble 이 아니다. 따라서 index(of:) 를 쓸 수 없고, index(where:{ $0.0 == x.0 && $0.1 == x.1 }) 이런식으로 비교해줘야 한다.
typealias Result = (Int, Int)
func divmod(_ a: Int, _ b: Int) -> DivResult { return (a / b, a % b) }
func test(_ d: Int) -> Int {
  var q = 1
  var paths: [Result] = []
  while true {
    let res = divmod(q, d)
    if let pos = (path.index{ $0.0 == res.0 && $0.1 == res.1 }) {
      return paths.count - pos
    } else {
      paths.append(res)
    }
    q = res.1 * 10
  }
}

let result = (2...1000).map{ ($0, test($0)) }
             .reduce((0, 0)){ $0.1 > $1.1 ? $0 : $1}
print(result.0)

그외

나누기 혹은 분수 계산과 관련된 문제가 오일러 프로젝트 내에 몇 개 있는데, 정말 헷갈림이 많이 유발된다. 코드는 간단해 보이지만, 중간중간에 여러 숫자들을 넣고 테스트해볼 것을 권장한다.

  • 키위새

    안녕하세요! 너무 좋은 글 감사드립니다.
    오일러 프로젝트를 풀고 있는데, 코드를 보고 정확히 이해가 되지 않아서..
    혹시 조금 더 설명 부탁드려도 될까요?
    막 배우기 시작해서 코드를 봐도 알고리즘이 한눈에 들어오지가 않네요 ㅠㅠ
    정말 감사합니다!

    • 분수를 소수로 표현하기 위해서는 분자를 분모로 나누는데요, 위 코드는 나누기를 손으로 하는 과정을 따라가는 겁니다. 몫으로 쓰이는 숫자들을 하나씩 붙여가면서 이 때 나머지에 10을 곱하면서 다음 나눗셈의 몫이 되게 되지요.

      이 때 몫이 되는 값이 이전에 출현한 값이면 그 시점부터 순환마디가 시작됩니다. 따라서 매번 나눠가면서 몫을 임시 리스트에 추가하고, 그 몫이 다시 나타나는지를 체크하고, 다시 나타난다면 그 몫이 나타난 시점 이후에 등장한 몫의 개수만큼 순환마디가 나타나니, 그 길이를 찾으면 됩니다.

      • 키위새

        아 네 친절한 설명 감사드립니다!