[크래프톤 정글] day 7 TIL 정수론

• 정수론 (Number Theory)
  • 정수론, 또는 수론은 정수의 성질 또는 정수가 등장하는 경우들을 연구하는 학문,
  • 문제 그 자체는 중학생도 이해할 수 있을 정도로 쉬운 경우가 많다.
  • 참고로 이름은 정수론이지만 주로 소수를 중점으로 다룬다.
    • ex) 페르마의 마지막 정리, 골드바흐 추측, 콜라츠 추측, 리만 가설,…
  • 왜 개발자가 정수론을 배워야할까? 컴퓨터에서 정수는 정확한 값을 가질 수 있기 때문이다.
    • 컴퓨터의 floating point 시스템은 소수점 이상과 소수점 이하를 합쳐서 표현할 수 있는 '유효 숫자' 자리수에 한계가 정해져 있다.
      • floating point 이란? 부동소수점
        • 실수를 컴퓨터상에서 근사하여 표현할 때, 소수점의 위치를 고정하지 않고 그 위치를 나타내는 수를 따로 적는 것으로 유효숫자를 나타내는 가수와 소수점의 위치를 지수로 나누어 표현한다.
      • 예시) 유효 숫자 자리수가 6자리라고 가정.
        • 12345600, 1234560, 12345.6, 1234.56, 123.456, 12.3456, 1.23456, 0.123456, 0.0.123456 ,…. 등 모두 표현 가능하다.
        • Q) 12345600은 8자리인데 왜 유효 숫자가 가능한가요?
          • 이 경우 소수점 이하의 값이 없고(0이고) 동시에 소수점 이상에서 일의 자리와 십의 자리 둘 다 0이기 때문에 이는 유효 정보가 없는 것으로 취급할 수 있기 때문이다.
          • 0.00123456 도 마찬가지로 소수점 이상의 값이 없고(0이고) 소수점 이하에서도 처음 두 자리 모두 0이라 똑같이 유효 정보가 없는 것으로 간주할 수 있다.
          • 이 유효 정보에다 다른 추가 정보를 사용해서 앞에서 든 값을 각각 구분해서 표현하는 것이다.
          • 그런데 12345600과 단 1 차이인 12345601 을 생각해보자.
          • 12345601은 일의 자리가 0이 아니므로 이를 정확하게 표현하기 위해서 유효 숫자는 8자리로 늘어난다. 하지만 앞에서 유효숫자는 6자리가 한계라고 가정했기 때문에, 12345601은 유효 숫자 6자리로 표현할 수 있는 근사값 12345600 (혹은 12345700) 으로 쓰여야 하고 오차가 발생한다.
          • 이 오차는 계산을 거듭할 수록 걷잡을 수 없이 커지기 때문이다.
          • 게다가 컴퓨터에서의 수 표현은 수를 표현할 저장공간의 한계상 정수론에서 말하는 시계 산술을 사용한다.
            • 시계 산술이란?
              • 정수 집합이 유한하다고 간주하는 산술.
  • 소수 (Prime number)
    • 왜 소수를 알아야 할까?
      • 소수를 알면 정수 전체에 대해서 알 수 있기 때문이다.
        • 하세-민코프스키 정리
      • 4 이상의 모든 짝수는 두 소수의 합 으로 표현 가능 ( 1을 소수로 보지 않았을 때)
      • 6 이상의 모든 자연수는 세 소수의 합으로 표현 가능
  • 산술함수
    • 정수론 연구를 위해 만든 특수 함수들..
      • 최대공약수, 최소공배수, 약수 함수
  • 코딩테스트에 나오는 비주류 유형 중 하나인 정수론. 하지만 상위 티어 기업들에서는 나름,…
  • 하지만, 코테에 나오는 수준의 정수론은 대부분 쉽다. (카더라인듯)
  • 유클리드 호제법
    • 유클리드 호제법이란?
      • 호제법이란 2개의 자연수 또는 정식의 최대 공약수를 구하는 알고리즘의 하나.
      • 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r 이라고 하면(a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라 b를 r로 나눈 나머지 r`` 를 구하고, 다시 r을r`` 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때, 나누는 수가 a와 b의 최대공약수이다.
      • 예시
        • 1071 과 1029의 최대공약수
        • 1071은 1029로 나누어 떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42
        • 1029는 42로 나누어 떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21
        • 42는 21로 나누어 떨어진다.
        • 따라서 최대공약수는 21 이다.

        a = 1071
        b = 1029
        
        while b != 0:  # b가 0이 될 때까지 반복
            rest = a % b
            print(f'{a}와 {b}를 나눈 나머지는 {rest}입니다.')
        
            a = b  # b를 a로 대입
            print(f'{b}는 a 위치로 들어가게 됩니다.')
        
            b = rest  # 나머지를 b로 대입
            print(f'{rest}는 b 위치로 들어가게 됩니다.')
        
        print(f'최대 공약수는 {a}입니다.')
        

      • 유클리드 호제법을 이용해 최대공약수를 구하는 건 약 O (log N)만큼의 시간이 걸린다. long long 범위 안쪽의 어떤 수가 들어와도 60번 정도의 연산만 하면 구할 수 있다.
  • N의 약수 구하기
    • 방법 1

    N = int(input())
    
    for i in range(1,N+1):
        if N % i == 0:
            print(f'{i}는 {N}의 약수입니다.')
    

    • O(n) 의 시간복잡도를 갖는다. 여기서 더 줄일 수 없을까요?
    • 방법 2) 각 약수는 짝이 있다. 에서 고안한 방법
      • 12의 약수는?
      • 1 * 12
      • 2 * 6
      • 3 * 4
      • 왼쪽 값(1,2,3)을 알면 오른쪽 값(12,6,4)는 바로 구할 수 있다.
      • 왼쪽 값들은 sqrt(12) 보다 작거나 같은 값들이다.

    import math
    
    N = int(input("숫자를 입력하세요: "))
    
    for i in range(1, int(math.sqrt(N)) + 1):  # sqrt(N)은 float이므로 int로 변환
        if N % i == 0:  # i가 N의 약수라면
            print(f'{i}는 {N}의 약수입니다.')
            
            # i * i가 N이 아닌 경우에만 N // i 출력 (중복된 약수를 방지)
            if i * i != N:
                print(f'{N // i}는 {N}의 약수입니다.'
    

  • 소수 판별하기
    • 기본형, O(N)

    def isPrime(x):
        # 2부터 (x - 1)까지의 모든 수를 확인하며
        for i in range(2, x):
            # x가 해당 수로 나누어떨어진다면
            if x % i == 0:
                return False # 소수 아님
        return True
    
    print(isPrime(int(input())))
    

    • 에라토스테네스의 체 O(NloglogN)
      • 여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 알고리즘
      • N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다.
      • 소수들 간의 연관성(= 소수를 생성할 수 있는 공식)이 나오지 않았으므로 ‘특정 범위 내의 소수’를 판정하는 데에만 효율적. ( 주어진 수 하나가 소수인가? 소수판정법을 이용)
      1. 2부터 N까지의 모든 자연수를 나열한다.
      2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
      3. 남은 수 중에서 i의 배수를 모두 제거한다. (i는 제거하지 않는다.)
      4. 더 이상 반복할 수 없을 때까지 2번과 3번 과정을 반복한다.
    • 골드바흐의 추측 (생략) 백준 문제 나와 있음.
      • https://studyiwthme.tistory.com/127

참고한 블로그

• https://kau-algorithm.tistory.com/27
• https://www.mathhm.com/previous_test/html/summary/number_theory/101.php
• https://st-lab.tistory.com/91
• https://st-lab.tistory.com/81?category=830901
• https://ko.wikipedia.org/wiki/부동소수점
• https://ko.wikipedia.org/wiki/유클리드_호제법
• https://www.mathhm.com/previous_test/html/summary/number_theory/101.php