배열에서 최소공배수를 구하는 프로그래머스 레벨2 문제
최대공약수를 구하는 알고리즘
의사코드
1. 최대공약수를 구하려는 두 값의 최소값을 구한다.
2. 두 값의 나머지가 0을 만족하는 1~최소값을 찾는다.
3. 만족하는 값이 최소값.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
int GCDFunc(int a, int b)
{
//a,b 중 작은 값을 찾아냄
//int iMin = (a < b) ? a : b;
iRange = min(a, b); // 1 ~ iRange 범위 값을 검사
for (int i = 1; i <= iRange; i++)
{
if (a % i == 0 && b % i == 0)
{
//값이 나오면 저장한 후 함수 종료 시 리턴
iMax_Div = i;
}
}
return iMax_Div;
}
|
수정 알고리즘
|
1
2
3
4
5
6
7
8
9
10
11
12
|
int GCDFunc(int a, int b)
{
//최대 공약수를 구하는 함수
//두 값을 동시에 나누는 값중 가장 큰 수
while (b != 0)
{
int r = a%b;
a = b;
b = r;
}
return a;
}
|
최소공약수를 구하는 알고리즘
|
1
2
3
4
5
6
7
|
int LCMFunc(int a, int b)
{
return a * b / GCDFunc(a, b);
}
|
프로그래머스 레벨2 테스트 솔루션
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
class CSolutuon
{
public:
explicit CSolutuon() {};
explicit CSolutuon(vector<int> vec)
: vecQ(vec) {}
int Solution()
{
iAnswer = vecQ.front();
for (int i = 1; i < vecQ.size(); ++i)
{
iAnswer = LCMFunc(iAnswer, vecQ[i]);
}
cout << iAnswer << endl;
return iAnswer;
}
int GCDFunc(int a, int b)
{
while (b != 0)
{
int r = a%b;
a = b;
b = r;
}
return a;
}
int LCMFunc(int a, int b)
{
return a * b / GCDFunc(a, b);
}
private:
int iAnswer = 0;
vector<int> vecQ;
};
int main()
{
vector<int> vec = {2,4,6,8,14};
CSolutuon C(vec);
C.Solution();
system("pause");
return 0;
}
|
프로그래머스 레벨 2 테스트(배열 내의 모든 값들의 최소공배수를 구하라)
의사코드
1. 최대공약수를 구하는 함수 제작
2. 최소공배수를 구하는 함수 제작
3. 현재 배열과 다음 배열의 최소공배수를 구한다.
4. 구해진 값으로 다음 배열의 값과 최소공배수를 구하며 배열의 끝까지 순회한다.
5. 배열의 끝까지 탐색이 완료되면 배열 내의 모든 값들의 최소공배수가 구해진다.
'코딩테스트 연습' 카테고리의 다른 글
| 코딩테스트 - 모의고사 (0) | 2020.01.03 |
|---|---|
| 코딩테스트 - 완주하지 못한 선수 (0) | 2020.01.03 |
| 코딩테스트 - 행렬의 곱셈 (0) | 2020.01.03 |
| 코딩테스트 - 전파탑 문제 (0) | 2020.01.02 |
| 코딩테스트 - string 문자열 비교 (0) | 2020.01.02 |