[정글 WEEK02_알고리즘] 개발 일지 - 2주차 마무리

공부 키워드

 - 이분 탐색

 - 분할 정복

 - 스택

 - 큐

 - 우선순위 큐

 - Linked List

 - 해시 테이블

 

 

지식의 연결

✏️ 파이썬 dict는 해시 충돌을 어떻게 해결하고, 해시 함수로 무엇을 쓸까? 

◼︎ 해시 충돌은 perturbation probing 기반의 open addressing 방식으로 해결한다.

 

단순히 버킷들을 한 칸씩 선형으로 탐색하는 것이 아니라, 해시값에서 유도한 perturb 값을 활용해 비트 연산과 시프트를 반복하며 다음 후보 인덱스를 계산한다.

perturb는 다음 탐색 위치를 다양하게 만들기 위한 보조 난수 값으로, 아래 코드에서 볼 수 있듯이 시작 인덱스를 계속 변화하게 만들어 충돌을 효과적으로 분산시킨다.

hash = 123456789
mask = 15         # table size = 16
perturb = hash
i = hash & mask   # 시작 인덱스

while 충돌:
    i = (5 * i + 1 + perturb) & mask
    perturb >>= 5

파이썬 dict의 이러한 구현은 C 언어로 작성된 CPython의 내부 구조에 기반한다. 

 

◼︎ 해시 함수로는 Sip Hash를 쓴다. (키로 문자열을 사용할 때)

(int, float, tuple, 사용자 정의 객체 등의 경우는 SipHash가 아니라 각자의 __hash__() 구현에 따라 달라진다.

문자열은 주로 사용자 입력, 네트워크 데이터 등 외부 입력으로 들어오기 때문에 해시 충돌 공격에 가장 취약한 타입이다. 따라서 파이썬은 보안상 중요한 문자열에만 SipHash를 적용하고, 나머지 타입은 속도를 더 중요하게 생각해서 단순한 수학적 해시를 사용한다.)

 

SipHash는 짧은 메세지를 빠르게 처리하면서도 보안성이 높은 해시함수로, 아래와 같은 주요 장점들을 가지고 있다. 

 

1) 충돌 공격에 강하다.

 내부에 비밀 키(k0, k1)를 사용해 공격자가 해시 값을 예측하거나 조작하기 매우 어렵다.

2) 빠르다.

 HMAC-HSA256이나 SHA1과 비교해도 훨씬 빠르고, 특히 1~16 바이트의 짧은 문자열에 대해 매우 빠른 성능을 보인다.

3) 해시값의 균일한 분산이 가능해 해시 테이블에 최적화돼있다.  

해시값의 충돌 확률이 낮고, 해시 테이블에 균등하게 분산된다.

4) 매 실행마다 해시값이 달라진다. (hash randomization)

 비밀 키(k0, k1) (시드 키) 가 바뀌면 해시값도 바뀐다. 파이썬에서는 매번 실행 시 랜덤 시드를 부여해서 같은 문자열도 다른 해시값을 갖게 한다.

 

✏️ 파이썬은 어떤 array인지?

 파이썬은 "동적" 배열로, 내부적으로는 C로 구현되어있다. (PyListObject)

모든 요소들이 메모리상 연속적으로 저장되고, 시작 위치 + 오프셋 계산만으로 특정 위치를 찾을 수 있기 때문에 O(1)에 원하는 위치에 접근이 가능하다.

특이한 점은 초기 용량(capacity)를 초과하면 더 큰 메모리 블록을 할당함으로써 resize하고, 기존 데이터를 복사해서 확장한다. 이 때는 접근 속도가 느려지기 때문에 미리 충분한 양의 크기를 할당하면 항상 O(1)에 접근이 가능하다.

 

JavaScript의 Array, Java의 ArrayList, C++의 vector는 모두 동적 배열(Dynamic Array)에 해당하며, C의 arr과 Java의 Array는 정적 배열(Static Array)이다.  

 

 

✏️ 파이썬에서 for문 순회 시 range()와 list의 차이점?

 range()는 __next__()로 다음 요소를 호출해야 값이 나오는 lazy evaluation을 하기 때문에 메모리를 효율적으로 사용할 수 있는 반면, list는 모든 요소들만큼 메모리를 차지한다. 

 

 

✏️ 파이썬에서 리스트를 만들 때 '표현식  for 변수 in iterable'을 []로 감싸는 형태를 쓸 수 있는데, [] 대신 ()로 감쌌을 때 어떤 객체가 만들어지고 리스트와 어떻게 다를까? 

 (표현식 for 변수 in iterable)을 사용하면 제너레이터가 만들어진다. 

 [표현식 for 변수 in iterable]은 List Comprehension, (표현식 for 변수 in iterable)은 Generator Expression이라고 칭한다. 

제너레이터는 lazy evaluation 방식으로 다음 요소를 호출해야 결과값이 생성되고 메모리 사용량이 적은 반면, 이터레이터는 모든 데이터를 가지고 있다가 바로바로 결과값을 생성해주는 eager evaluation 방식으로 속도는 빠르지만 메모리 사용량이 많다.

 

✏️ 파이썬에서 튜플과 리스트의 차이

튜플은 변경 불가한 immutable 타입이고, 리스트는 변경 가능한 mutable 타입이다. 따라서 튜플은 immutable 타입을 필요로 하는 딕셔너리의 키로 사용 가능한 반면, 리스트는 사용할 수 없다. 또, 튜플은 불변이기 때문에 최적화가 쉬워 비교나 반복 처리 같은 연산 성능이 빠른 반면 list는 느리다. 마지막으로, 튜플은 구조가 단순해서 메모리 접근이 빠르고 연산 부담도 적지만 리스트는 요소 외에도 capacity, resizing 등의 동적 배열 관리 정보를 저장하고 있기 때문에 튜플에 비해 무겁다. 

 

 

 

💡 무언가에 대한 정의를 할 때 operation에 대해서 생각해보자.