하루 10분 공부하기 자료구조

새해를 맞이하여 하루 10분 공부하기를 시작하려고 합니다.

오늘은 우선 자료구조부터 시작하려고 합니다.

사실 자료구조는 전공진입한 2학년 때 바로 배웠던 과목이긴 하죠.

그래도 그 때 안 배우고 지나갔던 것과 소홀하게 했던 것을 짚고 넘어가려고 합니다.

우선 기본적으로 배우는 자료구조에는 연결 리스트, 스택, 큐, 트리, 우선순위 큐, 힙 정도가 있습니다.

그리고 추가적으로 균형잡힌 이진탐색트리, 해쉬 테이블, 그래프가 있습니다.

우선순위 큐와 힙

우선순위 큐와 큐이면서 데이터의 저장방식이 우선순위대로 저장되어 데이터를 꺼낼 때 우선순위가 높은 데이터를 먼저 꺼낼 수 있도록 합니다.

힙은 우선 완전 이진트리의 형태를 띄고 있습니다. 

완전 이진트리는 노드의 값이 자식의 값보다 항상 크거나 같은 이진 트리를 말합니다 ( Max Heap )

균형 잡힌 이진 탐색 트리

균형 잡힌 이진 탐색 트리를 만들기 전에 트리에 균형 인수를 도입하여 트리가 얼마나 균형 잡혔는지 확인할 수 있습니다.

균형 인수 = 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이

균형을 맞추는 방법에는 4가지가 있습니다.

- LL회전

- RR회전

- LR회전

- RL회전

해쉬 테이블

데이터의 탐색이 주로 필요한 환경에서 자주 사용되는 해쉬 테이블은 키 값으로 바로 데이터를 찾을 수 있다는 장점이 있습니다.

그리고 그 키 값을 실제로 참조할 수 있는 해쉬 값으로 바꾸는 것이 해쉬 함수입니다.

좋은 해쉬 함수라는 것은 해쉬 값이 고르게 나오는 함수입니다.

그런데 해쉬 값이 고르게 나오기 위해서는 키 값을 일부만 사용하도록 하기도 합니다.

예를 들어 데이터들의 키 값들이 Alpha-1523, Alpha-5261, Alpha-9281 ... 식이라고 한다면 

중복되는 Alpha- 영역을 제외한 나머지를 이용하는 것이 효율적일 수 있습니다.

이러한 방법은 자릿수 선택 방법이라고 합니다.

다른 방법으로는 자릿수 폴딩 방법이 있는데

예를 들어 데이터의 키 값이 596214 이라고 하면

두자리씩 겹치게 하여 59 + 62 + 14 = 135 를 해쉬 값으로 쓰는 방법이 있습니다.

그래프

그래프는 정점과 간선이 있는 형태의 데이터를 표현하기 좋다.

그래프는 인접행렬이나 인접 리스트로 표현할 수 있다.

각각 정방 행렬과 연결 리스트를 활용한다.