티스토리 뷰

BOJ2401

약 2주일간 고생한 문제다.

해법은 kmp + dp로 간단한 편이나 시간초과가 날 리가 없는 시간복잡도인데 시간초과가 나버린다.

몇 일간 생각해봐도 이 이상의 풀이를 생각해내기가 불가능하다고 판단해서 풀이를 봤는데, 풀이도 똑같은 풀이를 썼다.

한 주간 이것 저것 막 해보다가 발견해낸 차이점은 각각의 index에 matching된 문자열의 길이를 vector로 관리한 코드들은 전부 시간초과가 뜨고 배열로 관리한 코드들은 전부 ac가 됐다는 점이다.


이론상 push_back의 속도는 O(1)이지만 이게 Amortized O(1)이라는 점이 중요하다. 최악의 경우에는 O(n)의 시간복잡도를 갖기 때문에 함부로 O(1)이라고 판단하면 안 된다. 그래서 검색해보니 vector의 reserve를 사용한 후 push_back을 하면 속도가 많이 줄어든다는 얘기를 듣고 reserve를 사용해서 제출해보니 ac가 떴다.

그래서, 실제로 reserve를 쓰고 난 후 push_back을 썼을 때, 그냥 push_back을 썼을 때, 그리고 배열로 관리할 때 얼마나 속도 차이가 나는가 비교해보았다.


코드


컴파일 옵션


결과


수 십번 돌려 본 후 가장 표본이라고 생각되는 결과를 뽑아보았다.


관찰 결과

1. 배열과 reserve로 미리 capacity를 확장한 후 push_back은 1.5배 차이난다.

2. 배열과 그냥 push_back은 2.5배 차이난다.


백준 문제를 풀 때에나, 최대 입력개수를 알 때에는 무조건 reserve를 한 번 해주자. 시간 내에 아슬아슬하게 들어오는 코드이거나 시간초과가 뜰 수가 없는 시간복잡도인데 시간초과가 뜰 때에는 vector을 배열로 바꿔주거나 reserve를 써주자.

댓글
댓글쓰기 폼
공지사항
Total
5,447
Today
0
Yesterday
19
링크
«   2019/08   »
        1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31
글 보관함