[알고리즘]Algospot_FANMEETING

출처 : 가장 멤버가 많은 아이돌 그룹으로 기네스 북에 올라 있는 혼성 팝 그룹 하이퍼시니어가 데뷔 10주년 기념 팬 미팅을 개최했습니다. 팬 미팅의 한 순서로, 멤버들과 참가한 팬들이 포옹을 하는 행사를 갖기로 했습니다. 하이퍼시니어의 멤버들은 우선 무대에 일렬로 섭니다. 팬 미팅에 참가한 M명의 팬들은 줄을 서서 맨 오른쪽 멤버에서부터 시작해 한 명씩 왼쪽으로 움직이며 멤버들과 하나씩 포...

카라츠바algorithmalgospot분할정복algorithm

카라츠바의 빠른 곱셈 알고리즘

분할 정복 알고리즘의 한 예로, 재미있는 병합과정을 가진 알고리즘이다. 수 백 자리 이상의 큰 수의 곱셈할 때 사용하는 빠른 곱셈을 위해 만들어졌다. 기본적인 곱셈 방법 두 자연수의 십진수 표기가 배열에 주어진다고 할 때, 이 둘을 곱한 결과를 계산하는 가장 기본적인 방법은 아래 그림과 같다 이 과정을 코드로 곧장 옮깃 것이 아래와 같다 이 알고리즘의 시간복잡도는 두 정수 배열의 길이가 모두...

큰수의곱셈알고리즘카라츠바karatsubaalgorithmalgorithm