꼭 알아야하는 코딩 테스트 유형: 11) #Number_Theory

• 이번에는 코딩 테스트에서 중요한 유형인 'Number Theory(정수론)'에 대해 알아보겠습니다. 정수론은 정수와 그 연산에 대한 학문으로, 수학적인 개념과 원리를 활용하여 문제를 해결하는 방법입니다. 코딩 테스트에서도 자주 출제되는 유형 중 하나이며, 수학적 사고력과 논리적 접근이 요구됩니다.

 

정수론의 개념

 

• 정수론은 다양한 개념과 성질을 포함하고 있으며, 주요한 개념들을 소개하겠습니다.

 

1. 소수(Prime Number): 1과 자기 자신으로만 나누어지는 양의 정수입니다. 소수 판별, 소인수분해 등의 문제에서 활용됩니다.
2. 최대공약수(GCD): 두 수의 공통된 약수 중 가장 큰 수를 의미합니다. 유클리드 호제법을 사용하여 계산할 수 있습니다.
3. 최소공배수(LCM): 두 수의 공통된 배수 중 가장 작은 수를 의미합니다. GCD를 활용하여 계산할 수 있습니다.
4. 오일러 피 함수(φ 함수): 어떤 정수 n보다 작거나 같은 자연수 중 n과 서로소인 수의 개수를 의미합니다.
5. 모듈러 연산(Modular Arithmetic): 나머지 연산을 의미하며, 일반적으로 모듈러 연산이 큰 정답을 요구하는 문제에서 사용됩니다.
6. 확장 유클리드 호제법: GCD를 구하는 동시에 GCD를 만족하는 x와 y 값을 찾는 방법입니다.
7. 중국인의 나머지 정리(CRT): 여러 모듈러 연립 합동식 문제에서 사용되며, 각각의 모듈러에 대한 해가 있는 경우 전체 해를 구할 때 유용합니다.
8. 페르마의 소정리: p가 소수이고 a가 p와 서로소인 경우, a^(p-1) ≡ 1 (mod p)가 성립합니다.
9. 오일러 토템 함수: 양의 정수 n에 대해, n보다 작거나 같고 n과 서로소인 수의 개수를 구하는 함수입니다.

 

코딩 테스트에서의 정수론 문제 접근법

 

• 정수론은 다양한 유형의 문제를 포함하고 있기 때문에, 각 문제마다 다른 접근 방법이 필요합니다. 하지만 몇 가지 일반적인 패턴과 전략을 활용하여 문제에 접근할 수 있습니다.

 

1. 소수 관련 문제: 소수 판별, 소인수분해 등과 같은 소수와 관련된 문제는 주로 빠른 속도로 수행 가능한 알고리즘을 사용합니다. 에라토스테네스의 체, 밀러-라빈 소수 판별 알고리즘 등이 유용한 도구입니다.
2. 최대공약수와 최소공배수: 두 수의 최대공약수와 최소공배수를 구하는 문제는 주로 유클리드 호제법을 사용하여 해결할 수 있습니다. GCD(a, b) = GCD(b, a % b)를 재귀적으로 계산하면 됩니다.
3. 모듈러 연산: 모듈러 연산은 큰 정답을 요구하는 경우나 숫자가 매우 커서 오버플로우가 발생할 가능성이 있는 경우에 사용됩니다. 모듈러 연산 규칙을 활용하여 중간 결과를 적절히 줄여나가면서 원하는 값을 구할 수 있습니다.
4. 오일러 피 함수와 페르마의 소정리: 오일러 피 함수와 페르마의 소정리는 모듈러 연산과 결합하여 다양한 정확한 결과를 얻을 때 유용합니다. 이들 개념을 적절하게 활용하여 계산량을 줄이거나 원하는 값을 도출할 수 있습니다.
5. 확장 유클리드 호제법과 중국인의 나머지 정리: 큰 정답이 요구되거나 모듈러 연립 합동식으로 주어진 경우에 사용됩니다. 확장 유클리드 호제법은 GCD 계산과 동시에 GCD를 만족하는 x와 y 값을 찾아내는 방법입니다. 중국인의 나머지 정리는 여러 모듈러 연립 합동식에서 전체 해를 구할 때 활용됩니다.
6. 수론적 성질 활용: 정수론에서 다양한 수론적 성질을 활용하여 문제를 해결할 수 있습니다. 예를 들어, 나머지 연산의 분배법칙, 지수 법칙, 모듈러 연산의 역원 등을 적절히 이용하여 문제를 간단하게 풀이할 수 있습니다.

 

9020번: 골드바흐의 추측

  문제  
 

• 1보다 큰 자연수 중에서  1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다.
• 골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다.
• 2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오. 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

 
  해결 방법  
 

• 골드바흐의 추측은 임의의 짝수는 두 소수의 합으로 나타낼 수 있다는 가설입니다. 이 문제에서는 주어진 짝수 n을 두 소수의 합으로 나타내되, 두 소수 차이가 가장 작은 경우를 찾아 출력하도록 요구하고 있습니다.
• 이 문제를 해결하기 위해서는 먼저 에라토스테네스 체 알고리즘을 사용하여 주어진 범위 내 모든 소수를 구합니다. 그 후, 입력된 짝수 n을 기준으로 양쪽 방향으로 탐색하며 최초로 만나게 되는 두 개의 소수가 답이 됩니다.

def prime_list(n):
    sieve = [True] * (n+1)
    for i in range(2, int(n ** 0.5)+1):
        if sieve[i]:
            for j in range(i*2, n+1, i):
                sieve[j] = False
    return [i for i in range(2, n+1) if sieve[i]]

def goldbach(n):
    prime_num = prime_list(n)
    idx = max([i for i in range(len(prime_num)) if prime_num[i] <= n/2])
    
    for i in range(idx, -1, -1):
        if n-prime_num[i] in prime_num:
            return [prime_num[i], n-prime_num[i]]

for _ in range(int(input())):
    print(' '.join(map(str, goldbach(int(input())))))

 

2436번: 공약수

  문제  
 

• 어떤 두 자연수에 공통인 약수들 중에서 가장 큰 수를 최대공약수라고 하고, 두 자연수의 공통인 배수들 중에서 가장 작은 수를 최소공배수라고 한다.
• 예를 들어, 두 자연수 12와 90의 최대공약수는 6이며, 최소공배수는 180이다.
• 이와 반대로 두 개의 자연수 A, B가 주어졌을 때, A를 최대공약수로, B를 최소공배수로 하는 두 개의 자연수를 구할 수 있다. 그러나, 이러한 두 개의 자연수 쌍은 여러 개 있을 수 있으며, 또한 없을 수도 있다.
• 예를 들어, 최대공약수가 6이며 최소공배수가 180인 두 정수는 위의 예에서와 같이 12와 90일 수도 있으며, 30과 36, 18과 60, 혹은 6과 180일 수도 있다. 그러나, 최대공약수가 6이며 최소공배수가 20인 두 자연수는 있을 수 없다.
• 두 개의 자연수가 주어졌을 때, 이 두 수를 최대공약수와 최소공배수로 하는 두 개의 자연수를 구하는 프로그램을 작성하시오. 

 
  해결 방법  
 

• 이 문제에서는 주어진 최대공약인 G와 최소공배수인 L이 있을 때, G와 L을 가지는 두 수 중에서 합이 가장 작은 두 수를 찾아 출력하도록 요구하고 있습니다.
• 이 문제를 해결하기 위해서는 다음의 원리를 이해해야 합니다. 두 수 A, B가 있을 때, 이들의 최대공약수가 G이고 최소공배수가 L이라면, A * B = G * L입니다. 그러므로 A와 B는 각각 G * (L/G)의 약수입니다.
• 따라서 L/G의 약수 중에서 두 수의 합이 가장 작은 경우를 찾아 출력하면 됩니다. 이때 주어진 조건에 따르면 두 수는 서로소여야 하므로, 약수 중에서 서로소인 경우만 고려하면 됩니다.

import math

def solve(G, L):
    if L % G != 0: return -1
    else:
        div = L // G
        for i in range(int(math.sqrt(div)), 0, -1):
            if div % i == 0 and math.gcd(i, div//i) == 1:
                return [i*G, (div//i)*G]

G,L = map(int,input().split())
print(' '.join(map(str, solve(G, L))))

• 위 코드에서 solve 함수는 입력된 최대공약수 G와 최소공배수 L에 대하여 문제를 해결하는 역할을 합니다. 만약 L이 G로 나누어떨어지지 않으면 -1을 반환하여 적절한 숫자 조합이 없음을 나타냅니다.
•  그렇지 않은 경우에는 div = L // G 연산으로 숫자 조합 후보를 찾습니다. 그 후 for문을 통해 가능한 숫자 조합 중에서 두 수가 서로소인 것을 찾아 반환합니다. 여기서 python 내장함수인 'math.gcd'를 사용하여 두 수의 최대공약수를 구하고 이 값이 1인 경우에만 해당하는 숫자 쌍을 선택합니다.

 

• 정리하자면 정수론 문제 해결 방법은 크게 세 단계로 나뉘며 첫째는 필요한 개념과 원리 파악, 둘째는 해당 원리에 근거한 문제 접근 방법 설정 및 코드 설계 그리고 마지막으로 설계된 로직에 따른 코드 작성입니다.