자료구조 2

1. 해시테이블해시테이블이란 해시함수를 이용해 키를 값에 매핑하는 자료구조구현충돌아무리 좋은 해시 함수라도 충돌을 피하기는 어렵다.예측 가능한 범위 내에서 해시값이 나오고, 데이터와 짝지어지는 것이기 때문에 해시값이 중복될 수 있다. 👉🏻 입력값이 달라도 똑같은 결과가 나오면 충돌이를 다루는 방식은 체이닝(Chaining), 오픈 어드레싱(Open Addressing) 이 있다.오픈 어드레싱은 탐사를 통해 ‘빈 공간을 찾아나서는’ 방식체이닝은 충돌 발생 시 ‘연결’해가는 것오픈 어드레싱 O(1)체이닝 O(n)오픈 어드레싱은 값이 뭉치는 클러스터링이 발생할 수 있고,체이닝은 메모리 오버헤드와 길어질 경우 탐색이 느려진다는 단점그래서 각 언어 별로 해시테이블의 구현 방식이 다른데요. C++, Java, ..

자료구조에 대해 알아보자.배열동일한 데이터 타입의 요소들을 연속된 메모리 공간에 순서대로 저장하는 자료구조데이터 조회에서 O(1)의 시간 복잡도를 가진다.장점연속된 메모리 공간을 사용하므로 처음 데이터의 주소를 알면 나머지도 쉽게 찾을 수 있다.단점크기가 고정되어 추가/삭제에 제약이 있다.연결리스트각각의 데이터가 메모리 공간 상에 고유한 노드로 존재하며, 해당 노드에 앞과 뒤의 메모리 주소를 기억하고 있는 형태즉, 노드들이 서로 연결되어 있는 구조데이터 조회 시 순차적으로 탐색하기 때문에 O(N)의 시간 복잡도데이터 추가와 삭제에는 O(1)의 시간 복잡도Array vs Linked List배열 (Array): 파이썬의 리스트. 접근 쉬움, 삽입 어려움. (파이썬의 리스트)연결리스트: 직접 구현. 접근 어..