'22.08.03 Today I Learned

<학습내용>

- 알고리즘 & 자료구조

 

---

 

1. 알고리즘 & 자료구조

 

오늘도 역시나 기본 알고리즘고 자료구조에 대해서 배웠다. 역시 어렵다.

 

 

> 해쉬

 

해쉬테이블은 파이썬 기본 데이터타입 중 하나인 딕셔너리와 비슷하다. key와 value 한 쌍을 저장한다. key 값만 알아도 value를 알 수 있기 때문에 데이터를 조회할 때 속도가 아주 빠르다. 그런데 해쉬 테이블도 내부적으로는 배열을 이용하고 있다. 

 

해쉬 테이블을 사용할 때 hash함수를 이용한다. 이것은 특정 문자열을 특정 숫자로 바꿔주는 역할을 하는 함수이다. 해쉬함수를 이용해서 얻은 숫자를 배열의 길이로 나눠주고 나온 나머지를 인덱스로 하여 배열에 저장해주면 된다.

 

그런데 만약 인덱스가 중복해서 나온다면 어떡해야될까? 이렇게 인덱스가 중복해서 나오는 경우를 충돌한다는 표현을 쓰는데 이럴 때는 링크드 리스트를 이용해서 각 인덱스에 (key, value) 쌍을 저장해주면 된다.

 

 

 

> 트리

 

큐, 스택 등이 선형구조인 것에 비해 트리는 비선형구조이다. 트리를 사용하는 가장 주요한 이유는 자료를의 표현이다. 트리는 일반적으로 계층을 띄고 있다.

 

 

트리의 종류에는 다양하게 있는데 오늘 배운 것은 이진트리와 완전 이진트리였다. 이진트리는 각 노드가 최대 두 개의 자식 노드를 가질 수 있다는 것이다. 하나의 노드가 자식 노드를 0, 1, 2개까지 가질 수 있다는 것이다. 완전 이진트리는 이진트리 중에서도 모든 노드가 왼쪽부터 채워져있는 트리를 의미한다. 

 

 

 

> 힙

 

최대값 혹은 최소값을 빠르게 찾기 위해 만든 완전트리의 한 종류. max 힙은 맨 루트 노드부터 아래로 갈수록 숫자가 작아진다. 이 규칙은 모든 노드에 적용된다. min 힙은 반대이다.