[Algorithm] 나머지 연산과 페르마의 소정리

이 문제를 풀며 정리한 것이다. 문제는 아래와 같이 nCr를 P로 나누었을 때, 그 값을 구하는 것이다. 여기서 N의 값이 매우 큰 경우 모듈러의 연산을 통해 분모항과 분자항을 분리해주어야 한다. 1. 모듈러의 연산 1. a mod P + b mod P = (a+b) mod P 2. a mod P - b mod P = (a-b) mod P 3. a mod P * b mod P = (a*b) mod P 모듈러의 연산에서는 나눗셈이 없다. 그래서 분자항을 괜찮지만, 분모항을 어떻게 처리해줘야 할지 고민해야 한다. 분모항을 처리하기 위해 사용하는 것이 페르마의 소정리이다. 2. 페르마의 소정리 a가 3이고, P가 5 일 때, 3의 거듭제곱을 5로 나눈 나머지는 아래와 같은 특징이 있다. 이러한 규칙을 페르마의..

→2022.04.11

Computer Science/Algorithm

완전 탐색 - 순열, 중복 순열, 조합, 중복 조합, 부분 집합

1. 순열(Permutation) 순열 - 서로 다른 n개 중 r개를 순서를 고려하여 선택하는 것 - n = 6, r = 4 이면, P(6, 4) = 6 X 5 X 4 X 3 = 360 - 경우의 수가 11! 이 넘으면 순열로 풀 수 없음(경우의 수: 4억 이상) 코드로 보는 순열 - 원소와 N, R이 주어졌을 때 순열을 구하는 코드 import java.util.Arrays; import java.util.Scanner; public class Test { static int N, R; static boolean[] isSelected; static int[] input, output; private static void permutation(int cnt){ if(cnt == R){ // R개를 뽑았..

→2022.02.20

[Algorithm] 나머지 연산과 페르마의 소정리

완전 탐색 - 순열, 중복 순열, 조합, 중복 조합, 부분 집합

티스토리툴바