땅다람쥐의 개발 일기

알고리즘 해답 중에 해시맵을 배열로 속도가 빨라지는 경우가 있어서, 그 부분을 기록으로 남길까 합니다. 왜 배열로 바꿨을 때 빨라질까?배열이나 해시맵이나 원소(Element)에 접근할 때의 시간 복잡도는 O(1)로 같습니다. 하지만 해시맵은 내부적으로 해시 함수를 거쳐야 하는 등 여러 오버헤드가 발생하기 때문에, 실제 연산 속도는 배열이 훨씬 빠릅니다.두 구조의 내부 접근 순서를 비교해 보면 다음과 같습니다.배열: Arr[Index] => 인덱스를 통한 메모리 주소 접근 => 원소 반환해시맵: Map.get(key) => 해시 함수(Hash Function) 연산 => 해시 값을 버킷 인덱스로 변환 => 해당 버킷 접근 => Collision 있을 시 연결 리스트나 트리 탐색 및 Key 동등성 비교 =>..

array 배열 sort 정렬하다 linear 선형의 element 원소 index 색인 sequential 순차적인 학교에서 자료구조 관련된 수업을 들었을 때 처음 배웠던 개념이 Linked list인게 기억나네요. 그 당시 기억을 회상해보면 잘만 쓰던 Array(배열)이 있는데, 왜 굳이 Linked List를 써서 머리 아프게 또 pointer를 써야하는지 짜증났던 기억이 납니다. 심지어 둘 다 똑같은 Linear data structure인데! 왜 Linked List를 저희가 배우고 써야 되는걸까요? Array의 size에는 한계가 있습니다. Array를 declare 할 때 마다, upper limit size를 정해줘야 하는 부분이 있습니다. 그 말은 즉 무한정으로 배열의 수를 증가시키기가 ..