-
[개념] 유클리드 호제법을 통한 최대공약수 + 최소공배수알고리즘 2023. 11. 2. 11:01
유클리드 호제법이란?
최대공약수를 구하는데 가장 흔하게 사용되는 알고리즘으로써 chatGPT나 구글링을 좀 해봤는데 거의 대부분 이 방법을 사용하고 있음
말로써 설명하자면 비교대상인 두 수 중 큰수(a)와 작은수 (b)가 있을 떄 a를 b로 나눈 수를 또 b로 나누고 반복하다가 나머지가 0이 되었을 때 그떄의 a 값이 최대공약수라는 내용임
사용방법
흔히 재귀함수를 통해서 사용하는 방법과 while반복문을 사용하는 방법 2가지가 있음
시간복잡도 상 크게 다르지 않음
O(log(min(a,b)))을 가지기에 필자는 좀더 짧고 이해하기 쉬운 재귀함수를 추천
1. 재귀함수
const gcd = (a, b) => { if (b === 0) return a; return gcd(b, a % b); }
2. while반복문
const gcd = (a, b) => { while (b) { let t = a a = b b = t % b } return a }
Tip) 이를 통한 최소공배수를 구하기!
const lcm = (a, b) => { return (a * b) / gcd(a, b) }
'알고리즘' 카테고리의 다른 글
[개념] BigO 표기법 (1) 2023.11.06 [개념] 검색알고리즘 (선형 VS 이진) (1) 2023.11.04 [프로그래머스 알고리즘] 2중반복문 (0) 2023.06.22 [프로그래머스 알고리즘] while과 reduce의 합작 (0) 2023.06.21 [프로그래머스 알고리즘] 1~N까지 배열만들기, 제곱근의 갯수와 약수의 관계 (0) 2023.06.21