Redddy's Devlog

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

🧩문제 해석 채팅방에서 사용한 임티갯수를 출력하면 되는 문제였다. 사람들은 새로운 사람이 들어왔을 때 임티를 사용하고 그 다음은 일반 대화를 이어나간다. 즉, 새로운 들어왔을 때 사용한 임티 갯수를 전부 더해주면 되는 문제이다. 📕 풀이 dict() 자료형을 사용하여 문제를 풀었다. 새로운 사람이 들어오면 dict()의 값들을 리셋해주었다. 💻 코드 import sys input = sys.stdin.readline cnt = 0 # 임티갯수 변수 user = {} # 이름과 임티사용을 확인할 변수 for i in range(int(input().rstrip())): # 채팅방의 기록수만큼 for문을 돌린다 # 채팅내용입력받음 s = input().rstrip() # 새로운 사람이 들어왔을때 if s =..

⚽ 서론 dict() 형 그러니까 해시를 사용한 집합과 맵에서 새로운 걸 발견해서 글로 남기기로 했다! 🧩문제 해석 포켓몬 이름을 받은 뒤 받은 순서대로 포켓몬 도감에 저장한다. 포켓몬 이름을 문제로 냈을 때 그 포켓몬이 몇번째로 도감에 등록됐는지 출력하고, 수를 입력했을 때는 그 수의 등록된 포켓몬 이름을 출력하면 되는 문제 (걸그룹 마스터 문제랑 비슷한 유형이다) 📖 풀이 처음에는 포켓몬 이름을 입력받으면 key에는 이름을, value에는 수를 저장한 다음 문제를 맞출 때 이름이 들어오면 포켓몬도감[이름] 이런식으로 출력하면 됐지만 수가 입력될 때는 값을 하나하나 찾아야 했다. 즉 key가 입력되면 바로 찾을 수 있지만 value가 입력되고 key 값을 찾으려면 하나하나 다 돌아야 했었다. value..