unordered_map과 배열의 성능 차이오프라인 쿼리 문제를 풀다가 unordered_map을 이용하면 시간초과가 나고 배열을 사용하면 시간이 단축되는 경험을 했다. 둘 다 접근할 때 O(1)으로 알고 있었는데, 어디서 차이가 날까 생각해보았다. 해시충돌 때문이라고 넘어갈까 했지만 자세히 알아보고 기록해두는 게 좋을 거 같아서 포스팅하기로 결정했다. 1. unordered_map vs 배열a) unordered_map의 특성시간 복잡도평균적으로 O(1) 시간에 접근 가능핮만 최악의 경우 O(N)으로 느려질 수 있음 (해시 충돌 발생 시)캐시 활용도unordered_map은 내부적으로 해시 테이블을 사용하며 데이터가 메모리 상에 분산되어 저장된다.따라서 캐시 적중률(cache hit rate)가 낮아질..
