데이터 엔지니어링 데브코스 2주차 - 목요일

학습주제
[수업] 알고리즘/ 자료구조 : Hash, Sort



주요내용

수업을 통해 Hash와 Sort를 통해 쉽게 해결할 수 있는 알고리즘 문제들을 풀어봤다. 기존에도 파이썬의 딕셔너리와 파이썬을 잘 활용하고 있었지만, 추가적으로 궁금증이 생겨서 각 자료형의 성질과 시간 복잡도 등 특징을 간략히 정리해본다.

 

1.  해시(Hash)

• 키(key)에 데이터(value)를 저장하는 자료구조이다.
• 데이터를 저장하는 공간을 해시테이블이라고 한다.
• 키와 해시테이블 사이에는 해시함수가 동작한다. 해시함수는 키에 대한 산술연산을 이용해 나온 해쉬 값 혹은 주소를 바탕으로 해시테이블에서 데이터의 위치를 단번에 확인할 수 있도록 하는 함수이다.
• 해쉬주소를 통해 해시테이블에 접근하므로 일반적으로 O(1) 시간복잡도를 가진다.
• 주로 검색이 많이 필요하거나, 데이터 저장, 삭제 등이 빈번한 경우 사용한다.
• 장점 : 데이터 저장/읽기 속도가 빠르고, 키에 대한 데이터가 있는지(중복 확인) 확인이 쉽다.
• 단점 : 저장 공간이 많이 필요하고, 여러 키에 해당하는 주소가 동일할 경우 해쉬 충돌이 발생할 수 있다.

https://media.geeksforgeeks.org/wp-content/cdn-uploads/20221220111537/ComponentsofHashing.png

 

2.  정렬(Sort)

• 파이썬에는 크게 리스트 객체 메소드인 .sort()와 자체 함수인 sorted() 정렬 방식이 있다.
• 파이썬 정렬 라이브러리는 병합정렬 기반으로 작성되었으며, 시간복잡도는 O(NlogN)이다.
• 파이썬 내장함수 sorted()는 이터러블(iterable) 객체를 받아 정렬된 리스트를 생성한다.
• sort()는 파이썬 리스트 객체의 내장함수로 별도의 반환 값 없이 내부원소를 바로 정렬한다.
• 정렬의 기본 값은 오름차순이며, reverse 매개변수를 통해 반대되는 내림차순으로 정렬할 수 있다.
• key 매개변수와 lambda 식을 이용해 특정한 데이터를 기준으로 정렬 순서를 설정할 수 있다.

a = sorted([2, 1, 4, 6, 5])
print(a)
>>> [1, 2, 4, 5, 6]

b = sorted({'a': 1, 'c': 2, 'b': 0}) # 딕셔너리도 이터너블한 객체이기 때문에 sorted 사용가능
print(b)
>>> ['a', 'b', 'c'] # 반면 리턴 결과는 항상 리스트 객체로 반환


c = [2, 5, 1, 10, 8]

c.sort() # 기본 정렬 순서는 오름차순
print(c)
>>> [1, 2, 5, 8, 10]

c.sort(reverse=True) # 내림차순으로 정렬을 원할 때는 reverser 매개변수를 True로 설정
print(c)
>>> [10, 8, 5, 2, 1]

d = [('강은미', '정의당'), ('노웅래', '더불어민주당'), ('박수영', '국민의힘')]

e = sorted(d, key=lambda x: x[0]) # 첫번째 이름을 기준으로 오름차순 정렬
print(e)
>>> [('강은미', '정의당'), ('노웅래', '더불어민주당'), ('박수영', '국민의힘')]

f = sorted(d, key=lambda x: x[1]) # 두번째 정당명을 기준으로 오름차순 정렬
print(f)
>>> [('박수영', '국민의힘'), ('노웅래', '더불어민주당'), ('강은미', '정의당')]