3.1 데이터 작업: 삽입, 삭제, 검색
삽입 (Insert):
데이터 구조에 새 요소를 추가하는 작업이야. 삽입은 데이터 구조의 시작, 끝 또는 임의 위치에서 발생할 수 있어.
삭제 (Delete):
데이터 구조에서 요소를 제거하는 작업이야. 값에 따라, 인덱스에 따라 또는 데이터 구조 내 요소의 위치에 따라 삭제가 발생할 수 있어.
검색 (Search):
데이터 구조에서 요소를 찾는 작업이야. 값이나 다른 기준에 따라 검색할 수 있어.
작업 예시:
- 배열: 삽입과 삭제는 요소 이동이 필요해, 그래서 시간이 좀 걸릴 수 있어 —
O(n). - 연결 리스트: 삽입과 삭제는 노드의 위치만 알면
O(1)에 가능해. - 해시 테이블: 검색, 삽입, 삭제는 평균적으로
O(1)에 수행돼. - 트리: 검색, 삽입, 삭제는 균형 잡힌 트리에서
O(log n)에 수행돼.
3.2 기본 개념: 배열, 리스트, 스택, 큐
배열
배열은 인덱스로 접근 가능한 동일 타입의 요소 시퀀스야.
작업 복잡도: 인덱스 접근 — O(1), 삽입 및 삭제 — O(n).
예시: 배열 생성, 요소 변경 및 결과 출력
# 숫자 배열 생성
arr = [1, 2, 3, 4, 5]
# 인덱스 2의 요소 변경 (세 번째 요소, 인덱싱은 0부터 시작)
arr[2] = 10
# 변경된 배열 출력
print(arr) # 출력: [1, 2, 10, 4, 5]
# 배열 끝에 새 요소 추가
arr.append(6)
print(arr) # 출력: [1, 2, 10, 4, 5, 6]
# 인덱스로 요소 삭제
del arr[1]
print(arr) # 출력: [1, 10, 4, 5, 6]
리스트
리스트는 다음(단일 연결 리스트) 또는 다음 및 이전(이중 연결 리스트) 요소에 대한 참조를 포함하는 요소의 컬렉션이야.
작업 복잡도: 위치를 알면 삽입 및 삭제 — O(1), 검색 — O(n).
예시: 간단한 단일 연결 리스트 생성 및 순회
# 리스트 노드 구조 정의
class Node:
def __init__(self, data):
self.data = data
self.next = None
# 단일 연결 리스트 생성
node1 = Node("101")
node2 = Node("102")
node3 = Node("103")
# 노드 연결
node1.next = node2
node2.next = node3
# 리스트 시작 설정
list_head = node1
# 리스트 순회 및 데이터 출력
current = list_head
while current:
print(current.data)
current = current.next
# 출력:
# 101
# 102
# 103
스택 (Stack)
스택은 LIFO (Last In, First Out) 원칙을 따르는 요소의 컬렉션이야: 마지막에 추가된 것이 먼저 나가.
작업 복잡도: 삽입 (push) 및 삭제 (pop) — O(1).
예시: 괄호 균형 체크를 위한 스택 구현 및 사용
def is_balanced(expression):
stack = []
opening = "({["
closing = ")}]"
pairs = {")": "(", "}": "{", "]": "["}
for char in expression:
if char in opening:
stack.append(char)
elif char in closing:
if not stack or stack.pop() != pairs[char]:
return False
return len(stack) == 0
# 다양한 표현식 검사
print(is_balanced("({[]})")) # 출력: True
print(is_balanced("([)]")) # 출력: False
print(is_balanced("((")) # 출력: False
큐 (Queue)
큐는 FIFO (First In, First Out) 원칙을 따르는 요소의 컬렉션이야: 먼저 추가된 것이 먼저 나가.
작업 복잡도: 삽입 (enqueue) 및 삭제 (dequeue) — O(1).
예시: 작업 처리를 시뮬레이션하기 위한 큐 구현 및 사용
from collections import deque
class TaskQueue:
def __init__(self):
self.queue = deque()
def add_task(self, task):
self.queue.append(task)
print(f"작업 '{task}'이(가) 큐에 추가됨")
def process_task(self):
if self.queue:
task = self.queue.popleft()
print(f"작업 처리 중: '{task}'")
else:
print("큐가 비어있음")
def display_queue(self):
print("현재 작업 큐:", list(self.queue))
# 작업 큐 생성 및 사용
task_queue = TaskQueue()
task_queue.add_task("이메일 발송")
task_queue.add_task("데이터베이스 업데이트")
task_queue.add_task("보고서 생성")
task_queue.display_queue()
task_queue.process_task()
task_queue.process_task()
task_queue.display_queue()
# 출력:
# 작업 '이메일 발송'이(가) 큐에 추가됨
# 작업 '데이터베이스 업데이트'이(가) 큐에 추가됨
# 작업 '보고서 생성'이(가) 큐에 추가됨
# 현재 작업 큐: ['이메일 발송', '데이터베이스 업데이트', '보고서 생성']
# 작업 처리 중: '이메일 발송'
# 작업 처리 중: '데이터베이스 업데이트'
# 현재 작업 큐: ['보고서 생성']
3.3 다양한 데이터 구조의 차이점
여기 다양한 데이터 구조 간의 주요 차이점이 있어:
배열:
- 접근: 인덱스로 빠른 접근 가능 —
O(1). - 크기 변경: 고정된 크기, 크기 증가 시 모든 요소를 복사해야 함 —
O(n). - 적합도: 데이터의 크기를 미리 아는 경우, 랜덤 액세스가 필요한 경우.
연결 리스트:
- 접근: 인덱스로 느린 접근 —
O(n). - 크기 변경: 쉽게 크기 변경 가능, 삽입 및 삭제 —
O(1). - 적합도: 자주 삽입 및 삭제하는 경우.
스택:
- 작업 원칙:
LIFO. - 작업: 한쪽 끝에서만 삽입 및 삭제 —
O(1). - 적합도: 작업의 역순 처리가 필요할 때, 함수 호출 관리.
큐:
- 작업 원칙:
FIFO. - 작업: 다른 끝에서 삽입 및 삭제 —
O(1). - 적합도: 작업이 들어온 순서대로 처리해야 할 때.
3.4 다양한 데이터 구조의 응용
다양한 데이터 구조의 실전 응용 예시:
배열
정해진 길이의 데이터 저장, 예를 들어 요일 또는 1년의 월.
예시: 요일 관련 작업을 위한 배열 사용
# 요일을 담은 배열 생성
days = ["월요일", "화요일", "수요일", "목요일", "금요일", "토요일", "일요일"]
# 인덱스로 요일을 가져오기 (예: 세 번째 요일)
print(days[2]) # 출력: 수요일
# 요일 이름 변경
days[0] = "월요일 (주의 시작)"
print(days[0]) # 출력: 월요일 (주의 시작)
# 모든 요일 출력
for day in days:
print(day)
# 출력:
# 월요일 (주의 시작)
# 화요일
# 수요일
# 목요일
# 금요일
# 토요일
# 일요일
연결 리스트
동적 컬렉션 구현, 컬렉션 중간에 요소 추가 및 삭제 가능.
예시: 할일 목록 저장을 위한 연결 리스트 구현 및 사용
class TodoItem:
def __init__(self, task):
self.task = task
self.next = None
class TodoList:
def __init__(self):
self.head = None
def add_task(self, task):
new_item = TodoItem(task)
if not self.head:
self.head = new_item
else:
current = self.head
while current.next:
current = current.next
current.next = new_item
def display_tasks(self):
current = self.head
if not current:
print("할일 목록이 비어있음")
else:
while current:
print(f"- {current.task}")
current = current.next
# 할일 목록 생성 및 사용
todo = TodoList()
todo.add_task("장보기")
todo.add_task("엄마께 전화하기")
todo.add_task("프레젠테이션 준비")
print("내 할일 목록:")
todo.display_tasks()
# 출력:
# 내 할일 목록:
# - 장보기
# - 엄마께 전화하기
# - 프레젠테이션 준비
스택
작업의 역순 처리, 예를 들어 함수 호출 처리, 작업 취소 (undo).
예시: 문자열 역순 처리를 위한 스택 사용
def reverse_string(s):
stack = []
# 문자열의 각 문자 스택에 추가
for char in s:
stack.append(char)
reversed_s = ''
# 스택에서 문자를 꺼내어 역순 문자열 생성
while stack:
reversed_s += stack.pop()
return reversed_s
# 예제 사용
original = "Hello, World!"
reversed_str = reverse_string(original)
print(f"원본 문자열: {original}")
print(f"역순 문자열: {reversed_str}")
# 출력:
# 원본 문자열: Hello, World!
# 역순 문자열: !dlroW ,olleH
큐
작업이 들어온 순서대로 처리, 예를 들어 인쇄 작업, 고객 서비스 큐.
예시: 문서 인쇄 큐 시뮬레이션
from collections import deque
class PrinterQueue:
def __init__(self):
self.queue = deque()
def add_document(self, document):
self.queue.append(document)
print(f"문서 '{document}'이(가) 인쇄 대기열에 추가됨")
def print_document(self):
if self.queue:
document = self.queue.popleft()
print(f"문서 인쇄 중: '{document}'")
else:
print("인쇄 대기열이 비어있음")
def display_queue(self):
print("현재 인쇄 대기열:", list(self.queue))
# 인쇄 대기열 생성 및 사용
printer = PrinterQueue()
printer.add_document("보고서")
printer.add_document("프레젠테이션")
printer.add_document("계약서")
printer.display_queue()
printer.print_document()
printer.print_document()
printer.display_queue()
# 출력:
# 문서 '보고서'이(가) 인쇄 대기열에 추가됨
# 문서 '프레젠테이션'이(가) 인쇄 대기열에 추가됨
# 문서 '계약서'이(가) 인쇄 대기열에 추가됨
# 현재 인쇄 대기열: ['보고서', '프레젠테이션', '계약서']
# 문서 인쇄 중: '보고서'
# 문서 인쇄 중: '프레젠테이션'
# 현재 인쇄 대기열: ['계약서']
이 예제에서는 간단한 인쇄 대기열 시뮬레이션을 만들었어. 문서는 대기열 끝에 추가되고 들어온 순서대로 인쇄되며, 이는 FIFO (First In, First Out) 원칙을 보여줘.
GO TO FULL VERSION