라떼는말이야

밑의 사진을 클릭하면 문제 링크로 이동합니다 문제 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번에 K개의 물병을 옮길 수 있다. 하지만, 지민이는 물을 낭비하기는 싫고, 이동을 한 번보다 많이 하기는 싫다. 따라서, 지민이는 물병의 물을 적절히 재분배해서, K개를 넘지 않는 비어있지 않은 물병을 만들려고 한다. 물은 다음과 같이 재분배 한다. 먼저 같은 양의 물이 들어있는 물병 두 개를 고른다. 그 다음에 한 개의 물병에 다른 한 쪽에 있는 물을 모두 붓는다. 이 방법을 필요한 만큼 계속 한다. 이런 제약 때문에, N개로 K개를 넘지않는 비어있지 않은 물병을..

문제 nCm을 출력한다. 입력 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) 출력 nCm을 출력한다. 예제 나의 풀이 문제에서 조합을 설명해주지 않아서 조합 구하는 식에 대해 찾아봤다 (까묵...) 나는 위 식을 살짝 변형해 사용했다. n, m = map(int, input().split()) ja, mo = 1, 1 for i in range(1, m): ja *= (n-i) mo *= i ja *= n mo *= m print(ja//mo) 분자, 분모 각각 반복문을 돌릴 수도 있었지만 범위가 거의 유사했기 때문에 한 번의 반복만 하기 위해서 분자에서는 n을 제외한 (n-1)(n-1) ... (n-(r-1)) 까지 계산했고, 분모에서는 r을 제외한 1*2*...*(..

유클리드 알고리즘 (Euclidean algorithm) 두 정수 사이의 최대공약수(GCD, Greatest Common Divisor)를 구하는 알고리즘이다. 유클리드 알고리즘의 동작 두 정수 a, b가 있을 때 r은 a ÷ b의 나머지로 정의한다. 즉, r = a % b이다. (a > b로 가정) 위 프로세스와 같이 나머지가 0이 될 때까지 두 번째 인자 값을 첫 번째 인자 값에 넣고, 나머지를 두 번째 인자 값에 넣는다. 예시 Q1. 2740과 1760의 최대공약수 계산 2740과 1760의 최대 공약수는 20이다. Q2. 25와 60의 최대공약수 계산 25와 60의 최대공약수는 5이다. 위 예제에서는 r1과 r2 중 어느 쪽이 커도 상관 없다는 것을 보여준다. 구현 gcd = lambda a, b..

0. RSA의 키 생성 알고리즘 RSA의 키 생성 알고리즘은 다음과 같다. 자세한 건 이전 글을 참고 바란다. 2020/06/18 - [알고리즘/RSA] - [RSA] 소개 & 키 생성 알고리즘 서로 다른 큰 소수 p, q를 선택한다. (p ≠ q) N = p x q를 계산한다. φ(N) = (p - 1) x (q - 1)을 계산한다. φ(N) 보다 작고, φ(n)와 서로소인 자연수 e를 선택한다. (gcd(e, φ(N))=1, 1 < e < φ(N)인 e 선택) d x e를 φ(N)로 나누었을 때 나머지가 1인 정수 d를 구한다. ( de ≡ 1 mod φ(N) ) , 유클리드 호제법 이용 KU = {e, N}, KR = {d, N}이 된다. 위 알고리즘에서 해결해야 할 문제들이 있다. 1. 큰 소수 ..