아롱이의 PS하는 블로그

이번 글에서 다뤄볼 주제는 FFT를 구현 안하고 FFT 문제를 빨리 푸는 방법이다.얼마전에 FFT를 알고리즘 스터디 시간에 열심히 증명하고, 파이썬으로 구현체를 열심히 만들었던 기억이 있다.물론, 구현체는 아직도 외우지 못해서 내가 예전에 만든걸 복붙하고 있다. 하지만, , , , , 가끔씩 숏코딩을 들어가보면 터무니없이 짧은 길이의 코드들이 있다.도대체 어떻게 푼 것일까???? 1. 파이썬 언어의 특징파이썬에서는 C++과 달리 매우 큰 수 연산이 쉽게 가능하다.파이썬 내부적으로 큰 수 연산을 어떠한 방법을 써서 하기 때문이다.곱셈을 예를 들자면, 자리수가 적당히 작으면 파이썬은 그냥 우리가 알고있는 곱셈 방법을 쓴다.다만, 자리수가 적당히 커지면파이썬은 FFT를 기반으로 한 알고리즘이나 카라추바 알고..

"파이썬으로 구현하는"시리즈 3매내처(Manacher)오늘은 갑자기 뜬금없이 파이썬으로 구현하는 매내처에 대해서 알아볼 것이다.원래는 세그먼트 트리 바텀업을 먼저 적었어야 했는데, 문제풀다가 매내처라는 천재적인 알고리즘을 공부하게 되어서 정리해본다. 먼저 매내처가 뭐하는 알고리즘인지 알아보자.팰린드롬이란 무엇인가?앞뒤가 대칭인 문자열을 팰린드롬이라고 한다. 우리말로 회문이라고 한다.예시로는 다음이 있다. 'bob''ABCBA''WAS IT A CAT I SAW' (이상한 나라의 앨리스에 나오는 유명한 회문)'다시합창합시다' 다음과 같은 예시들은 팰린드롬이 아니다. 'apple''팰린드롬''알고리즘' 매내처는 팰린드롬을 다루는 알고리즘인데, 구체적으로는 다음과 같은 문제를 풀 때 쓰인다. 문자열 S가 주어..