2023.04.20 TIL

토깽이연구소 수석연구원·2023년 4월 21일

TIL 자료구조

TIL

목록 보기

14/37

오늘의 나는 무엇을 잘했을까?

페어 프로그래밍을 잘 마무리 했다. 같이 고민하면서 코딩을 하니까 확실히 아이디어도 많이 나오는 것 같고 혼자 칠 때보다 효율적으로 분량이 끝나는 것 같다.

오늘의 나는 무엇을 배웠을까?

Open addressing을 통한 해시테이블 충돌 해결

해싱을 통해 다른 키가 한 값이 되어 인덱스 충돌이 일어나면, 다른 비어있는 인덱스를 찾는 기법이다. 그렇다면 비어있는 인덱스를 찾는 로직은 뭘까?

선형 탐사(linear probing)
- 충돌이 일어났을 때, 한 칸씩 다음 인덱스가 비었는지 확인
- 예를 들어 해싱을 통해 인덱스 20을 얻었는데 20번 인덱스에 이미 데이터가 있다면, 20에서 하나씩 더해가면서 처음으로 빈 인덱스가 나오면 거기에 저장하는 로직
제곱 탐사
- 충돌이 일어났을 때, 인덱스에 1 ~ n의 제곱을 더해가면서 빈 인덱스를 찾는 방법.
- 예를 들어 20번 인덱스에 충돌이 일어나면, 1의 제곱인 1을 더해 21번을 보고, 비어있지 않다면 2의 제곱인 4를 21번에 더해 25번 인덱스를 보고, 비어있는 인덱스를 찾을 때 까지 반복하는 로직
Open Addressing이 적용된 해시테이블 탐색/삭제
- 탐색: 선형 탐색이 적용된 경우, key 204를 가지는 데이터를 테이블에서 탐색하려면 다음과 같은 과정이 필요하다
  - 해싱: 204 → 20으로 해시값을 구한다
  - 20번 인덱스를 본다. 안에 데이터의 키가 204가 아니다.
  - 21번 인덱스를 본다. 또 아니다.
  - 22번 인덱스를 본다. 비어있다. 이것은 키가 204인 데이터는 이 해시테이블에 없다는 의미이다. 204의 키를 가진 데이터가 삽입되었다면 20번부터 올라가면서 가장 먼저 비어있는 곳에 선형 탐사를 통해 저장되었을 것이다. 즉, 20번부터 올라가면서 참색하다 하나가 비어있다면 그 이후에는 무조건 없다는 뜻이다.
- 삭제: 선형 탐사가 적용된 해시 테이블에서 key가 204인 데이터를 삭제하는 연산은 다음 과정이 필요하다.
  - 해싱: 204 → 20으로 해시값(인덱스)를 구한다
  - 20번 인덱스를 본다. 안에 데이터의 키가 204가 아니다
  - 선형 탐사를 진행하여 21, 22, 23…순서대로 확인하다가 key값이 204인 데이터를 찾으면, DELETED라는 표시를 해준다. 그냥 데이터를 빼는 것이 아닌 삭제되었다는 표시를 해 두는 이유는 해당 인덱스를 비워두면 안되기 때문이다. 인덱스 이후에 있는 값을 나중에 탐사할 때 빈 인덱스를 만나면 해당 데이터가 처음부터 없었던 것으로 판단하기 때문이다.
Open addressing 연산 시간 복잡도 (최악, 평균)
연산 시간 복잡도 (최악의 경우)
삽입 $O(n)$
탐색 $O(n)$
삭제 $O(n)$

연산 시간 복잡도 (평균)
삽입 $O(1)$
탐색 $O(1)$
삭제 $O(1)$

연산	시간 복잡도 (최악의 경우)
삽입	$O(n)$
탐색	$O(n)$
삭제	$O(n)$

연산	시간 복잡도 (평균)
삽입	$O(1)$
탐색	$O(1)$
삭제	$O(1)$

추상 자료형

기능과 구현의 차이
- 기능: 연산이 “무엇”을 하는지
- 구현: 연산을 “어떻게” 하는지
추상화
- 구현을 몰라도 기능만 알면 사용할 수 있게 만드는 것
추상 자료형(ADT)
- 자료 구조를 추상화한 것
- 데이터를 저장/사용할 때 “기능”만 생각
- 자료구조 자체에 집중하기보다, 추상자료형을 먼저 떠올리면 코드의 흐름에 집중할 수 있다. 각 탐색, 삭제, 삽입 이러한 연산의 구현보다는 기능을 사용해서 어떻게 접근할 지에 때해 고민할 수 있다.
- 큐, 스택은 모두 추상자료형이다. 이를 구현하기 위해 배열을 사용할 수도, 연결 리스트를 사용할 수도 있다.