99클럽 3기 2일차

쉬어가는 날인가 보다!!

Notion에서 작성한 글이라, 여기에서 더 깔끔하게 보실 수 있습니다 😮😊

---

[Beginner] 평균 구하기

[평균 구하기]

나누는 문제라 부동소수점 오차를 생각해야하나 했으나 그런 문제는 아니고 단순히 언어 처음 배울 때 나오는 연습문제 수준이었다.

Solution) $O(n)$

return sum(arr)/len(arr)

---

[Middler] x만큼 간격이 있는 n개의 숫자

[x만큼 간격이 있는 n개의 숫자]

오늘은 쉬어가는 날인가보다. 어제 미들러 문제의 기억,,, 때문에 엥??? 뭐지??? 혹시 Sliding Window?? Prefix Sum?? 뭔가 엄청난 게 있을 줄 알았는데 다른 언어에서 Integer overflow만 주의할 것 외엔 문제될 게 없어보였다.

Solution) $O(n)$

return [x*i for i in range(1, n+1)]

---

[Challenger] 숫자 카드 나누기

[숫자 카드 나누기]

• 철수/영희가 가진 카드들에 적힌 모든 숫자를 나눌 수 있는 수는 $GCD$를 의미한다. 이를 $GCD_a$, $GCD_b$라 하자.

• 여기서, $GCD_a$, $GCD_b$에 대해 $arr_b$, $arr_a$의 모든 수들을 나눌 수 없다면 두 $GCD$중 큰 값을 return하면 된다. 만약 하나라도 나눌 수 있는 수가 존재한다면 $GCD$ 대신 0을 return하고, 두 값의 대소를 비교하면 된다.

• 공약수까지 함께 비교할 필요 없이 $GCD$로 상대의 $arr$의 각 수들에 대해 나눌 수 있는지 비교해도 된다.

  Proof. 공약수들은 $GCD$의 약수이므로, $GCD$가 어떤 수를 나눌 수 없으면, 그 $GCD$의 모든 약수(공약수)도 그 수를 나눌 수 없다.
  

Solution) $O(n \lg{k})$

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

def gcd_arr(arr):
    ret = arr[0]
    for i in range(1, len(arr)):
        ret = gcd(ret, arr[i])
    return ret

def x_gcd(gcd, arr):
    if all(n%gcd != 0 for n in arr):
        return gcd
    return 0

def solution(arrayA, arrayB):
    return max(x_gcd(gcd_arr(arrayA), arrayB), x_gcd(gcd_arr(arrayB), arrayA))

---