day48.py

from random import shuffle

def make_lotto_numbers():
    pool = list(range(1, 45+1))
    shuffle(pool)
    return pool[:6], pool[6]

def main():
    input_nums = set(map(int, input("숫자 6개를 입력: ").split()))
    if len(input_nums) != 6:
        return print("중복되지 않는 숫자 6개를 입력해주세요.")
    if not all(map(lambda x: 1 <= x <= 45, input_nums)):
        return print("1~45 사이의 숫자를 입력해 주세요.")
    
    lotto_nums, bonus_num = make_lotto_numbers()
    lotto_nums = set(lotto_nums)
    sames = len(input_nums & lotto_nums)
    get_bonus = bonus_num in input_nums

    print(f"당신의 숫자: {input_nums}")
    print(f"추첨된 숫자: {lotto_nums} + 보너스번호 {bonus_num}")
    print(f"맞춘 번호: {sames}개")

    if sames == 6:
        print("1등입니다.")
    elif sames == 5 and get_bonus:
        print("2등입니다.")
    elif sames == 5:
        print("3등입니다.")
    elif sames == 4:
        print("4등입니다.")
    elif sames == 3:
        print("5등입니다.")
    else:
        print("낙첨입니다.")

if __name__ == "__main__":
    main()

day48_explaination.md

Day 48. 로또 번호 시뮬레이터

사용자로부터 로또 번호를 받아서, 몇 등에 당첨되었는지 시뮬레이션합니다.

코드 설명

def make_lotto_numbers():
    pool = list(range(1, 45+1))
    shuffle(pool)
    return pool[:6], pool[6]

로또 번호를 추첨합니다. 1부터 45까지의 정수가 담긴 리스트를 만들고, 이 리스트를 완전히 셔플한 뒤 첫 6개 번호만을 받아오는 방식입니다. 번호 추첨을 이렇게 구현한 이유는 다음과 같습니다.

• 구현을 최대한 단순하게 만들어서 문제가 있을 여지를 줄이기 위함입니다.
  • 특히, 모든 값이 편의 없이 항상 같은 확률으로 뽑힐 것임을 확실하게 하기 위함입니다.
  • 뽑힌 값에 중복값이 없음을 확실하게 하기 위함입니다.
• 번호 추첨이 랜덤값과 관계없이 항상 일정한(예측 가능한) 연산 시간을 사용하게 하기 위함입니다.

def main():
    input_nums = set(map(int, input("숫자 6개를 입력: ").split()))
    if len(input_nums) != 6:
        return print("중복되지 않는 숫자 6개를 입력해주세요.")

set 자료구조는 중복된 값을 제거합니다. 따라서 중복된 값을 넣거나 6개 이외의 숫자를 넣을 경우 여기에서 걸러지게 됩니다.

    if not all(map(lambda x: 1 <= x <= 45, input_nums)):
        return print("1~45 사이의 숫자를 입력해 주세요.")

input_nums의 모든 값들이 1 <= x <= 45 조건을 만족하는지 검사합니다.

    lotto_nums, bonus_num = make_lotto_numbers()
    lotto_nums = set(lotto_nums)
    sames = len(input_nums & lotto_nums)
    get_bonus = bonus_num in input_nums

코드의 가독성을 높이기 위한 변수 선언입니다.

두 set 객체간의 & (bitwise and) 연산은, 두 집합 간의 교집합을 반환합니다. 이를 sames를 선언할 때 사용하였습니다.

    print(f"당신의 숫자: {input_nums}")
    print(f"추첨된 숫자: {lotto_nums} + 보너스번호 {bonus_num}")
    print(f"맞춘 번호: {sames}개")

    if sames == 6:
        print("1등입니다.")
    elif sames == 5 and get_bonus:
        print("2등입니다.")
    elif sames == 5:
        print("3등입니다.")
    elif sames == 4:
        print("4등입니다.")
    elif sames == 3:
        print("5등입니다.")
    else:
        print("낙첨입니다.")

로또 규칙에 따라 등수를 정합니다.

day53.py

from math import sqrt, floor

class PrimeChecker:
    def __init__(self):
        self.__primes = set()
        self.__primes_list = list()
        self.__check_size = 1

    def is_prime(self, num):
        self.__expand_primes_until(num)
        return num in self.__primes

    def __expand_primes_until(self, num):
        if num <= self.__check_size:
            return

        for i in range(self.__check_size, num + 1):
            if self.__check_prime(i):
                self.__add_prime(i)
            self.__check_size = i

    def __add_prime(self, num):
        if num in self.__primes:
            return

        self.__primes.add(num)
        self.__primes_list.append(num)

    def __check_prime(self, num):
        if num <= 1: return False

        check_limit = floor(sqrt(num)) + 1
        for prime in self.__primes_list:
            if prime > check_limit:
                break
            if num % prime == 0:
                return False

        return True

def factorize(num):
    primecheck = PrimeChecker()

    factors = []
    for i in range(2, num):
        if not primecheck.is_prime(i):
            continue

        mod = num % i
        if mod == 0:
            factors += [i]

    if not factors:
        factors = [num]

    return factors

if __name__ == "__main__":
    print(factorize(12))
    print(factorize(7))
    print(factorize(100008))

day53_explaination.md

Day 53. 소인수분해

주어진 값을 소인수분해해서 소인수를 오름차순으로 반환하는 함수를 만들어봅시다.

코드 설명

class PrimeChecker

소수를 판별합니다. PrimeChecker는 이미 계산한 값은 두 번 다시 계산하지 않습니다.

PrimeChecker 클래스에 대한 자세한 설명은 https://gist.github.com/nulta/a74706676c9cebd19ec246c48fea561d 링크를 참조하세요.

---

소수 판별을 PrimeChecker에 맡겨버린 이상, 소인수분해는 아래와 같이 아주 간단하게 구현할 수 있습니다.

def factorize(num):
    primecheck = PrimeChecker()

    factors = []
    for i in range(2, num):
        if not primecheck.is_prime(i):
            continue

        mod = num % i
        if mod == 0:
            factors += [i]

    if not factors:
        factors = [num]

    return factors

위 코드는 2부터 num까지의 모든 정수를 순회하며, 소수이면서 num의 인수인지를 판별하고 리스트에 삽입합니다.

만약 삽입된 수가 없다면, num 자체가 소수라는 뜻이기에 이 부분도 처리합니다.

day54.py

from itertools import permutations
from math import sqrt, floor

class PrimeChecker:
    def __init__(self):
        self.__primes = set()
        self.__primes_list = list()
        self.__check_size = 1

    def is_prime(self, num):
        self.__expand_primes_until(num)
        return num in self.__primes

    def __expand_primes_until(self, num):
        if num <= self.__check_size:
            return

        for i in range(self.__check_size, num + 1):
            if self.__check_prime(i):
                self.__add_prime(i)
            self.__check_size = i

    def __add_prime(self, num):
        if num in self.__primes:
            return

        self.__primes.add(num)
        self.__primes_list.append(num)

    def __check_prime(self, num):
        if num <= 1: return False

        check_limit = floor(sqrt(num)) + 1
        for prime in self.__primes_list:
            if prime > check_limit:
                break
            if num % prime == 0:
                return False

        return True


def permutation_numbers(num):
    return map(int, map(''.join, permutations(str(i))))


if __name__ == "__main__":
    prime_checker = PrimeChecker()
    circular_prime_count = 0
    query_range = 1_000_000

    for i in range(query_range):
        is_circular_prime = True

        for x in permutation_numbers(i):
            if not prime_checker.is_prime(x):
                is_circular_prime = False
                break

        if is_circular_prime:
            circular_prime_count += 1
    
    print(f"There is {circular_prime_count} circular prime numbers where 1 < N < {query_range}.")

day54_explaination.md

Day 54. 재배열 가능 소수 개수 찾기

"재배열 가능 소수"는, 각 자릿수의 숫자를 어떻게 바꾸어도 소수인 수를 말합니다. 이를테면 17과 71은 순환하는 소수입니다.

재배열 가능 소수는 100 밑으로는 13개가 있습니다. 1,000,000 밑으로는 몇 개나 있을까요?

코드 설명

class PrimeChecker

소수를 판별합니다. PrimeChecker는 이미 계산한 값은 두 번 다시 계산하지 않습니다.

PrimeChecker 클래스에 대한 자세한 설명은 https://gist.github.com/nulta/a74706676c9cebd19ec246c48fea561d 링크를 참조하세요.

---

def permutation_numbers(num):
    return map(int, map(''.join, permutations(str(i))))

자연수 i에 대해, i를 재배열해서 얻을 수 있는 모든 정수를 반환하는 이터레이터입니다.

• map(int, map(''.join, permutations(str(i))))는, 정수 i의 각 숫자를 재배열하여 만들 수 있는 모든 정수를 순회합니다.
  • str(i)를 이용해 i를 str로 변환합니다.
  • str은 Iterable이기 때문에 순회할 수 있습니다. 순회하면 str을 이루는 문자 하나하나를 얻습니다.
  • itertools.permutations(str(i))를 사용하여 각 문자를 재조합해서 만들 수 있는 모든 문자열의 이터레이터를 얻습니다.
  • map(''.join, ...)을 이용하여, 얻은 값 x를 전부 ''.join(x)로 매핑합니다.
  • map(int, ...)을 이용하여 얻은 값을 정수로 다시 반환합니다.

이렇게 얻어낸 이터레이터에는 중복되는 값이 있지만, PrimeChecker가 계산한 값을 캐싱한다는 점을 고려하면 이는 용인 가능합니다.

if __name__ == "__main__":
    prime_checker = PrimeChecker()
    circular_prime_count = 0
    query_range = 1_000_000

    for i in range(query_range):
        is_circular_prime = True

        for x in permutation_numbers(i):
            if not prime_checker.is_prime(x):
                is_circular_prime = False
                break

        if is_circular_prime:
            circular_prime_count += 1
    
    print(f"There is {circular_prime_count} circular prime numbers where 1 < N < {query_range}.")

• 그렇게 얻은 모든 값을 순회하면, 재배열 가능 소수 여부를 검사할 수 있습니다.
• 출력값은 다음과 같습니다.

There is 22 circular prime numbers where 1 < N < 1000000.