# Euclidean algorithm
확장된 유클리디언 알고리즘(Extended Euclidean Algorithm)
우선 설명하기에 앞서 2가지 개념을 먼저 이해하고 가자. 유클리드 호제법(Euclidean Algorithm)과 베주 항등식(Bezout's Identity) ! 유클리드 호제법(Euclidean Algorithm) 우선 정수론에 나오는 내용이므로 여기서 나올 변수는 모두 정수라고 보면 된다. 두 정수 a, b가 있을 때 이들의 최대공약수는 gcd(a, b)로 표현한다. a >= b일 때 a를 b로 나눈 나머지를 r이라고 하자. (0 a ≡ r (mod b) 그럼 gcd(a, b) = gcd(b, r)을 만족한다. >gcd(a, b) = gcd(b, r)
[C++] 2981: 검문
문제 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다. 먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다. N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오. 입력 첫째 줄에 종이에 적은 수의 개수 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄부터 N개 줄에는 종이에 적은 수가 하나씩 주어진다. 이 수는 모두 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. 같은 수가 두 번 이상 주어지지 않는다. 항상 M이 하나 이상 존재하는 경우만 입력으로 주어진다. 출력 첫째 줄에 가능한 M을 공백으로 구분하여 모두
최대 공약수와 최소 공배수 구하기
알고리즘 문제를 풀다가 javascript로 최대 공약수와 최소 공배수를 구할 일이 종종 생길 것 같아서 정리할 필요를 느꼈다. 일단 간단하게 설명부터 하고 넘어가겠다. 최대 공약수: 두 수 A와 B의 공통된 약수 중에 가장 큰 정수이다. 최소 공배수: 두 수, 혹은 그 이상의 여러 수의 공통인 배수 중 가장 작은 수이다. 두 가지 모두 주어진 수에서 1을 증가하거나 감소시켜서 찾을 수 있지만, 알고리즘 문제에서는 해당 접근 방식으로는 시간 복잡도 제한을 해결할 수가 없다. 따라서 유클리드 호제법을 이용한 최대 공약수와 최소 공배수를 구해 볼 것이다. 유클리드 호제법 유클리드 호제법은 두개의 자연수의 최대 공약수를 구하는 알고리즘이다. 정리를 해보면 다음과 같다. 두 수 A, B가 주어질 때, A와 B의 최대 공약수를 gcd(A, B)라고 하면 다음이 성립된다. > gcd(A, B) = gcd(B, r) 이 때, `r
[알고리즘] 유클리드 호제법(Euclidean algorithm)
유클리드 호제법이란? 두 수의 최대공약수(GCD)를 구하는 알고리즘으로, 유클리드에 의해 기원전 300년경에 발견된 가장 오래된 알고리즘이다. 호제법(互除法)이라는 말은 서로(互) 나누기(除) 때문에 붙여진 이름이다. 유클리드 호제법 동작 과정 유클리드 호제법에는 모듈러 연산(나머지 연산)이 사용된다. 큰 수를 작은 수로 나눈 나머지를 구한다. 나눴던 수와 그 나머지로 또 모듈러 연산을 한다. 위의 과정을 반복하다가 나머지가 0이 되었을 때, 마지막 연산에서 나누는 수로 사용된 수가 최대공약수(GCD)이다. cf) 이 알고리즘의 포인트는 두 수가 모두 GCD의 배수라는 점이다. 그렇기 때문에 나머지 연산의 반복으로 GCD를 구할 수 있다. 💡유클리드 호제법 활용 문제 프로그래머스 N개의 최소공배수
모듈러 역원
관용 암호화 또는 공개키 암호화 등에서 곱셈에 대한 모듈러 역원을 필요로하는 경우가 더러 있습니다. 이는 유클리드 알고리즘을 통해 조금 더 쉽게 구할 수 있습니다. 유클리드 알고리즘 > $gcd(a,b)=gcd(b,r)$ $r=a\space mod\space b$ $q:$몫, $r:r1$을 $r2$로 나눈 나머지 ($r=r1-q*r2)$ 확장 유클리드 알고리즘 > $s\times a + t\times b =gcd(a,b)$ 
[Cryptography] RSA
RSA 가장 널리 쓰는 공개 키 알고리즘 중 하나로 전자서명이 가능한 최초의 공개 키 알고리즘으로 알려져 있다. 개념 >- Public Key : e, n ⤷ Plain Text의 크기는 n을 넘을 수 없으며 n은 1024 bits 이상의 수 이다 * Private Key* : d $C = P^e mod n$ $P = C^d mod n$ 생성 알고리즘 > 1. 512비트 이상의 큰 소수 p, q를 선택 ⤷ p ≠ q n = p × q ⤷ n은 1024비트 이상의 수가 된다 * φ⒩ = ( p - 1) × ( q - 1 ) * * φ⒩ 와 서로소인 e를 선택 ⇒ _ 1 < e < φ⒩ _ * Public Key : e, n **Private Key : d = `e⁻¹ mod φ
백준 2487번: 섞기 순열
섞기 순열 백준 2487번: 섞기 순열 아이디어 사이클 크기 모두 찾고 그 크기간의 최소공배수를 구하면 정답. 코드 여담 > 최소공배수를 구하기 위해 곱하는 과정에서 int 범위를 초과할 수 있다.
백준 2168번: 타일 위의 대각선
타일 위의 대각선 백준 2168번: 타일 위의 대각선 아이디어 대각선은 가로, 세로 모든 타일에 각 한 번씩 대응되고, 가로, 세로 길이의 최대공약수만큼 겹친다. 가로, 세로 길이가 서로소일 때 가로+세로-1이니까 gcd 단위로 쪼개고 이렇게 계산해도 됨. 근데 똑같음. 코드 여담 > 수학이 싫어
백준 2981번: 검문
검문 백준 2981번: 검문 아이디어 N1 % M = k N2 % M = k N3 % M = k N4 % M = k ... N2 % M - N1 % M = 0 (N2 - N1) % M = 0 따라서 각 숫자의 차를 구하고, 그 차의 최대공약수를 구한 후, 구한 최대공약수의 약수를 전부 출력하면 된다! 또, gcd(a, b) = gcd(a+b, b) 이므로, 크기순으로 정렬한 후 인접 숫자간의 차이만 구해도 된다. 약수 구할 때 O(N)이 아니라 O(√N)으로 구해야함. 코드 여담 > 2년 전에 중도에서 열심히 풀다 포기한 문제. 아니 진짜 정수론 개어렵다. 공부 열심히 해야겠다.
🐡 TIL 0208
⬇️ Main Note https://docs.google.com/document/d/1Ce2r1obYEdFcmE1S8LLDWiZJbWWA0V6iE_wj4J9802k/edit 🔍[Search] Mostly backend computer takes a big role in searching. Once the frontend computer requsts for searching a word, the backend copmuter responses with the wanted word. then frontend receives it and displays to the screen. 🔧 Types of Database Full Table Scan : This database scans the whole thing. ex) When the user is using searching method to look up for the pos
[Java] 백준 / 공약수 / 2436번
[Java] 백준 / 공약수 / 2436번 > 문제 > 공약수 문제 링크 어떤 두 자연수에 공통인 약수들 중에서 가장 큰 수를 최대공약수라고 하고, 두 자연수의 공통인 배수들 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 두 자연수 12와 90의 최대공약수는 6이며, 최소공배수는 180이다. 이와 반대로 두 개의 자연수 A, B가 주어졌을 때, A를 최대공약수로, B를 최소공배수로 하는 두 개의 자연수를 구할 수 있다. 그러나, 이러한 두 개의 자연수 쌍은 여러 개 있을 수 있으며, 또한 없을 수도 있다. 예를 들어, 최대공약수가 6이며 최소공배수가 180인 두 정수는 위의 예에서와 같이 12와 90일 수도 있으며, 30과 36, 18과 60, 혹은 6과 180일 수도 있다. 그러나, 최대공약수가 6이며 최소공배수가 20인 두 자연수는 있을 수 없다. 두 개의 자연수가
GCD의 고찰 (최대공약수)
1.최대공약수 개념 2.코드 표현법 유클리드 호제법: Euclidean algorithm 알고리즘의 피타고라스의 정리 아닐까 싶을정도로 이건 알고 넘어가자 일단 코드 부터 보면서 해보자 두수가 입력이 되면 나머지가 0이 된다면 n
Recursion - 재귀함수(호출)
1. Recursion - 재귀함수 재귀함수란 자기 자신을 호출하는 함수다. 재귀함수는 반복문(loop)과 스택(stack) 구조가 결합된 함수라고 할 수 있다. 재귀함수를 사용할 때 장점으로는 반복문을 중첩해서 코드를 쓸 때보다 코드가 한층 간결해진다는 점이다. 하지만, 재귀함수는 일반적으로 이해하는데 상대적으로 높은 정신력을 써야 하므로 유지보수가 어려워질 수 있다. 또한, 재호출된 함수가 쌓임으로써(이는 스택 형태로 쌓여있다) 메모리를 더 사용한다고 한다. 재귀함수를 모르는 것보다 이해하고 있으면 당연히 좋다. 재귀함수를 이해하려고 노력하면서 코딩 스킬의 하나로서 익숙해져 있으면 좋을 것이다. 바로 코드를 통해 알아본다. 2. sum(num) 먼저 for문을 활용해 수들을 반복적으로 합해주는 코드를 짜본다. 위와 동일한 결과값을 반환하지만 이번엔 재귀함수를 활용해본다. 3. GCD, LCM - 최대공약수, 최소공배수 다음은 최대공약수와 최소공배수
[3주 - 5일차] 학습 정리
Control + i sort code indent String.replacingOccurrences String.trimmingCharacters(in: ["!"]) 조건에 부합하는 끝을 잘라준다 pie M_PI Array Array.capacity - 메모리 관련 > 배열에 요소를 추가할 때, 해당 배열이 예약된 용량을 초과하기 시작하면 배열은 더 큰 메모리 영역을 할당하고, 요소를 방금 할당한 새 메모리에 복사합니다. 이때 새로운 저장소는 이전 저장소 크기의 2배입니다. reference GCD(최대공약수) - 유클리드 호제법(Euclidean algorithm)