민제 | Notion

자료 구조

대량의 데이터를 효율적으로 관리할 수 있도록 하는 데이터 구조를 말한다.
데이터 특성에 따라 체계적인 데이터 구조화가 필요하며, 이러한 데이터 구조는 코드의 효율성, 성능을 결정한다.

Python의 대표적인 자료구조

List
- 배열과 같은 종류로 데이터를 순차적으로 저장하는 자료구조이다.
- LIFO(Last-In, First-Out) 방식이며 stack 자료구조에서는 최대갯수를 사전에 정의해줘야해서 저장 공간의 낭비가 있을 수도 있다는 단점 때문에 python에서는 리스트로 대체하여 자주 사용한다.
- index를 통해 직접 접근이 가능하다.
- 하나의 리스트에 여러 데이터 변수형을 넣을 수 있다
- 장점 : 빠른 접근이 가능하다.
- 단점 : 데이터 추가와 삭제에 비용이 많이 사용된다. 데이터 추가시 공간이 많이 필요하며 삭제 시 빈공간이 생겨 이를 관리해주어야한다.
deque
- LILO(Last-In, Last-Out) 방식으로 queue 자료구조와 같은 종류의 자료구조이다.
- queue 자료 구조는 단순히 put과 get으로 넣고 먼저 들어온 데이터를 빼주는 기능만을 하는 것과는 달리 deque은 stack처럼 LIFO 방식도 구현할 수 있고 queue처럼 LILO 방식도 구현할 수 있기 때문에 deque과 queue보다 유용하게 사용할 수 있다.
- 멀티쓰레드 환경을 지원하여 느린 queue보다 명령들을 O(1)로 처리해주는 deque이 더 빠르므로 데이터의 삽입과 삭제 등의 연산을 할 때에는 deque을 쓰는 것이 효율적이다.
- deque은 이중 연결 리스트로 삽입과 삭제 연산이 O(1)이라는 장점이 있지만 이중연결 리스트이므로 인덱스로 접근할 수 없고 앞에서부터 순차적으로 접근해야하기 때문에 O(N)이 걸린다는 단점과 데이터 하나당 링크를 2개 사용하기 때문에 메모리를 2배로 사용한다는 단점이 있다.
- 장점 : 데이터의 삽입과 삭제가 빠르다.
- 단점 : list보다 메모리를 2배 사용하고 인덱스로 접근이 오래 걸린다.
dictionary
- dictionary는 key와 value의 한 쌍으로 이루어진 사전 자료구조이다.
- dictionary 자료구조는 순서가 없기 때문에 인덱싱을 지원하지 않고 key값으로 value값에 접근한다.
- 이런 key를 통해 value에 접근하는 방식 때문에 key는 중복을 허용하지 않고 key가 중복되면 한개를 제외한 나머지는 무시된다.
- dictionary의 in 함수는 true와 false를 반환한다.
set
- set은 집합 자료구조라고 한다.
- set 자료구조는 중복을 허용하지 않고 순서가 없다는 특징이 있다.
- 순서가 없기 때문에 인덱싱을 지원하지 않고 dictionary 자료구조처럼 key 값으로 value값에 접근한다.
- set자료구조는 교집합, 합집합, 차집합을 구할 때 유용하게 사용할 수 있다.
```
s1=set(1,2,3,4)
s2=set(3,4,5,6)
```
  - 교집합
```
print(s1&s2)
//3,4
print(s1.intersection(s2))
//3,4
```
  - 합집합
```
print(s1|s2)
//1,2,3,4,5,6
print(s1.union(s2))
//1,2,3,4,5,6
```
  - 차집합
```
print(s1-s2)
//1,2
print(s1.difference(s2))
//1,2
```
- set 자료구조는 안의 값을 찾을 때도 유용하다. list는 in을 통해 안의 값을 찾는데 O(N)의 시간이 걸리지만 set은 순서가 없기 때문에 O(1)의 시간으로 값을 찾을 수 있다.