위코드 부트캠프에서 진행한 세션 중 일부를 요약한 내용입니다.
자료구조란 데이터에 편리하게 접근하고, 변경하기 위해서 데이터를 저장하거나 조직하는 방법을 말합니다. 모든 목적에 맞는 자료구조는 없기 때문에 각 자료구조의 특성을 잘 파악하고 사용할 수 있어야 합니다.
자료구조를 통해 메모리의 물리적 공간에 대해 알게 됐는데 앞으로 더 깊게 공부해보고 싶은 분야입니다.
자료구조 종류
- Primitive
- integer
- float
- string
- boolean
- Non-primitive
- array
- list
- tuple
- dictionary
- set
- file
1. Array
특징
- 메모리에 순서대로 저장
- 수정 가능
- 동일값 삽입 가능
- 순서가 있어서 indexing 가능
- multi dimentional array 가능. array 안 array
단점
메모리상에서 항상 연속되어야 하기 때문에 예상보다 요소 숫자가 많아지만 resizing 필요
언제
- 순차적 데이터
- 특정 요소를 빠르게 읽어야 할 때
- 데이터 사이즈가 자주 변하지 않을 때
- 요소를 자주 삭제해야 하지 않을 때
속도
linked list
물리적 리사이징 제약을 없애기 위한 array
2. Tuple
특징
- 순차적 저장 가능
- 수정 불가능
- 2,3개 소규모 데이터 저장시
- 함수에서 리턴 값 한개 이상 리턴할 때 사용
3. Set
특징
- 순서가 없음
- 수정 가능
- 중복값 저장 안함
- 해시함수를 이용해 메모리에 저장
- 같은 값이 해시함수를 통해 같은 값이 나오기 때문에 중복이 안됨
- set는 사실 리스트 기반이며 리스트로 할당된 메모리에 해쉬값의 나머지 값을 할당해 지정
- 파이썬의 경우는 해쉬값 자리수를 끊어서 해쉬충돌 여부를 파악하고 지정
- 해쉬 후 치환해서 저장하는 이유는 다른 메모리값일 경우 다른 값으로 인식할 경우도 있기 때문
- 클래스의 최상의 object클래스에 eq함수 디폴트값에 정해져 있음
속도
4. Dictionary
특징
- 키밸류 형식
- 중복키 허용 안함
- 키를 해시로 저장
5. stack
6. queue
- 선입선출
- 맛집 예약
- 우선순위가 있는 priority queue도 존재(os 스케줄링)
7. Tree
- 탐색 속도가 빠름
- 숫자가 아닐 경우 비교 기준을 만들어놔야 함
속도