https://www.acmicpc.net/problem/11688 11688번: 최소공배수 찾기 세 정수 a, b, L이 주어졌을 때, LCM(a, b, c) = L을 만족하는 가장 작은 c를 찾는 프로그램을 작성하시오. LCM(a, b, c)는 a, b, c의 최소공배수이다. www.acmicpc.net 문제 설명 세 정수 a, b, L이 주어졌을 때, LCM(a, b, c) = L을 만족하는 가장 작은 c를 찾는 프로그램을 작성하시오. LCM(a, b, c)는 a, b, c의 최소공배수이다. 풀이 과정 나의 풀이 ① 문제 바라보기 LCM(a,b,c) = L 의 과정에서 a,b,L이 주어졌고, 가장 작은 c를 구하는 것이 문제에서 요구하는 것이다. 기본적으로 최소공배수는 유클리드 호제법을 통해 구할 ..
Algorithm/수학
https://www.acmicpc.net/problem/2824 2824번: 최대공약수 첫째 줄에 N이 주어진다.(1 ≤ N ≤ 1000) 둘째 줄에는 N개의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, N개의 수를 곱하면 A가 된다. 셋째 줄에 M이 주어진다.(1 ≤ M ≤ 1 www.acmicpc.net 문제 설명 상근이는 학생들에게 두 양의 정수 A와 B의 최대공약수를 계산하는 문제를 내주었다. 그런데, 상근이는 학생들을 골탕먹이기 위해 매우 큰 A와 B를 주었다. 상근이는 N개의 수와 M개의 수를 주었고, N개의 수를 모두 곱하면 A, M개의 수를 모두 곱하면 B가 된다. 이 수가 주어졌을 때, 최대공약수를 구하는 프로그램을 작성하시오. 풀이 과정 나의 ..
https://www.acmicpc.net/problem/1850 1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net 문제 설명 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A가 111이고, B가 111111인 경우에는 최대공약수가 111이다. 풀이 과정 나의 풀이 ① 최대공약수 구하는 법 유클리드 호제법을 통해 최대공약수를 ..
https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 문제 설명 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오. 풀이 과정 나의 풀이 ① 최대공약수 구하는 법 유클리드 호제법을 통해 최대공약수를 쉽게 구할 수 있다. 유클리드 호제법이란 기원전 300년 전에 나온 가장 오래된 알고리즘으로 유명하다. 유클리드 호제법으로 최대공약수를 구하는 방법은 다음과 같다. ○ 두 자연수 a,b에 대하여 a를 b로 나눈 나머지 r에 대해 a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이를..
https://www.acmicpc.net/problem/9613 9613번: GCD 합 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진 www.acmicpc.net 문제 설명 양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오. 풀이 과정 나의 풀이 ① 최대공약수 구하는 법 유클리드 호제법을 통해 최대공약수를 쉽게 구할 수 있다. 유클리드 호제법이란 기원전 300년 전에 나온 가장 오래된 알고리즘으로 유명하다. 유클리드 호제법으로 최대공약수를 구하는 방법은 다음과 같다. ○ 두 자연수 a,b에 ..
https://www.acmicpc.net/problem/13241 13241번: 최소공배수 정수 B에 0보다 큰 정수인 N을 곱해 정수 A를 만들 수 있다면, A는 B의 배수이다. 예: 10은 5의 배수이다 (5*2 = 10) 10은 10의 배수이다(10*1 = 10) 6은 1의 배수이다(1*6 = 6) 20은 1, 2, 4,5,10,20의 배수이다. 다 www.acmicpc.net 문제 설명 정수 B에 0보다 큰 정수인 N을 곱해 정수 A를 만들 수 있다면, A는 B의 배수이다. 예: 10은 5의 배수이다 (5*2 = 10) 10은 10의 배수이다(10*1 = 10) 6은 1의 배수이다(1*6 = 6) 20은 1, 2, 4,5,10,20의 배수이다. 다른 예: 2와 5의 최소공배수는 10이고, 그 이..
https://www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net 문제 설명 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다. 두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오. 풀이 과정 나의 풀이 ① 최대공약수..
https://www.acmicpc.net/problem/2702 2702번: 초6 수학 첫째 줄에 테스트 케이스의 개수 T(1
https://www.acmicpc.net/problem/1193 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 풀이 과정 풀이 과정 나의 풀이 이게 나만의 팁인지 아닌지는 모르겠지만.. 알고리즘 문제 중에서 분류가 '수학'인 문제를 풀 때는 '규칙' 찾기에 집념해야하는 것 같다. 물론 뭐... 규칙 없는 알고리즘이 어딨냐고 하면 또 할 말이 없지만.. 수학 문제는 좀 더 중요하다는 말이다 쨋든..!! 그래서 이 문제의 규칙을 내가 어떻게 찾았는지 한번 알아보자. 문제에서 분수의 배열은 표에서 지그재그식으로 움직이며 배열됨을 알 수 있다. 간단하게 써보면 다음과 같다. ● 분수의 배열 첫번째 줄 : 1/1 두번째 줄 : 1/2 2/1 세번..
https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 문제 설명 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행사가 되어 새로운 세계에 발을 내려 놓는 영광의 순간을 기다리고 있다. 그가 탑승하게 될 우주선은 Alpha Centauri라는 새로운 인류의 보금..
