Algorithm 26일차

알고리즘에 명제와 논리를 활용할 수 있다.

명제란 참과 거짓을 명확히 판별할 수 있다는 문장이다. 예시는 아래와 같다.

두 변의 길이가 같다면 이등변 삼각형이다. (참)

명제가 참이면 대우는 참이고, 명제가 거짓이면 대우는 거짓이다. 예시는 아래와 같다.

이등변 삼각형이 아니면 어느 두 변의 길이를 선택해도 길이가 다르다. (참)

알아야 하는 명제는 아래와 같다.

1. 2로 나눠지는 자연수는 짝수고, 2로 나눠지지 않는 자연수는 홀수다.
2. 마방진은 각 행의 합, 열의 합, 대각선들의 합이 모두 같다.
3. 유리수는 서로소인 두 정수의 나눗셈으로 표현할 수 있고, 표현할 수 없으면 무리수다.
4. 0이 아닌 수로 다른 수를 나눴을 때 나머지가 0이면 나눈 수는 나눠진 수의 약수이다.

알고리즘에 수학 이론을 활용할 수 있다.

활용할 수 있는 수학 이론은 아래와 같다.

1. 페르마의 소정리 : p가 소수고 p가 a의 약수가 아니면 a^p-1 = 1 (mod p) 이다.
2. 배열 차원 변환 : A가 1차원이고 B가 2차원이다.
   그럼 A[i] = B[i/col][i%col], B[i][j] = A[i*col+j] 이다.