26091 백준 2609번 최대공약수와 최소공배수(코틀린) 두 수를 나눌 수 있는 수 중 가장 큰 수를 최대공약수라고 한다. 18과 12의 최대공약수는 6이 된다. 두 수 모두의 배수중 가장 작은 수를 최소공배수라고 한다. 9와 12의 최소공배수는 36이다. https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 이 문제는 최대공약수와 최소공배수를 구하는 문제이다. 최대공약수는 두 수중 가장 작은 값부터 1까지 천천히 반복문을 돌아서 찾는 방법과 유클리드 호제법을 이용해서 찾는 방법 2가지가 있다. 첫번째 방법은 평균적으로 n/2, 최악의 경우 n번 수행하여 시간복잡도 O(n.. 2023. 1. 14. 이전 1 다음