[8일차 과제] 자료구조(배열, 스택, 큐)
2026. 5. 31. 23:12ㆍKDT/과제
# 자료구조
- 대량의 데이터를 효율적으로 관리할 수 있도록 하는 데이터 구조
# 배열 Array
1. 설명 및 장단점
- 같은 종류의 데이터를 순차적으로 저장하는 자료구조
ex. 전화번호부. 연락처. 소셜 미디어 타임라인. 학생 성적 관리. 화면 픽셀 데이터. 체스/바둑판 및 맵 구조. CPU의 순차 자료구조 - 연속된 메모리 공간에 순차적으로 데이터 저장 (선형 구조)
- index로 직접 접근 가능
- 배열 생성 시 크기 지정하면 크기가 고정됨
- 시간 복잡도 :
- 삽입 : 최선(=배열 맨끝) O(1)
최악/평균(=맨 처음 또는 중간) O(N) -> 중간에 삽입하려면 해당 위치 뒤에 있는 모든 요소를 한 칸씩 뒤로 밀어야하므로 데이터 수만큼 연산 발생 - 삭제 : 최선(=배열 맨끝) O(1)
최악/평균(=맨 처음 또는 중간) O(N) -> 데이터를 삭제한 후 빈 공간을 메우기 위해 뒤 요소들을 한 칸씩 앞으로 당겨야 하므로 시간 소요 - 검색(Search) : O(N) -> 인덱스를 모르고 찾는 경우, 배열의 처음부터 끝까지 순차적으로 확인이 필요하므로 데이터 수(N)에 비례
- 접근(Access) : O(1) -> 배열 크기와 상관 없이 인덱스로 메모리 주소 즉시 접근하므로 일정한 시간 소요
- 삽입 : 최선(=배열 맨끝) O(1)
- 장점 : 인덱스를 통한 빠른 접근
- 단점 :
- 고정된 크기를 가지므로 필요보다 큰 배열 생성 시 메모리 낭비
- 데이터 삽입/삭제 시 비효율성
2. 구현
# 배열 구현하기
class Array:
def __init__(self, size):
self.arr = [None] * size # 배열 생성 시 size 만큼 None으로 초기화 (배열의 고정 크기)
self.length = 0 # 배열의 길이
# 데이터 추가
def insert(self, idx, value):
if idx < 0 or idx > self.length: # 인덱스가 0보다 작거나, 배열 길이 보다 큰 경우에 에러 발생
raise IndexError("Invalid Index")
if self.length >= len(self.arr): # 배열이 꽉 찬 경우, 에러 발생
raise Exception("Array is Full")
for i in range(self.length, idx, -1):
self.arr[i] = self.arr[i - 1] # 중간 데이터 삽입 시 뒤 원소들을 한 칸씩 미룬 후
self.arr[idx] = value # 해당 인덱스에 해당 데이터를 삽입 (데이터 추가)
self.length += 1 # 데이터가 들어왔으니 길이를 1 늘려줌
# 데이터 삭제
def delete(self, idx):
if idx < 0 or idx >= self.length: # 인덱스가 0보다 작거나, 배열 길이 보다 큰 경우에 에러 발생
raise IndexError("Invalid Index")
for i in range(idx, self.length - 1):
self.arr[i] = self.arr[i + 1] # 중간 데이터 삭제 시 뒤 원소들을 한 칸씩 앞으로 당긴 후
self.arr[self.length - 1] = None # 마지막 데이터는 None으로 변경
self.length -= 1 # 데이터가 삭제되었으니 길이를 1 줄여줌
# 데이터 조회
def get(self, idx):
if idx < 0 or idx >= self.length: # 인덱스가 0보다 작거나, 배열 길이 보다 큰 경우에 에러 발생
raise IndexError("Invalid Index")
return self.arr[idx]# 스택 Stack
1. 설명 및 장단점
- stack = 쌓다
- 데이터를 쌓아 올리며 관리하는 후입 선출 LIFO (Last In First Out) 원칙을 따르는 자료 구조
-> 한 쪽 끝(Top)에서만 데이터 삽입/삭제 가능
ex. 쌓여있는 접시. 브라우저의 뒤로가기 기능. 실행취소(Undo). 수식 계산 및 괄호 검사. 역순 문자열 만들기. 프로그램 함수 호출(Call Stack). 재귀 함수. DFS(깊이 우선 탐색). - 데이터를 일시적으로 저장하기 위해 사용하는 자료 구조
- 스택의 실제 메모리 동작은 배열 기반 또는 연결리스트 기반으로 구현
- 스택의 연산 :
- push(x) : 스택에 데이터 x를 추가
- pop() : 스택의 맨 위 데이터 제거, 반환
- size() : 스택에 있는 데이터 개수 반환
- isEmpty() : 스택이 비어 있는지 판단 (True or False)
- peek() : 스택 맨 위 데이터 반환
- Top : 스택의 삽입/삭제가 일어나는 지점
- 시간 복잡도 :
- 삽입 : O(1) -> 맨 위에 데이터 추가만 하면 됨
- 삭제 : O(1) -> 맨 위에 데이터 삭제만 하면 됨
- 검색(Search) : O(N) -> 맨 위부터 아래로 순차 탐색 해야하므로 스택의 크기(N)에 비례하는 시간이 걸림
- Peek(Top) : O(1) -> 데이터 변경 없이 맨 위의 값을 읽기만 하면 됨
- 장점 :
- 빠른 데이터 처리 (Top에서만 데이터 삽입/삭제가 일어남)
- 구조가 단순해서 간단하게 구현이 가능
- 데이터 역추적 용이 (이전 상태로 돌아가는 작업에 직관적으로 활용 가능)
- 단점 :
- 제한적인 접근 (Top에서만 데이터 삽입/삭제가 일어나므로 중간에 있는 데이터를 검색하거나 수정하기 어려움)
- 메모리 낭비 (배열로 구현 시 최대 크기를 미리 정해야 하므로 배열과 마찬가지로 메모리 낭비 발생 가능성 존재)
- 크기 변경의 한계 (고정된 크기를 초과하여 데이터를 넣으려고 하면 overflow 발생 가능성 존재)
2. 구현
class Stack1:
def __init__(self, size=10000): # 스택 크기의 기본값을 10000으로 세팅
self.arr = [None] * size # 스택 size 만큼 값들을 None으로 초기화
self.idx = 0 # 가장 마지막 값이 있는 인덱스 + 1 (즉, 스택의 크기)
def push(self, value):
# stack overflow 처리
if self.idx >= len(self.arr): # push가 계속되었을 때 stack의 크기보다 더 많은 데이터가 들어오면
raise Exception("Stack Overflow") # 에러 발생
self.arr[self.idx] = value # 매개변수로 받아온 value 데이터를 스택에 넣음
self.idx += 1 # 데이터가 들어온 다음 인덱스로 옮겨줌
def pop(self):
# 뒤(위)에서 뽑기 (LIFO 구조이기 때문)
if self.idx == 0: # idx가 0이 되었을 때 -1 연산을 하게 되면 리턴 값이 arr[-1]이 되는데,
# 이는 파이썬에서 가장 마지막 요소를 가리키기 때문에 에러 발생
raise Exception("Stack is empty")
# return None # 에러 말고 None을 리턴 시킬 수도 있음 (프로그램 종료되지 않도록)
self.idx -= 1 # 가장 마지막 데이터를 가리키도록 idx-1
value = self.arr[self.idx] # 그 요소를 변수에 저장한 후
self.arr[self.idx] = None # pop한 요소를 None으로 설정 (스택에서 값 제거)
return value # value에 저장했던 요소 리턴
def isEmpty(self):
if self.idx == 0: # idx가 0이면 비어있는 것이 맞으니까 True 리턴
return True
else: # 아니면 False 리턴
return False
def size(self):
return self.idx # 스택 크기 리턴
def peek(self):
if self.idx == 0: # idx가 0이면 스택이 비었다는 에러 발생
raise Exception("Stack is empty")
return self.arr[self.idx - 1] # 아니면 가장 마지막 데이터 리턴# 큐 Queue
1. 설명 및 장단점
- 데이터를 일렬로 나열한 후, 처음 들어온 데이터가 처음 나가는 선입선출 FIFO (First In First Out) 원칙을 따르는 자료구조
-> 뒤(Rear)에서 삽입되고, 앞(Front)에서 삭제
ex. 줄서기. 프린트 출력 대기. 온라인 게임 서버 대기열. 웹 서버 요청 처리. 동영상 버퍼링. BFS(너비우선탐색). 캐시(Cache) 구현. 네트워크 패킷 처리 - 큐의 실제 메모리 동작은 배열 기반 또는 연결리스트 기반으로 구현
- 큐의 연산 :
- enqueue() : 큐의 끝(rear)에 항목 추가
- dequeue() : 큐의 맨 앞(front)의 항목 삭제
- isfull() : 큐가 가득 찼는지 확인
- isempty() : 큐가 비어 있는지 확인
- peek() : 큐의 맨 앞(front)에 있는 항목 반환
- 시간 복잡도 :
- 삽입 : O(1) -> rear에 데이터 추가
- 삭제 : O(1) -> front에서 데이터 삭제
선형 큐 : O(N) -> 배열 사용하므로 삭제 시 데이터를 앞으로 한 칸씩 당겨야함
원형 큐 : O(1) -> 시작점과 끝점을 이동시킴 - 검색(Search) : O(N) -> 큐 내부의 순차 탐색을 통해 특정 데이터 찾음
- peek(front) : O(1) -> 맨 앞 원소(front)만 확인하므로 즉시 접근 가능
* 우선 순위 큐 : 삽입 삭제 시 O(log N)
-> 들어온 순서가 아닌 데이터의 우선 순위에 따라 처리.
삽입 삭제 시 정렬 과정이 포함되어 일반 큐와 다른 시간 복잡도를 가짐
- 장점 :
- 빠른 데이터 처리 (삽입/삭제가 rear/front에서 이루어짐)
- 데이터 일관성 (입력된 순서대로 데이터 처리)
- 단점 : 제한적인 데이터 접근 (큐 중간에 있는 데이터에 대한 임의 접근이 어려움)
2. 구현
# Linearqueue 구현하기 (선형 큐)
class LinearQueue:
def __init__(self, size):
self.arr = [None] * size # size만큼 배열 생성
self.front = 0 # 삭제가 이루어지는 front
self.rear = 0 # 삽입이 이루어지는 rear
self.size = size # 큐의 크기
# 데이터 삽입
def enqueue(self, value):
if self.isFull(): # 큐가 꽉 찼으면 에러 발생 (더 이상 삽입 불가능)
raise Exception("Queue is Full")
self.arr[self.rear] = value # 맨 뒤에 데이터 삽입
self.rear += 1 # 맨 뒤를 가리키는 인덱스인 rear에 1 추가
# 데이터 삭제
def dequeue(self):
if self.isEmpty():
raise Exception("Queue is Empty") # 큐가 비어있으면 에러 발생 (더 이상 삭제 불가능)
value = self.arr[self.front] # 삭제할 데이터를 value에 저장해두고
self.arr[self.front] = None # 배열에서 데이터를 삭제0
self.front += 1 # 맨 앞의 데이터가 비었으니 뒤로 한 칸 이동
return value # 저장해둔 데이터 리턴
# 맨 앞 데이터 조회
def peek(self):
if self.isEmpty():
raise Exception("Queue is Empty") # 큐가 비어있으면 에러 발생 (데이터 조회 불가능)
return self.arr[self.front] # 맨 앞 데이터 리턴
# 큐가 비어있는지
def isEmpty(self):
return self.front == self.rear # 맨 앞과 뒤를 가리키는 변수가 같은 값이면 비었음
# 큐가 꽉 찼는지
def isFull(self):
return self.rear == self.size # 큐의 크기와 맨 뒤를 가리키는 변수가 같으면 꽉 찼음
3. "선형 큐 / 원형 큐 / 연결리스트 기반 큐"
- 선형 큐 : 배열로 구현
- 원형 큐 : 선형 큐의 문제를 해결. 배열 끝에 도달하면 다시 처음으로 돌아감. (원처럼 front와 rear가 연결되어 있음)
- 연결리스트 기반 큐 : 데이터와 포인터를 이용
# 배열, 스택, 큐의 차이점
1. 시간 복잡도
- 시간복잡도면에서 위에 조사한 차이점을 가진다
2. 특징
| 배열 | 스택 | 큐 | |
| 접근 | 임의 접근 가능 | Top만 접근 | 임의 접근 어려움 |
| 구조 | 일반 저장 | LIFO | FIFO |
| 삽입 위치 | 어디든 가능 | Top만 | Rear |
| 삭제 위치 | 어디든 가능 | Top만 | Front |
- 배열과 파이썬리스트는 완전히 같은 개념? : False!
- 파이썬의 List 자료형도 Array처럼 index로 원소에 접근 가능하지만
서로 다른 자료형을 원소로 가질 수 있고
동적 배열로써 크기 조절이 자유롭다
리스트 안의 원소들은 값들을 자유롭게 변경도 가능
- 파이썬의 List 자료형도 Array처럼 index로 원소에 접근 가능하지만
- 스택은 왜 후입선출 구조 사용? :
- 가장 최근에 사용한 데이터를 가장 먼저 처리해야하는 상황에 효율적으로 해결할 수 있기 때문
- 큐는 왜 선입선출 구조 사용? :
- 먼저 들어온 데이터를 먼저 처리해야 효율적으로 해결할 수 있기 때문
- 웹 브라우저의 뒤로 가기 기능은 어떤 자료 구조? : stack의 예시로 언급
- [과제 후기]
- - C언어로 자료구조를 공부했었는데, 파이썬으로 자료구조를 구현하는 건 처음이었다. 하지만 어떤 것들이 필요한지 금방 이해가 돼서 문제없이 과제를 마칠 수 있었다.
- - 선형 큐 구현하는 부분에서 배열로 구현했으니까 데이터를 삭제 했을 때 값을 앞으로 당겨야하지 않나? 라는 의문이 들었다. 찾아보니 큐는 자료를 이동시키는 것이 아닌 front와 rear를 움직여서 구현하는 것이 효율적이기 때문에 앞으로 당길 필요가 없다는 것이었다. 그래야 dequeue의 시간복잡도가 O(1)이 되어 효율적이라는 것이다. (삭제는 항상 맨 앞에서) 이 때문에 선형 큐에서 front가 계속 증가하는 문제가 발생한다. 이 문제를 해결하기 위해 원형 큐가 등장한 것이다. 라는 이야기를 과거에 들었던 기억이 나서 소름돋았다.
- - 배열, 스택, 큐를 구현하는 과정에서 과거의 기억을 더듬어 서치없이 구현해보고, 모자란 부분들을 채우는 식으로 해보았더니 조금 더 잘 와닿았다. 배열에서는 index 유효성 검사를 계속 해줘야하고, 스택에서는 데이터를 삽입(push) 할 때 stack overflow처리, 큐에서는 isFull과 isEmpty를 사용하여 enqueue, dequeue에서 에러를 잡아내도록 구현할 수 있었다.
- - 다음 과제는 어떤 것일지 기대되면서 무섭다.
'KDT > 과제' 카테고리의 다른 글
| [12일차 과제] 시간복잡도, 공간복잡도 (0) | 2026.06.07 |
|---|---|
| [11일차 과제] 자료구조(해시 테이블) (0) | 2026.06.04 |
| [10일차 과제] 자료구조(트리) (0) | 2026.06.03 |
| [9일차 과제] 자료구조(연결 리스트, 이중 연결 리스트) (0) | 2026.06.01 |
| [4일차 과제] (0) | 2026.05.22 |