CHIPMAKER

1. 카라츠바 알고리즘

다른 사람 C++ 코드를 보고 phython으로 옮겨 봤다.

알고리즘의 Insight는 아래 유투브 강의에 잘 나와 있다.

https://www.youtube.com/watch?v=7JvRFnxn3W0

def normalize(a): a.append(0) for i in range(len(a)-1): if a[i] < 0: borrow = (abs(a[i]) + 9) // 10 a[i+1] -= borrow a[i] += borrow*10 else: a[i+1] += (a[i] // 10) a[i] %= 10 while len(a) > 1 and a[-1] == 0: a.pop() def multiply(a, b): length = len(a) + len(b) + 1 c = [0] * length for i in range(len(a)): for j in range(len(b)): c[i+j] += (a[i] * b[j]) normalize(c) return c def addTo(a, b, k): newLength = max(len(a)+1, len(b)+k) #a = a + [0]*(newLength - len(a)) zeroFillNum = newLength - len(a) while zeroFillNum > 0: a.append(0) zeroFillNum -= 1 for i in range(len(b)): a[i+k] += b[i] normalize(a) def subFrom(a, b): newLength = max(len(a)+1, len(b)) +1 zeroFillNum = newLength - len(a) while zeroFillNum > 0: a.append(0) zeroFillNum -= 1 for i in range(len(b)): a[i] -= b[i] normalize(a) def karatsuba(a, b): if len(a) < len(b): return karatsuba(b, a) if len(a) == 0 or len(b) == 0: return [] if len(a) < 2: return multiply(a, b) half = len(a) // 2 a0 = a[:half] a1 = a[half:] b0 = b[:min(len(b), half)] b1 = b[min(len(b), half):] # z2= a1*b1 z2 = karatsuba(a1, b1) # z0= a0*b0 z0 = karatsuba(a0, b0) # a0 = a0 + a1 # b0 = b0 + b1 addTo(a0, a1, 0) addTo(b0, b1, 0) #z1 = (a0+a1)*(b0+b1)-z0-z2 z1 = karatsuba(a0, b0) subFrom(z1, z0) subFrom(z1, z2) result = [] addTo(result, z0, 0) addTo(result, z1, half) addTo(result, z2, half+half) return result if __name__ == '__main__': #a = [8, 2, 7] #b = [4, 4] a = [1, 2, 3, 4, 5, 6, 7, 8, 9] b = [9, 8, 6, 5, 4, 3] result = karatsuba(a[::-1], b[::-1]) #print(827*44) print(123456789*986543) print(result)

2. 팬미팅 소스

https://www.algospot.com/judge/problem/read/FANMEETING

Normalize 코드를 빼주고, fan의 순서를 뒤집어 주는 것이 원본 카라츠바 알고리즘과 차이점

def multiply(a, b): length = len(a) + len(b) + 1 c = [0] * length for i in range(len(a)): for j in range(len(b)): c[i+j] += (a[i] * b[j]) return c def addTo(a, b, k): newLength = max(len(a)+1, len(b)+k) zeroFillNum = newLength - len(a) while zeroFillNum > 0: a.append(0) zeroFillNum -= 1 for i in range(len(b)): a[i+k] += b[i] def subFrom(a, b): newLength = max(len(a)+1, len(b)) +1 zeroFillNum = newLength - len(a) while zeroFillNum > 0: a.append(0) zeroFillNum -= 1 for i in range(len(b)): a[i] -= b[i] def karatsuba(a, b): if len(a) < len(b): return karatsuba(b, a) if len(a) == 0 or len(b) == 0: return [] if len(a) <= 2: return multiply(a, b) half = len(a) // 2 a0 = a[:half] a1 = a[half:] b0 = b[:min(len(b), half)] b1 = b[min(len(b), half):] # z2= a1*b1 z2 = karatsuba(a1, b1) # z0= a0*b0 z0 = karatsuba(a0, b0) # a0 = a0 + a1 # b0 = b0 + b1 addTo(a0, a1, 0) addTo(b0, b1, 0) #z1 = (a0+a1)*(b0+b1)-z0-z2 z1 = karatsuba(a0, b0) subFrom(z1, z0) subFrom(z1, z2) result = [] addTo(result, z0, 0) addTo(result, z1, half) addTo(result, z2, half+half) return result def hugs(a, b): N = max(len(a), len(b)) M = min(len(a), len(b)) inta = [1 if v == 'M' else 0 for v in a] intb = [1 if v == 'M' else 0 for v in b] intb.reverse() C = karatsuba(inta[::-1], intb[::-1]) allHugs = 0 for i in range(M-1, N): if C[i] == 0: allHugs += 1 return allHugs if __name__ == '__main__': members = ['FFFMMM', 'FFFFF', 'FFFFM', 'MFMFMFFFMMMFMF'] fans = ['MMMFFF', 'FFFFFFFFFF', 'FFFFFMMMMF', 'MMFFFFFMFFFMFFFFFFMFFFMFFFFMFMMFFFFFFF'] for i in range(len(members)): result = hugs(members[i], fans[i]) print(result)