나머지 연산

  • (A+B)%M = (A%M + B%M)%M

  • (A*B)%M = (A%M * B%M)%M

  • (A-B)%M = (A%M - B%M + M)%M

    (6$3-5%3)%3을 고려해 보자.

  • 나누기는 불가

  • 관련 문제

    • 1: https://www.acmicpc.net/problem/4375

약수

  • 두 자연수 A와 B가 있을 때, A=BC를 만족하는 C를 A의 약수라고 함

  • 관련 알고리즘

    1. 1부터 A까지의 모든 자연수로 나눔: $O(N)$

      1
2
3

      for i in range(1, N+1):
	if N%i == 0:
		print(f"{i}는 {N}의 약수")

    2. 1부터 $\sqrt{\text A}$까지의 모든 자연수로 나눔: $O(\sqrt {N})$

      1
2
3

      for i in range(1, int(N**0.5)+1)
	if N%i == 0:
		print(f"{i}, {N}는 {N}의 약수")

    3. N보다 작거나 같은 모든 자연수는 N의 약수와 약수가 아닌 수로 나눌 수 있고, 약수의 개수는 그렇지 않은 수보다 매우 작으므로 불필요한 연산을 줄이기 위해 배수를 이용해 약수를 구할 수 있다.

      1부터 24까지 모든 자연수에 대해 각 자연수의 약수의 합을 구해보자. 각 자연수에 대해 약수의 합을 구하는 것은 $O(N)$ 혹은 $O(\sqrt N)$인데, 이를 $N$번 하므로 $O(N^2)$이거나 $O(N\sqrt N)$이다. 하지만 1은 모든 수의 약수이고, 2는 2의 배수들의 약수임을 이용하면 1부터 N까지의 수 * 각 수의 총 개수를 구하면 되고, 각 수의 총 개수는 $N/수$ 이므로 $1\times \lfloor N/1\rfloor + 2\times \lfloor N/2 \rfloor +\cdots +N \times \lfloor N/N \rfloor$으로 $O(N)$으로 구할 수 있다.

  • 관련 문제

    • 약수: https://www.acmicpc.net/problem/1037
    • 약수의 합 2: https://www.acmicpc.net/problem/17427
    • 약수의 합: https://www.acmicpc.net/problem/17425

최대 공약수와 최소 공배수

  • 두 수 A와 B의 최대 공약수 G는 A와 B의 공통된 약수 중 가장 큰 정수로, 줄여서 GCD라고 쓴다.

  • 최대 공약수가 1인 두 수를 서로소(Coprime)이라 한다.

  • 관련 알고리즘

    1. 2부터 $\min(A,B)$까지 모든 정수로 나누어 구할 수 있다.

      1
2
3

      for i in range(2, min(A, B)+1):
	if A%i ==0 and B%i ==0:
		gcd = i

    2. 유클리드 호제법(Euclidean Algorithm): $a$를 $b$로 나눈 나머지를 $r$이라 했을 때, $\gcd(a, b)=\gcd(b,r)$임을 이용한다. $r=0$일 때 $b$가 최대 공약수이다.

      1
2
3
4
5

      def gcd(A, B):
	if B==0:
		return A
	else:
		return gcd(B, A%B)

    세 수의 최대 공약수는 $\gcd(a, b,c)=\gcd(\gcd(a,b),c)$로 구할 수 있다. 여러 개의 수도 동일한 방식으로 구할 수 있다.

  • 두 수의 공통된 배수 중에서 가장 작은 정수로, 줄여서 LCM이라 쓴다.

  • 최대 공약수를 $g$라 하면, 최소 공배수 $l=g\times(a/g)\times(b/g)$이다.

  • 관련 문제
    • 최대공약수와 최소공배수: https://www.acmicpc.net/problem/2609

소수

  • 약수가 1과 자기 자신 밖에 없는 수

  • 관련 알고리즘

    1. 어떤 수 N이 소수인지 판별

      • 2부터 $N-1$까지 나누어 떨어지는지 확인 $\rightarrow O(N)$
      • 1과 $N$을 제외한 가장 작은 약수는 2이므로, $\sqrt N$를 기준으로 이와 대칭인 $N/2$부터 $N$까지는 약수가 존재하지 않음. 따라서, 2부터 $N/2$까지 확인$\rightarrow O(N/2)$
      • 약수는 나누어 떨어지는 수가 존재하므로, 나누는 수와 나누어 떨어지는 수 중 하나만 확인하면 된다. 따라서, 2부터 $\sqrt N$까지 확인 $\rightarrow O(\sqrt N)$

    2. N 이하의 모든 소수를 찾는 방법

      • 1번 방식을 사용하면 $O(N\sqrt N)$

      • 에라토스테네스의 체

        1. 2부터 $N$까지 모든 수를 써놓는다.

        2. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.

        3. 그 수는 소수이고, 이제 그 수의 배수를 모두 지운다.

          그 수의 배수를 지울 때, 그 수의 제곱부터 지우면 됨. 그보다 작은 수들은 이미 제거됨

  • 관련 문제

    • 소수 찾기: https://www.acmicpc.net/problem/1978
    • 소수 구하기: https://www.acmicpc.net/problem/1929
    • 골드바흐의 추측: https://www.acmicpc.net/problem/6588

Leave a comment

You may also enjoy