자료구조 기초

위코드 부트캠프에서 진행한 세션 중 일부를 요약한 내용입니다.

 

자료구조란 데이터에 편리하게 접근하고, 변경하기 위해서 데이터를 저장하거나 조직하는 방법을 말합니다. 모든 목적에 맞는 자료구조는 없기 때문에 각 자료구조의 특성을 잘 파악하고 사용할 수 있어야 합니다.

자료구조를 통해 메모리의 물리적 공간에 대해 알게 됐는데 앞으로 더 깊게 공부해보고 싶은 분야입니다.

자료구조 종류

• Primitive
  - integer
  - float
  - string
  - boolean
• Non-primitive
  - array
  - list
  - tuple
  - dictionary
  - set
  - file
  

 

1. Array

특징

• 메모리에 순서대로 저장
• 수정 가능
• 동일값 삽입 가능
• 순서가 있어서 indexing 가능
• multi dimentional array 가능. array 안 array

단점

메모리상에서 항상 연속되어야 하기 때문에 예상보다 요소 숫자가 많아지만 resizing 필요

언제

• 순차적 데이터
• 특정 요소를 빠르게 읽어야 할 때
• 데이터 사이즈가 자주 변하지 않을 때
• 요소를 자주 삭제해야 하지 않을 때

속도

• O(N)
  최대 배열개수만큼 필요

linked list

물리적 리사이징 제약을 없애기 위한 array

 

2. Tuple

특징

• 순차적 저장 가능
• 수정 불가능
• 2,3개 소규모 데이터 저장시
• 함수에서 리턴 값 한개 이상 리턴할 때 사용

 

3. Set

특징

• 순서가 없음
• 수정 가능
• 중복값 저장 안함
• 해시함수를 이용해 메모리에 저장
• 같은 값이 해시함수를 통해 같은 값이 나오기 때문에 중복이 안됨
  - set는 사실 리스트 기반이며 리스트로 할당된 메모리에 해쉬값의 나머지 값을 할당해 지정
  - 파이썬의 경우는 해쉬값 자리수를 끊어서 해쉬충돌 여부를 파악하고 지정
• 해쉬 후 치환해서 저장하는 이유는 다른 메모리값일 경우 다른 값으로 인식할 경우도 있기 때문
• 클래스의 최상의 object클래스에 eq함수 디폴트값에 정해져 있음

속도

• O(1)
  항상 동일한 속도 constant

 

4. Dictionary

특징

• 키밸류 형식
• 중복키 허용 안함
• 키를 해시로 저장

 

5. stack

• 후입선출
• 함수호출시
• 브라우저 뒤로가기

 

6. queue

• 선입선출
• 맛집 예약
• 우선순위가 있는 priority queue도 존재(os 스케줄링)

 

7. Tree

• 탐색 속도가 빠름
• 숫자가 아닐 경우 비교 기준을 만들어놔야 함

속도

• O(logN)