Programers : N개의 최소공배수 (GCD / LCM)
11586 단어 level2PROGRAMERSPROGRAMERS
N개의 최소공배수
코드
[ 나의 풀이 ]
#include <string>
#include <vector>
#include <map>
#include <cmath>
using namespace std;
int solution(vector<int> arr) {
int answer = 1;
map<int,int> m;
/* 각 숫자들이 어떤 수의 곱으로 이루어져 있는지 검사 */
for(int i=0;i<arr.size();i++)
{
map <int,int> temp;
int n = arr[i];
int j=2;
while(n != 1)
{
if(n % j == 0){
temp[j]++;
n = n/j;
}else{
j++;
}
}
/* 약수의 차수만 필요하므로 기존 map 값과 비교! */
for(auto it = temp.begin();it != temp.end();it++)
{
int idx = it->first;
int value = it->second;
m[idx] = max(m[idx], value);
}
}
/* 약수의 최대 차수의 곱들로 정답을 산출 */
for(auto it = m.begin();it != m.end();it++){
answer *= pow(it->first,it->second);
}
return answer;
}
- 모든 수를 대상으로 최소 공배수를 구하려면 각 약수들의 최대 차수들의 곱이 필요하다고 생각했음
- 그래서 모든 수의 약수를 구했고, 최대 값들만 map에 저장하여 계산했음
- 밑에 풀이가 더 간단하고 똑똑한 풀이!
[ 최적 코드 ]
#include <string>
#include <vector>
using namespace std;
/* 최대 공약수 */
int GCD(int a, int b){
if(a == 0) return b;
return GCD(b%a,a);
}
/* 최소 공배수 */
int LCM(int a, int b){
return a*b / GCD(a,b);
}
int solution(vector<int> arr) {
int answer = 0;
answer = arr[0];
for(int i=1;i<arr.size();i++){
answer = LCM(answer, arr[i]);
}
return answer;
}
- key point!
: 앞에 2개씩 차례차례 최소 공배수를 구하면 결국 모든 수의 최소공배수를 구할 수 있음
- 최대공약수를 구하는 GCD와 최소공배수를 구하는 LCM을 만드는 함수는 외워두자!
- 이것은
유클리드 호제법
을 재귀
로 구현한 것이다
Author And Source
이 문제에 관하여(Programers : N개의 최소공배수 (GCD / LCM)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@neity16/Programers-N개의-최소공배수
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
[ 나의 풀이 ]
#include <string> #include <vector> #include <map> #include <cmath> using namespace std; int solution(vector<int> arr) { int answer = 1; map<int,int> m; /* 각 숫자들이 어떤 수의 곱으로 이루어져 있는지 검사 */ for(int i=0;i<arr.size();i++) { map <int,int> temp; int n = arr[i]; int j=2; while(n != 1) { if(n % j == 0){ temp[j]++; n = n/j; }else{ j++; } } /* 약수의 차수만 필요하므로 기존 map 값과 비교! */ for(auto it = temp.begin();it != temp.end();it++) { int idx = it->first; int value = it->second; m[idx] = max(m[idx], value); } } /* 약수의 최대 차수의 곱들로 정답을 산출 */ for(auto it = m.begin();it != m.end();it++){ answer *= pow(it->first,it->second); } return answer; }
- 모든 수를 대상으로 최소 공배수를 구하려면 각 약수들의 최대 차수들의 곱이 필요하다고 생각했음
- 그래서 모든 수의 약수를 구했고, 최대 값들만 map에 저장하여 계산했음
- 밑에 풀이가 더 간단하고 똑똑한 풀이!
[ 최적 코드 ]
#include <string> #include <vector> using namespace std; /* 최대 공약수 */ int GCD(int a, int b){ if(a == 0) return b; return GCD(b%a,a); } /* 최소 공배수 */ int LCM(int a, int b){ return a*b / GCD(a,b); } int solution(vector<int> arr) { int answer = 0; answer = arr[0]; for(int i=1;i<arr.size();i++){ answer = LCM(answer, arr[i]); } return answer; }
- key point!
: 앞에 2개씩 차례차례 최소 공배수를 구하면 결국 모든 수의 최소공배수를 구할 수 있음- 최대공약수를 구하는 GCD와 최소공배수를 구하는 LCM을 만드는 함수는 외워두자!
- 이것은
유클리드 호제법
을재귀
로 구현한 것이다
Author And Source
이 문제에 관하여(Programers : N개의 최소공배수 (GCD / LCM)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@neity16/Programers-N개의-최소공배수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)