🔘 백준 - 1629 곱셈

하트아욱국

---

# 1629

곱셈

🥈s1

 

A * A * A * ...B번 하기

O(B)

 

트리 깊이가 log2(B)이라고 치면

한 줄에 2개씩 생성되니까 2^n 등비수열의 합 트리 깊이만큼 하면~

값 똑같음

O(B)

?

 

아니 엥 멍청아

완전 이진 트리를 만들어버리네 

multiply(a,nextB) * multiply(a,nextB)

가 아니라

mul = multiply(a,b // 2)

if b % 2 == 1 : # odd

return mul * mul * A

하면 이제~

그냥 깊이만큼!

O(log2(B))

 

는 바로 시간 초과 나와버리고

직접 거듭제곱 연산 사용 (A ** B):
Python에서 A ** B는 내부적으로 효율적인 방식으로 거듭제곱을 계산
일반적으로 고속 거듭제곱 알고리즘인 'Exponentiation by squaring'를 사용
O(logB) 시간에 계산

이럴 거면

A ** B 냈지

---

모듈러 연산 

맨날 잊어버림

 

• (a+b) mod n = [(a mod n)+(b mod n)] mod n
• (a×b)mod  n = [(a mod  n)×(b mod  n)] mod  n 

 

맨 마지막에 한 번 하는 거랑 중간중간에 계속 하는 거랑 시간복잡도 차이?

=> 마지막에 한 번 큰 수를 나누는 게 훨씬 자원이 많이 소모된다~ 

---

킄ㅋ킄ㅋㅋ오늘 이쁘단 소리를 많이 들었다디코말ㄷ고도실제세상에서도!

머리도하고치마도입었지만 역시

추천