작성한 질문수 1

0

아주 재미있는 발상을 해 보셨네요.

관련 논문을 좀 더 찾아봐야겠지만, 즉답을 드리자면, 
행렬을 이용하는 방법으로는 더 빠르게 풀 수 있을 것 같지 않습니다.

But, 

이 질문을 보니 알고리즘을 제대로 공부할 수 있는 탁월한 자질을 가지셨습니다.
발상의 전환을 해보는 것에서 알고리즘의 진정한 묘미를 느끼실 수 있으실 겁니다.

1. 아이디어

큰 정수의 곱셈을 행렬을 이용해서 더 빠르게 풀 수 있을까?

2. 전개

큰 정수의 곱셈은 두 개의 1차원 벡터의 곱셈(내적 또는 외적)을 확장한 것과 같다.
큰 정수의 표현을 행렬로 바꾸면 행렬 곱셈으로 치환할 수 있지 않을까?

4. 시도

일반적인 행렬 곱셈은 n^3이지만, 쉬트라센 알고리즘에 의해 n^2.5 이하로 단축될 수 있다.
큰 정수의 곱셈과 시간 복잡도를 비교해 보면 더 나은 것 같기도 하지만,
큰 정수 곱셈 알고리즘보다 빠를 것 같지 않지만, 한 번 시도해 보자.

5. 검증

직접 해보니 시간 복잡도는 이렇게 나오고, 실행 속도는 이렇게 나오네?
실패다. 하지만, 이 방식을 다른 문제에 적용해 볼 수 있지 않을까?

요렇게 공부를 해 보시면, 대학원 수준의 논문을 쓸 수 있게 되실 것 같습니다.
꼭 한 번 도전해 보시길 응원하겠습니다!