Computer Science/자료구조 및 알고리즘

연결리스트

연결리스트는 차례로 연결된 노드를 표현해주는 자료구조이다. 배열과 달리 특정 인덱스를 상수 시간에 접근할 수 없다. linked list 장점 : Linked list의 길이를 동적으로 조절 가능, 데이터의 삽입과 삭제가 쉬움 linked list 단점 : 임의의 노드에 바로 접근할 수 없음, 다음 노드의 위치를 저장하기 위한 추가 공간이 필요함, Cache locality를 활용해 근접 데이터를 사전에 캐시에 저장하기가 어려움, 거꾸로 탐색하기 어려움 Runner 기법 Runner(부가 포인터라고도 함)는 연결리스트 문제에서 많이 활용되는 기법으로 연결리스트를 순회할 때 두 개의 포인터를 동시에 사용하는 것이다. 이때 한 포인터가 다른 포인터보다 앞서도록 하는데 앞선 포인터가 따라오는 포인터보다 항상 ..

해시 테이블

해시 테이블은 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료구조이다. 해시 테이블의 시간 복잡도는 O(1)이다. 키와 값을 해시 테이블에 넣을 때 거치는 과정 키의 해시 코드를 계산 해시 코드를 이용하여 배열의 인덱스를 구함 배열의 각 인덱스에 키와 값으로 이루어진 연결 리스트가 존재 해시 함수의 두가지 성질 입력 원소가 해시 테이블 전체에 고루 저장되어 있어야 함 계산이 간단해야 함 ⭐️ 첫번째 성질이 중요: 이 성질을 잘 만족해야 서로 다른 두 원소가 한 주소를 놓고 충돌할 확률이 작아짐 해시 함수를 만드는 두 가지 방법 나누기 방법 : 해시 테이블 크기보다 큰 수를 해시 테이블 크기 범위에 들어오도록 수축시킴 h(x) = x mod m ⭐️ 여기서 m은 테이블의 크기..