확장 유클리드 호제법
이전에 유클리드 호제법에 대해 알아본 적이 있었습니다. 유클리드 호제법과 확장 유클리드 호제법 모두 정수론을 이용한 알고리즘인데요, 유클리드 호제법이 a와 b의 최대 공약수 gcd(a, b)를 구하는 알고리즘이었다면, 확장 유클리드 호제법은 더 나아가 a와 b의 최대 공약수 gcd(a, b)와 ax+by = gcd(a, b)를 만족하는 x, y까지 구하는 알고리즘 입니다. 그럼 확장 유클리드 호제법을 어떻게 사용하는지 알아보겠습니다. 확장 유클리드 호제법을 사용하기 위해 간단한 규칙을 먼저 살펴봐야 합니다. 아래 규칙을 통해서 Ri가 0이 될 때까지 반복했을 때 마지막으로 나온 Xi, Yi가 gcd(a, b)를 만족하는 x, y가 됩니다. 초기 설정해줘야 하는 값은 X0 = 1, X1 = 0, Y0 = ..
2021. 3. 25.
단축키
내 블로그
| 내 블로그 - 관리자 홈 전환 |
Q
Q
|
| 새 글 쓰기 |
W
W
|
블로그 게시글
| 글 수정 (권한 있는 경우) |
E
E
|
| 댓글 영역으로 이동 |
C
C
|
모든 영역
| 이 페이지의 URL 복사 |
S
S
|
| 맨 위로 이동 |
T
T
|
| 티스토리 홈 이동 |
H
H
|
| 단축키 안내 |
Shift + /
⇧ + /
|
* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.
