728x90
반응형
서론
본 포스팅 시리즈는 필자가 Baekjoon 문제를 풀면서 정리한 코드나 이론을 올리는 포스팅이다.
대부분의 설명은 코드의 주석으로 기재되어있으니 참고바란다.
문제
Baekjoon 1934번 - 최소공배수
https://www.acmicpc.net/problem/1934
1934번: 최소공배수
두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있
www.acmicpc.net
해법
이번 문제는 주어진 A, B에 대하여 두 수의 최소공배수를 구하는 문제다. 이번 문제는 "유클리드 호제법"을 이용하면 쉽게 해결할 수 있다. 우선 유클리드 호제법을 이용해 두 수의 최대공약수를 구한 뒤, "(두 수의 곱) / (두 수의 최대공약수)"를 통해 최소공배수를 구할 수 있다.
풀이
참고자료
위키피디아 - 유클리드 호제법:
https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95
유클리드 호제법 - 위키백과, 우리 모두의 백과사전
유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를
ko.wikipedia.org
728x90
반응형
'SW > Baekjoon' 카테고리의 다른 글
| [Baekjoon 문제풀이] 1018 - 체스판 다시 칠하기 (Python 3) (0) | 2022.03.04 |
|---|---|
| [Baekjoon 문제풀이] 1463 - 1로 만들기 (Python 3) (0) | 2022.01.10 |
| [Baekjoon 문제풀이] 4948 - 베르트랑 공준 (Python 3) (0) | 2022.01.06 |
| [Baekjoon 문제풀이] 1011 - Fly me to the Alpha Centauri (Python 3) (0) | 2022.01.06 |
| [Baekjoon 문제풀이] 11653 - 소인수분해 (Python 3) (0) | 2022.01.04 |