알고리즘
-
모듈러 연산의 분배 법칙 (곱셈)알고리즘 2023. 12. 2. 18:47
모듈러 연산의 분배 법칙모듈러 연산의 분배 법칙에 따라 다음이 성립한다.(A×B) mod N(A \times B) \ mod \ N(A×B) mod N = (A mod N)×(B mod N) mod N(A \ mod \ N) \times (B \ mod \ N) \ mod \ N(A mod N)×(B mod N) mod N 증명A와 B는 다음과 같이 쓸 수 있다.A=aC+mA = aC + mA=aC+m B=bC+nB = bC + nB=bC+n (C는 몫, m과 n은 나머지) 따라서 (A×B) mod C(A \times B) \ mod \ C(A×B) mod C 를 다음과 같이 표현할 수 있다.= ((aC+m)×(bC+n)) mod C((aC + m) \times (bC + n)) \ mod \ ..
-
경우의 수, 순열, 조합알고리즘 2023. 11. 25. 19:16
💡 책을 참고 했습니다. 경우의 수(곱의 법칙)사건1이 일어나는 경우가 N가지, 사건2가 일어나는 경우가 M가지일 때 사건1과 사건2가 일어나는 경우의 조합은 모두 NM가지 이다.이런 곱의 법칙은 사건이 3개 이상인 경우로도 확장할 수 있다. 예를 들어 “형태”, “색”, “타입”을 선택해서 로고 마크를 만드는 경우를 생각해 보자.형태 : 원, 사각형, 삼각형색 : 붉은색, 파란색타입 : 1, 2, 3, 4 로고 마크를 만드는 방법은 모두 3 x 2 x 4 = 24가지이다. n개의 대상을 나열하는 방법의 수n개의 대상을 나열하는 방법은 n!n!n! = n×(n−1)×(n−2)…×2×1n \times (n-1) \times (n-2)… \times 2 \times 1n×(n−1)×(n−2)…×2×1 로..
-
소수 판정법알고리즘 2023. 11. 25. 16:56
💡 책을 참고 했습니다.소수 - 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수 단순한 소수 판정법어떤 수가 소수인지 판정하려면 어떤 방법을 사용해야 할까?먼저 가장 단순한 방법을 생각해보자. 소수는 1과 자기 자신만을 약수로 가지므로 1과 자기 자신을 제외한 수들로 나눴을 때 나누어지지 않으면 소수라는 것을 알 수 있다.예) 53 → 2~52까지의 자연수로 나누어본다. 시간복잡도 - O(N)O(N)O(N) 빠른 소수 판정법사실 2부터 N−1N-1N−1까지 전부 확인할 필요는 없고, n\sqrt{n}n 까지만 나누어보면 소수인지 판정할 수 잇다.예) 53=7.28...\sqrt{53} = 7.28...53=7.28... 이므로 2, 3, 4, 5, 6, 7까지만으로 나누어보면 “53..
-
[알고리즘] C++로 구현한 이진 탐색 (Binary Search)알고리즘 2021. 8. 17. 15:49
이진 탐색 한번 반복할 때마다 탐색 범위를 반으로 줄여나가는 탐색 방법. 정렬된 데이터의 목록에만 사용이 가능하다. 탐색 과정 우선 어떤 방식으로 탐색이 진행되는지 알고리즘을 살펴보자. 아래의 배열에서 100을 찾아보겠다. 먼저 배열 중앙값인 50과 찾는 값인 100을 비교한다. 배열은 정렬되어 있고, 100은 50보다 크므로 50 이하의 값들은 탐색 대상에서 제외한다. 5번과 9번 배열의 중앙에 있는 7번 배열의 값인 80과 찾는 값인 100을 비교한다. 100은 80보다 크므로 80 이하의 값들은 제외한다. 8번과 9번 배열의 중앙에 있는 8번 배열의 값인 90과 찾는 값인 100을 비교한다. 100은 90보다 크므로 90 이하의 값들은 제외한다. 9번과 9번 배열의 중앙에 있는 9번 배열의 값인 1..