여러 숫자들의 최대공약수를 찾아야 하는 상황입니다. 일단 gcd(a, b) 는 유클리드 호제법 사용합니다. 몇만개의 숫자에 대해 짧은 시간안에 해답이 나와야 하므로 효율적인 알고리즘을 고민하고 있는데요.
처음에 생각할 수 있는 방법으로는 한쌍씩 최대공배수를 구하여 N개의 숫자가 있다면 N-1번의 gcd()를 호출하는 방법이 있습니다만, 일단 이것은 시간이 너무 많이 걸립니다.
그래서 제가 선택한 방법은 매번 두개씩 쌍으로 묶어서 숫자들의 개수를 반으로 줄여나가는 방법입니다. 머지소트에서 착안을 했죠. 예를 들어 처음 숫자들의 개수가 8개라면 8개 -> 4개 ->2개 -> 1개 이렇게 되겠죠. 숫자들의 개수가 N = 2^k 일 경우 총 2^(k-1) + 2^(k-2) + ... + 2 + 1 의 gcd 호출이 있게 됩니다. 그럼 N-1 번의 gcd 호출이 있게 되겠죠. 어라 지금 보니 전혀 개선된 방법이 아니구나. 그래서 시간이 여전히 오래걸렸군
..이왕 이렇게 된거 프게분들의 아이디어를 빌려봅니다. gcd(a, b) 의 수행시간이 O(log b) 인 점을 공략해야 하나 싶기도 하고..
글쓰기