📗자료구조

📌 자료구조란 데이터를 효율적으로 관리할 수 있는 데이터의 구조를 말한다.

다양한 자료구조를 통해 데이터를 관리할 수 있으며 상황에 따라 효율적인 자료구조가 존재한다. 그 중에서도 가장 기본적인 배열, 큐, 스택에 대해서 정리해보고자 한다. 배열, 큐, 스택은 선형자료구조이다(선형 자료구조는 연결리스트, deque도 포함한다). 말그대로 데이터를 순서대로 나열한 형태이며 하나의 자료 뒤에는 하나의 자료가 존재한다.

📚배열(Array)

📝특징

✔️장점

논리적 저장 순서와 물리적 저장 순서가 같다.

(A = start_address, B= element_size라고 하자)
-> 우리가 1, 2, 3, 4, 5라는 순서로 데이터를 나열했을 때, 컴퓨터 메모리 또한 A, A+B, A+2B로, 연속된 메모리 공간에 순차적으로 저장되기 때문에 O(1)의 속도로 메모리에 저장된 모든 데이터에 접근이 가능하다.(Random Access)

시작주소 + 오프셋(자료형의 크기 * 인덱스)로 값을 조회할 수 있다.

배열 0번째: 1000 + (4 * 0)

배열 1번째: 1000 + (4 * 1)

배열 2번째: 1000 + (4 * 2)

(정수형 자료형인 int형은 4byte로 char배열은 1, double형은 8씩 주소가 증가한다)

❌단점

하지만 삽입,삭제에서 데이터의 이동이 잦다. 메모리의 연속성을 지켜줘야하기 때문에 해당 원소 이후의 원소를 이동시켜주어야 할 때, 시간 복잡도가 O(n)이 된다.

내가 사용할 배열 크기를 미리 파악한다는 것은 쉬운 일이 아니다. 초기 배열 크기를 지정할 때 저장공간이 낭비 될 수 있고 이를 변경할 수 없다.

📌파이썬에서는..

파이썬에서는 동적배열인 list를 사용해 배열의 크기를 자유롭게 확장할 수 있다. 하지만 내부적으로는 정적배열을 사용하고 있기 때문에 기존의 배열이 크기가 작아서 더 큰배열이 필요하다면 2배 더 큰 크기의 배열을 할당하고 기존 배열의 데이터를 더 큰 크기의 배열에 복사(O(n))한다. 그리고 가장 마지막에 데이터를 추가한다(O(1))

📚큐(Queue)

📝특징

롯데월드나 에버랜드 혹은 서울랜드 등을 가본적이 있다면 놀이기구를 타기 위해 기다려본 경험이 있을 것이다.

큐는 선입선출 자료구조(FIFO(First In First Out))로써 먼저 줄을 선 사람이 먼저 놀이기구를 타는것이다! 그리고 안전을 위해 입장하는 장소에서만 입장할 수 있고 퇴장하는 장소에서만 퇴장할 수 있다. 큐도 이와 다른점이 없다. 가장 앞부분(front/head)에서는 데이터의 삽입만 이루어지고 가장 마지막부분(rear/tail)에서는 삭제만 이루어진다.

스택과 큐는 추상 자료형이기 때문에 정해진 구현방식은 없고 연결리스트나 배열 모두 사용가능하다. 하지만 일종의 규약을 제공하기 때문에 이것을 지켜주여야 비로소 큐(Queue)라고 구분될 수 있다. 대략적으로 다음과 같다.

push(): 큐의의 마지막(rear/tail)에 값을 삽입한다.
pop(): 큐의 front에 있는 값을 반환하고, 삭제한다.
queueSize(): 큐의 사이즈를 반환한다.
isFull(): 큐가 가득 차 있는지 유무를 반환한다.
isEmpty(): 큐가 비어있는지 유무를 반환한다.
front(): 큐의 front에 있는 값을 반환한다.
rear(): 큐의 rear에 있는 값을 반환한다.

📌파이썬에서는

파이썬에서는 list, 큐(Queue) 라이브러리를 사용하는방법, collections 모듈의 deque를 사용하는 방법이 있다. 간단하게 list로 구현하는 방법을 살펴보자.

✏️큐(Queue) 구현

queue = [1, 2, 3, 4, 5] #front 1, rear 5
queue.append(7)
queue.append(8)

print(queue)

queue.pop(0) #0번째 요소 삭제
queue.pop(0) #0번째 요소 삭제

print(queue)

출력결과
[1, 2, 3, 4, 5, 7, 8]
[3, 4, 5, 7, 8]

queue = [3, 4, 5] # front 5 rear 3
queue.insert(0, 2) #0번째에 2라는 요소 삽입
queue.insert(0, 1) #0번째에 1이라는 요소 삽입

print(queue)

queue.pop()
queue.pop()

print(queue)

출력결과
[1, 2, 3, 4, 5]
[1, 2, 3]

하지만 추천하지 않는다.

파이썬의 list를 사용한다는 것은 앞서 살펴본 다른언어의 배열을 사용하는 것과 비슷하다. 따라서 인덱스를 통한 조회가 아닌 값의 삽입, 삭제는 불리할 수 밖에 없다.

그중에서도 insert(0, x) pop(0)는 맨앞에서 insert를 했을때 모든 데이터를 밀어줘야하고 맨 앞에서 pop을 했을 때 모든 데이터를 한칸씩 당겨주어야한다. 성능적으로 손해를 볼 수밖에 없고, 코딩테스트에서는 더욱 취약하다. 동적배열인 리스트는 내부적으로는 정적배열 구조를 띄고있고 배열크기가 부족할때마다 기존 크기의 2배 크기의 배열을 만들고 복사한 다음 push를 해주기 때문에 이 경우가 가장 오래 걸리는 작업이 될 것이다.

따라서 파이썬의 deque사용을 추천하는데 데이터를 양방향으로 삽입하거나 삭제할 수 있다. 사기다

안전을 위해 입장하는 장소에서만 입장할 수 있고 퇴장하는 장소에서만 퇴장할 수 있었던 규제를 해제해줬다.

from collections import deque

dq = deque([1,2,3]) # front 1 rear 3
dq.append(4)
dq.append(5)

print(dq)

dq.popleft()
dq.popleft()

print(dq)

출력결과

deque([1, 2, 3, 4, 5])
deque([3, 4, 5])

❌단점
하지만 deque도 단점이 존재한다. 내부적으로는 linked list를 사용하기 때문에 삽입/삭제에서는 유용하나 i번째 데이터에 접근하는 것은 배열과 달리 i번의 순회가 필요하기 때문에 O(n)의 시간복잡도를 갖는다.

📚스택(Stack)

📝특징

스택 예시는 쌓여있는 접시로 설명이 가능하다. 가장 아래에서 꺼내는 미친놈은 없을것이다. 쌓여있는 접시를 세척할 때 가장 위에있는 접시부터 차곡차곡 세척한다. LIFO(Last in First out)) 자료구조이다.

스택도 큐와 마찬가지로 추상 자료형이기 때문에 정해진 구현방식은 없고 연결리스트나 배열 모두 사용가능하다. 기능은 다음과 같다.

push(): 스택의 가장 윗 부분의 값을 추가한다.
pop(): 스택의 가장 윗부분의 값을 반환하고 제거한다.
stackSize(): 스택의 사이즈를 반환한다.
top(): 스택의 가장 위에 있는 항목을 반환한다.
isFull(): 스택이 가득 차 있는지 유무를 반환한다.
isEmpty(): 스택이 비어있는지 유무를 반환한다.

✏️스택(Stack) 구현

이중연결리스트로 되어있는 collections 모듈의 deque를 사용하여 Stack을 구현해보자.

from collections import deque

dq = deque([1,2,3])
dq.append(4)
dq.append(5)
dq.pop()
dq.pop()

print(dq)

출력결과
deque([1, 2, 3])

✔️장점
비교적 구조가 단순하여 구현하기가 쉽다.
삽입과 삭제시에 O(1)이다.

❌단점
탐색에는 O(n) 비용이 든다.

🔎 참고

출처 https://questionet.tistory.com/36,
https://webcache.googleusercontent.com/search?q=cache:BUicik02Sp4J:https://cocodding0723.github.io/datastructure/02_array-post/&cd=5&hl=ko&ct=clnk&gl=kr, https://www.daleseo.com/python-queue/