-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
분할정복에서 큰 정수 곱셈 다른 계산법?
20.09.30 00:23 작성 조회수 171
1
안녕하세요! 이제 분할정복 파트를 완강했습니다.
재밌게 잘 설명해 주셔서 너무 흥미롭게 듣고 있습니다.
큰 정수 곱셈 부분을 듣다가 문득 떠오른 생각인데
이러한 문제를 행렬로 해결할 수 있을지 의문점이 들었습니다.
혹시 행렬을 이용해서 더 빠르게 풀수 있는 방법이 있을까요?
답변을 작성해보세요.
0
주니온
지식공유자2020.09.30
아주 재미있는 발상을 해 보셨네요.
관련 논문을 좀 더 찾아봐야겠지만, 즉답을 드리자면,
행렬을 이용하는 방법으로는 더 빠르게 풀 수 있을 것 같지 않습니다.
But,
이 질문을 보니 알고리즘을 제대로 공부할 수 있는 탁월한 자질을 가지셨습니다.
발상의 전환을 해보는 것에서 알고리즘의 진정한 묘미를 느끼실 수 있으실 겁니다.
1. 아이디어
큰 정수의 곱셈을 행렬을 이용해서 더 빠르게 풀 수 있을까?
2. 전개
큰 정수의 곱셈은 두 개의 1차원 벡터의 곱셈(내적 또는 외적)을 확장한 것과 같다.
큰 정수의 표현을 행렬로 바꾸면 행렬 곱셈으로 치환할 수 있지 않을까?
4. 시도
일반적인 행렬 곱셈은 n^3이지만, 쉬트라센 알고리즘에 의해 n^2.5 이하로 단축될 수 있다.
큰 정수의 곱셈과 시간 복잡도를 비교해 보면 더 나은 것 같기도 하지만,
큰 정수 곱셈 알고리즘보다 빠를 것 같지 않지만, 한 번 시도해 보자.
5. 검증
직접 해보니 시간 복잡도는 이렇게 나오고, 실행 속도는 이렇게 나오네?
실패다. 하지만, 이 방식을 다른 문제에 적용해 볼 수 있지 않을까?
요렇게 공부를 해 보시면, 대학원 수준의 논문을 쓸 수 있게 되실 것 같습니다.
꼭 한 번 도전해 보시길 응원하겠습니다!
답변 1