알고리즘 - 최대 공약수 / 최대 공배수

dongha1992·2020년 10월 28일
0

알고리즘

목록 보기
10/42

문제

내 생각

두 인자가 지워지면 최대공약수, 최대공배수를 포함한 배열을 리턴한다.

약수란 어떤 수를 나누었을 때 떨어지는 수다. 1과 자기 자신 밖에 존재하지 않으면 소수

최대 공약수 구하기

두 수의 max,min을 정하고 나머지를 구한다. 이제 다음 턴에 min값이 max가 되고 나머지를 또 구한다. min이 0일 때 max값이 최대 공약수다!

재귀로 푸는 방법인데 b의 인자로 a와 b를 나눈 나머지가 인자로 들어간다. 식으로 나타내면

LCM = GCD * (a / GCD) * ( b / GCD)

최소 공배수 구하기

최소 공배수(LCM)는 최대 공약수(GCD)에 입력값들의 서로소를 곱해주면 된다.

으렵다..

내 풀이

뇌 정지.. 최대 공약수 / 최소 공배수 문제는 언제나 어렵다...

최대 공약수 구하기

최소 공배수는 그냥 외워야겠다...

최중 풀이.. 배열에 담아야 하는데 저렇게 담았다. 어떻게 하면 이쁘게 담지?

return 배열 형태로 바로 담으면 된다.

다른 사람 풀이

profile
글과 코드와 사람에 관해 생각합니다.

관심 있을 만한 포스트

0개의 댓글