-
2/9기록 - 백준 1934Algorithm 2022. 2. 9. 10:17728x90
오늘은 교육이 있어서 아침에 급하게 문제를 하나 풀어보기 위해서 그래도 익숙한 문제를 하나 선정했다.
오늘의 문제는 최소공배수 문제이다. 최소공배수는 해당 두개의 값을 곱하고 최대공약수로 나누어 주면 간단히 해결할 수 있다. 하지만 최대공약수를 구할 때 알고리즘을 생각하지 않으면 굉장히 험난한 길을 갈 수도 있다.
중딩때 경시대회 준비를 하면서 배웠던 유클리드 호제법을 아직도 최대공약수 구할 때 익숙하게 사용했었는데, 유클리드 호제법을 사용하면 최대공약수를 컴퓨터 언어로도 굉장히 쉽게 풀어낼 수 있다.
출처 : 위키백과
위키 백과에 유클리드 호제법을 잘 설명해 두어서 가져와 보았다. a와 b의 최대공약수를 (a,b)라 하면 (a,b) = (b,r) 로 표현하여 r 나머지가 0이 될 때까지 계속 나누어 준다. r이 0이 되는 순가 b 자리에 있는 값이 최대공약수가 된다.
알고리즘 생각
1. 값을 입력받기
2. 유클리드 호제법을 사용하여 최대공약수를 구하는 함수 만들기
3. 최소공배수 = (a*b)/a,b의 최대공약수
4. StringBuilder를 사용하여 반복문의 최소공배수값을 모두 append
5. 출력
최대공약수를 구하는 함수 GCD를 나누는 값 b가 0이 아닐 때 계속 GCD(b,r)로 해주기 위해서 재귀함수 형식으로 표현했고 b가 0이 되면 더이상 나눌 수 없으므로 a를 반환
이렇게 쉽게 최소공배수를 구해낼 수 있었다.
2/9 기록 끝!!!!!!!!
728x90'Algorithm' 카테고리의 다른 글
2/11기록 - 백준 2581 (1) 2022.02.11 2/10 기록 - 프로그래머스 2020 Kakao 인턴쉽 level3 보석쇼핑 (0) 2022.02.10 2/7기록 - 백준 2941 (0) 2022.02.07 2/6기록 - 백준 7568 (0) 2022.02.06 2/4기록 - 프로그래머스 두 개 뽑아서 더하기 (0) 2022.02.04