문제 https://www.acmicpc.net/problem/14476 14476번: 최대공약수 하나 빼기 첫째 줄에 정수의 개수 N (4 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 N개의 수가 주어진다. 각각의 수는 20억을 넘지 않는 자연수이다. www.acmicpc.net 설명 N개의 정수 중에서 임의의 수 K를 뺐을 때, 나머지 N-1개의 최대공약수가 가장 커지게 해야 한다. 모든 경우의 수를 하나하나 따지면 수행시간이 O(\(N^{2}\)) 이지만 누적합을 사용하면 O(N) 으로 해결할 수 있다. LtoR 배열에는 배열 좌측에서부터 하나씩 누적해서 구한 최대공약수를 저장한다. RtoL 배열에는 배열 우측에서부터 하나씩 누적해서 구한 최대공약수를 저장한다. 최대공약수를..
문제 https://www.acmicpc.net/problem/1735 1735번: 분수 합 첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. www.acmicpc.net 설명 두 분수가 주어졌을 때, 그 합을 기약분수의 형태로 구해야 한다. \( \dfrac{A}{B} + \dfrac{C}{D} = \dfrac{A \times D + B \times C}{B \times D} \) 분수의 합을 계산하는 방법은 다음과 같다. 여기서 기약분수로 만들어야 하므로 최종 결과에서 분자와 분모의 최대공약수를 구하고 분자와 분모를 각각 구한 값으로 나눠주면 된다. int temp1 = A * D + B * C; int te..
유클리드 호제법 두 개의 자연수가 주어졌을 때, 두 수의 최대공약수를 구하는 알고리즘의 하나이다. 두 자연수 a, b (a > b) 에 대해서 a를 b로 나눈 나머지를 r이라 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수가 된다. gcd(a, b) = gcd(b, r) gcd(a, b, c) = gcd(gcd(a, b), c) a = 36, b = 28 36 % 28 = 8 gcd(36, 28) = gcd(28, 8) 28 % 8 = 4 gcd(28, 8) = gcd(8, 4) 8 % 4 = 0 gcd(8, 4) = gcd(4, 0) 따라서, 36과 28의 최대공약수는 4가 된다. ..
