GCD

문제 https://leetcode.com/problems/find-greatest-common-divisor-of-array 풀이 수열 nums의 원소 중 가장 큰 원소의 가장 작은 원소의 GCD를 리턴하면 된다. 처음에 max()와 min()을 썼는데, 제출 시간이 거의 최하위권이길래 for loop로 다시 작성했다. GCD 자체는 유클리드 호제법을 이용해서 구한다. 코드 class Solution { func findGCD(_ nums: [Int]) -> Int { func gcd(_ a: Int, _ b: Int) -> Int { b == 0 ? a : gcd(b, a % b) } var min = Int.max var max = 0 for num in nums { min = min > num ? num : min max = max < num ? num : max } return gcd(min, max) } }

문제 https://leetcode.com/problems/sum-of-gcd-of-formed-pairs 풀이 문제에서 지시한 내용을 그대로 구현하면 되는 문제다. 문제의 지시사항은 다음과 같다: 인티저 배열 nums의 누적 최대값 배열 mx를 만든다. prefixGcd[i] = gcd(nums[i], mx[i]) 으로 이루어진 배열을 만든다. prefixGcd를 오름차순 정렬한다. prefixGcd의 제일 큰 값과 제일 작은 값의 쌍을 만들어, GCD를 구하는 것을 더 이상 만들지 못할 때 까지 반복한다. 만약 prefixGcd의 원소의 개수가 홀수라서 페어을 만들지 못한 하나가 남는다면 무시한다. ‘4’에서 구한 모든 GCD 값의 합을 리턴한다. 페어을 만드는건 간단한 형태의 투 포인터로 해결했다. 정렬과 유클리드 호제법을 제외하곤 모두 $O(n)$에 해결되기 때문에, 시간복잡도는 $O(n \log n + n \log V) = O(n \log (nV))$이다. ...

문제 https://leetcode.com/problems/gcd-of-odd-and-even-sums 풀이 인티저 n이 하나 주어지고 작은 짝수 n개, 가장 홀수 n개를 각각 모두 더한 합 간의 GCD를 구하는 문제이다. 문제에서 요구하는 내용이 너무 간단해서, gcd()를 쓰지 않고, 유클리드 호제법을 직접 작성해서 GCD를 구했다. 코드 class Solution { public: int gcdOfOddEvenSums(int n) { int sumOdd = 0; int sumEven = 0; for (int num = 1; num <= n * 2; num++) { if (num % 2 == 0) sumEven += num; else if (num % 2 != 0) sumOdd += num; } while(sumEven) { sumOdd %= sumEven; swap(sumOdd, sumEven); } return sumOdd; } };

문제 https://leetcode.com/problems/find-the-number-of-subsequences-with-equal-gcd 풀이 수열 nums이 주어지고, nums에서 서로 원소가 겹치지 않게 부분 수열을 두 개 만든 뒤, 각 부분 수열(이하 A, B라 함)의 GCD가 같은 경우의 수를 찾는 문제이다. 만약 브루트 포스를 시도한다면, 원소의 개수 n, 각 원소가 가질 수 있는 상태가 3개(부분 수열 A, 부분 수열 B, 아예 미포함)이므로, 시간 복잡도가 $O(n \times 3^n)$ 이 되는데, nums의 최대 크기가 200이므로 유효한 시간 내에 해결할 수 없다. 하지만 부분 수열을 점점 채워나가면서 두 부분 수열을 비교할 수 있으므로, DP를 사용하면 O(n * 부분 수열A의 최대 gcd * 부분 수열B의 gcd 최대값)이 된다. 문제의 제약조건에서 원소의 최대 크기는 200이고, GCD는 원소보다 클 수 없으므로, $O(n \times 200 \times 200)$으로 줄일 수 있다. ...