알고리즘/잡설
vector push_back은 느리다. reserve!
BOJ2401 약 2주일간 고생한 문제다. 해법은 kmp + dp로 간단한 편이나 시간초과가 날 리가 없는 시간복잡도인데 시간초과가 나버린다. 며칠간 생각해봐도 이 이상의 풀이를 생각해내기가 불가능하다고 판단해서 풀이를 봤는데, 풀이도 똑같은 풀이를 썼다. 한 주간 이것 저것 막 해보다가 발견해낸 차이점은 각각의 index에 matching된 문자열의 길이를 vector로 관리한 코드들은 전부 시간초과가 뜨고 배열로 관리한 코드들은 전부 ac가 됐다는 점이다. 이론상 push_back의 속도는 O(1)이지만 이게 Amortized O(1)이라는 점이 중요하다. 최악의 경우에는 O(n)의 시간복잡도를 갖기 때문에 함부로 O(1)이라고 판단하면 안 된다. 그래서 검색해보니 vector의 reserve를 사용..
