학습 목표

  • PS에서 사용되는 기초적인 수학 이론에 대해 알아봅시다.
  • 약수, 배수, 소인수 분해, 모듈로의 개념에 대해 알아봅시다.
  • 약수를 $O(\sqrt{n})$의 시간복잡도로 구하는 방법에 대해 알아봅시다.
  • 소인수 분해를 $O(\sqrt{n})$의 시간복잡도로 구하는 방법에 대해 알아봅시다.

나눗셈과 나머지

나눗셈에서 나머지는 다음과 같이 정의됩니다:

두 정수 $a$와 $b$에 대해 $a$를 $b$로 나눌 때, 나머지는 $a$를 $b$로 나눈 나머지 값으로 정의됩니다. 수학적으로 표현하면 $a$를 $b$로 나눈 몫이 $q$이고, $r$이 나머지일 때, $a = bq + r$이 성립합니다. 이때, $0 \leq r < \mid b \mid$를 만족합니다.

예를 들어, $17 \div 5$를 계산하면, 몫은 3이고 나머지는 2가 됩니다. 즉, $17 = 5 \times 3 + 2$입니다.

나눗셈과 관련된 용어는 다음과 같이 정의됩니다:

  • 제수 (Dividend):
    나누어지는 수로, 나누려는 수를 제수라고 합니다. 주로 $a$로 표기됩니다.

  • 피제수 (Divisor):
    나누는 수로, 나누는 수를 피제수라고 합니다. 주로 $b$로 표기됩니다.

  • 몫 (Quotient):
    나눗셈의 결과로 나온 정수 부분을 의미합니다. 몫은 제수를 피제수로 나눈 값이 됩니다. 주로 $q$로 표기됩니다.

  • 나머지 (Remainder):
    나눗셈의 결과로 나머지 부분을 의미합니다. 나누는 수로 나눈 후의 나머지 값이 됩니다. 주로 $r$로 표기됩니다.

예를 들어, $a$를 $b$로 나누었을 때, 몫은 $\lfloor \frac{a}{b} \rfloor$이고, 나머지는 $a - b \lfloor \frac{a}{b} \rfloor$으로 계산됩니다.

약수와 배수

약수와 배수는 다음과 같이 정의됩니다.

  • 약수 (Divisor):
    어떤 정수를 다른 정수로 나누어 떨어지게 하는 정수를 그 수의 약수라고 합니다. 즉, 정수 $a$가 정수 $b$를 약수로 가지려면 $a$를 $b$로 나누었을 때 나머지가 0이어야 합니다. 예를 들어, 6의 약수는 1, 2, 3, 6입니다.

  • 배수 (Multiple):
    어떤 정수 $a$를 다른 정수 $b$로 곱한 수를 $b$의 배수라고 합니다. 정수 $a$가 정수 $b$의 배수이려면 $a$를 $b$로 나눈 나머지가 0이어야 합니다. 예를 들어, 10은 5의 배수이며, $10 = 5 \times 2$입니다.

또한, 편의를 위해 다음 기호를 정의합시다. 배수를 나타내는 기호는 수학적으로 세로 막대 기호 $\mid$를 사용할 수 있습니다. 이 기호를 사용하여 정의를 설명할 수 있습니다.

예를 들어, $10$이 $5$의 배수임을 나타내는 수식은 $5 \mid 10$으로 표현할 수 있습니다. 이는 $10$을 $5$로 나누었을 때 나머지가 $0$이라는 의미입니다. 또한, $5$는 $10$의 약수라는 표현으로도 해석할 수 있습니다.

소수와 소인수 분해

또한, 우리는 특별한 수인 소수를 다음과 같이 정의할 수 있습니다.

  • 소수 (Prime Number): 소수는 1보다 큰 자연수 중에서 1과 자기 자신만을 약수로 갖는 수를 말합니다. 즉, 양의 약수가 1과 자기 자신뿐인 자연수를 소수라고 합니다. 예를 들어, 2, 3, 5, 7, 11, 13 등은 소수입니다.

소수는 합성수와 대비되며, 수학에서 아주 중요한 성질을 갖고 있습니다. 우리가 나중에 배울 수학 내용들도 소수를 활용한 내용들이 많습니다.

특히 중요한 성질 중 하나로, 우리는 모든 수를 소수의 곱으로 나타낼 수 있습니다. 이에 대한 증명은 다음과 같습니다.

소인수 분해의 존재성 증명

다음 명제를 증명하는 것을 통해, 소인수 분해가 존재함을 증명할 수 있습니다.

어떤 $1$보다 큰 임의의 양의 정수 $n$에 대하여, 두 번째로 작은 약수는 소수이다.

  • 증명

귀류법을 통해 증명할 수 있습니다.
어떤 $1$보다 큰 임의의 양의 정수 $n$에 대하여, 두 번째로 작은 약수가 합성수라고 가정합시다. ($1$은 무조건 가장 작은 약수이기 때문에 고려할 필요가 없습니다.) 이 두 번째로 작은 약수를 $m$이라고 하면, 합성수의 정의에 따라 $\exists l \text{ such that } l \mid m \text{ where 1 < l < m}$ 이 경우 $l \mid n$이므로 $l$도 $n$의 약수입니다.
따라서 $l$이라는 $m$보다 작고 $1$보다 큰 약수가 존재하므로 $m$이 두 번째로 작은 약수라는 가정에 모순됩니다. 따라서, 위 명제는 참입니다.

위의 명제를 통해 임의의 $1$보다 큰 양의 정수 $n$은 $n = p_1 n_1$으로 분해할 수 있습니다. 이 과정을 계속 반복하면 소인수 분해가 항상 존재한다는 것을 알 수 있습니다. 할 수 있다는 것을 알 수 있습니다.

소인수 분해의 유일성

소인수분해는 또한 순서에 관계 없이 생각할 때 단 하나의 소인수분해만 존재합니다. 이와 관련된 증명은 산술의 기본 정리를 참고해주십시오.

모듈로와 합동

우리는 여기서 나눗셈의 나머지에 집중할 수 있습니다. 왜냐하면, 나눗셈의 나머지는 순환하는 속성을 가지고 있기 때문이죠.

과제 문제

번호 문제번호 제목 난이도 분류
0 1003 피보나치 함수 S3 DP, 시간복잡도
1 1912 연속합 S2 DP
2 21463 1로 만들기 S3 DP
3 2293 동전 1 G5 DP
4 12865 평범한 배낭 G5 DP, 배낭 문제
5 2579 계단 오르기 S3 DP
6 11053 가장 긴 증가하는 부분 수열 S2 DP
7 11054 가장 긴 바이토닉 부분 수열 G4 DP
8 11055 가장 큰 증가하는 부분 수열 S2 DP
9 12852 1로 만들기 2 S1 DP, 최단거리 역추적
10 11726 2xn 타일링 S3 DP
11 11727 2xn 타일링 S3 DP
12 2133 타일 채우기 G4 DP, 챌린지
13 2294 동전 2 S4 DP, 챌린지
14 1750 서로소의 개수 S5 DP, 배낭 문제, 챌린지

다음시간 예고

  • 8주차