전체 글
-
모듈러 연산의 분배 법칙 (곱셈)알고리즘 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..
-
백준) 17087 - 숨바꼭질6 (C++)PS/BOJ 2023. 11. 19. 19:16
문제 링크 : https://www.acmicpc.net/problem/17087 문제 설명 SSS = 수빈이의 위치DDD = 보폭AnA_nAn = n번째 동생의 위치 DDD씩 이동해서 모든 동생의 위치에 도착할 수 있어야 한다. 문제 풀이D씩 이동해서 모든 위치를 방문할 수 있으려면 D는 이동할 거리들의 최대 공약수가 되어야 한다.이동할 거리가 D로 나눠져야 해당 위치로 정확히 이동할 수 있기 때문이다.예) gcd(8, 16, 6) = 2 두 거리의 최대 공약수를 구하고, 그렇게 구한 최대 공약수와 다음 거리의 최대 공약수를 구해가는 방식으로전체 거리의 최대 공약수를 구할 수 있다. 최대공약수를 구하는 알고리즘인 유클리드 호제법 사용.https://ko.wikipedia.org/wiki/유클리..
-
[C++] 문자열(string) 자르기C++ 2023. 6. 16. 03:08
1. string::substr()을 이용한 방법 string substr (size_t pos = 0, size_t len = npos) const; substr()은 문자 위치 pos에서 시작해서 len개의 문자까지 잘라서 리턴해준다. len에 값을 입력하지 않으면 문자열의 마지막까지 잘라서 리턴해준다. #include #include using namespace std; int main() { string str = "2023.06.16"; string year = str.substr(0, 4); string month = str.substr(5, 2); string day = str.substr(8); cout
-
C++ 반복자(iterator), vector와 list의 반복자 비교C++ 2021. 10. 18. 08:37
반복자(iterator) 어떤 컨테이너(자료구조)에 접근하든 동일한 방법으로 접근하기 위해서 제공되는 객체. 반복자는 원소의 위치를 갖고 있는 포인터와 비슷한 형태이다. 반복자를 이해하기 위해 먼저 벡터와 리스트의 접근 방식을 비교해보자. 벡터는 배열 기반으므로 연속된 메모리 공간을 가지고 있다. 그래서 인덱스 연산으로 임의 접근이 가능하고, 인덱스에 넣은 값을 증가시키는 방식으로 순회도 가능하다. 모든 컨테이너에 이런 간단한 방식으로 접근이 가능하다면 반복자는 필요하지 않을 것이다. 하지만 컨테이너들마다 접근 방식이 다르다. 그러면 리스트를 살펴보자. 하지만 리스트의 경우는 어떨까? 우선 연속된 메모리 공간을 가지지 않기 때문에 벡터처럼 인덱스 로 접근하는 것이 불가능하다. 즉 다른 방법으로 순회를 해..
-
[자료구조] 큐의 개념, 배열로 큐 구현하기(원형 큐)자료구조 2021. 9. 10. 15:15
큐(Queue) 큐는 먼저 들어간 데이터가 먼저 나가는 FIFO(First in, First Out)의 구조를 가지는 자료구조이다. 큐는 일상생활에서도 많이 볼 수 있다. 예를 들면 매표소, 은행 대기표, 식당 등 줄을 세우고 먼저 온 사람이 먼저 서비스를 받는 형태를 모두 큐라고 볼 수 있다. 실제로 큐를 구현하기에 앞서 어떤 연산과 변수들이 필요할지 생각해보자. 핵심이 되는 연산은 넣고(enqueue), 빼는(dequeue) 연산이다. 그리고 데이터가 들어오는 곳과 나가는 곳의 위치를 구분하기 위한 변수 front(앞쪽), rear(뒤쪽)가 필요하다. 배열로 큐 구현하기 우리가 실제로 줄을 서는 것 처럼 큐를 구현해보자. 제일 앞사람이 일을 마치고 빠져나가면, 뒤에 사람들은 한칸씩 앞으로 이동하는 방..