목록정수론 (1)

tempcru 삽질기록

유클리드 호제법 (Euclidean algorithm)

유클리드 호제법이란? - 유클리드가 집필한 '유클리드 원론'에 나오는 최대공약수를 찾는 기법이다. - 호제법 의미, 互(서로호), 除 (덜 제)를 사용한 단어로 두 숫자를 상호 나누거나 빼서 "최대공약수"를 찾는다. 1. 호제법의 이해 (1) 호제법을 어떤 function 이나 Method 라고 생각해본다 input : 임의의 숫자 2개 (각 a, b 라고 가정) output : 두수의 최대공약수 숫자 1개 (x 라고 가정) // 코드로 표현하면 이런식 public int gcd(int a, int b) { return 최대공약수; } (2) input, output을 어떻게 정의해야할지 고민해본다 (3) input a, b는 자연수가 입력되어야한다. input a, b는 int로 정의했다. (숫자기만 ..
Algorithm/이산수학 2022. 1. 21. 00:41
이전 Prev 1 Next 다음