Redddy's Devlog

🔈 문제koosaga와 cubelover가 "핌버"를 하고 있다. 핌버는 님 게임에 규칙을 추가한 게임이다. 핌버는 돌을 차곡 차곡 위로 쌓아올린 돌 더미 k개를 이용한다. 각각의 돌 더미에는 한 개 이상의 돌이 있다. 두 사람은 서로 턴을 번갈아가면서 핌버를 진행한다. 각 사람의 턴이 되면, 돌 더미 하나를 선택해 돌을 제거한다. 제거한 돌의 개수는 피보나치 수여야 한다. 전체 돌 더미에서 마지막 돌을 제거하는 사람이 게임을 이기게 된다.  게임은 koosaga가 먼저 시작한다. 두 사람이 최적의 방법으로 게임을 진행했을 때, 이기는 사람을 출력한다. 📝입력첫째 줄에 돌 더미의 개수 $N$ $(1 ≤ N ≤ 10^5)$이 주어진다. 둘째 줄에 각 돌 더미에 쌓여있는 돌의 개수 $P_i$ $(1 ≤ ..

서론코드포스를 참가하다보면 라운드 중일 때에는 Accept 떠서 기분좋게 다른 문제 풀러 갔지만, 시스텟 돌 때 TLE가 터지는 경우가 어떤 자료구조를 사용하면 99% 있다. 이유는 바로 해시 저격 때문이다. 우리는 해시 맵의 조회, 삭제, 삽입 연산이 $O(1)$이라고 알고 그렇게 사용해왔다. 하지만 이는 평균 시간복잡도이지 최악의 경우 $O(1)$을 보장해주지 못하고 $O(n)$이 된다. 파이썬에서 해시를 사용하는 dict와 set은 물론이고 collections의 Counter와 defaultdict 역시 해시 저격에 안전하지 않다. 본론해시 저격이 가능한 이유는 해시 충돌이 생기기 때문이다.먼저 해시 충돌에 대해 설명해보자면,,, 해시는 임의의 데이터를 고정된 크기의 값으로 변환해주는 과정이다. ..