정리 - 자료 구조

자료 구조는 코드의 성능과 밀접

코드 성능을 어떻게 수치화 할 것인지

시간 복잡도와 공간 복잡도를 고려해야함

 

주요 자료 구조

배열과 연결리스트

스택과 큐

해시 테이블

트리

- 계층형 데이터

그래프

 

정렬 알고리즘

힙

• 최대값 혹인 최소값을 빠르게 찾기 위한 이진트리
• 최소 힙인 경우에는 부모는 자식보다 작고, 최대 힙인 경우에는 부모는 자식보다 크다
• 높이 만큼의 시간 복잡도 O(logN)

이진탐색 트리

• 왼쪽자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 이진 트리
• 한쪽으로 편형될 수 있음 (N)
• 시간 복잡도는 O(logN ~ N)

자가 균형 트리

• 편향되지 않게 삽입, 삭제를 개선한 이진 탐색 트리
• 이진 탐색 트리는 시간 복잡도가 트리의 높이에 따라 결정되므로 편향될 경우 효율이 떨어짐
• 그래서 편향되지 않게 삽입과 삭제를 개선한 이진 탐색 트리를 자가균형 트리라고 함

해시

• 해시에 매핑하여 데이터를 저장하는 자료구조
• key는 해시 함수를 통해 hash로 변경된 다음에 value와 매핑되어서 bucket에 저장되게 됨
• 시간복잡도는 삽입, 삭제, 조회가 모두 O(1)의 시간복잡도를 가짐

해시 충돌 회피 방법

1. Open Addressing
   • 다른 해시 값에 저장
2. Chaining
   • 해쉬 테이블이 원소 하나를 담는게 아니라 Linked List를 담음