[20250131] 파이썬 프로그래밍 - 알고리즘 1

수업 목표

- 스택 자료의 구조를 설명할 수 있다.

- 스택을 리스트와 클래스로 구현할 수 있다.

- 큐 자료의 구조를 설명할 수 있다.

- 큐를 리스트와 클래스로 구현할 수 있다.

 

 

1. 스택 (Stack)

- 데이터를 처리하는 기본 자료 구조

- 데이터의 삽입과 삭제가 상단에서만 발생

- 후입선출(Last In First Out, LIFO) 형태로 데이터 처리

    - 가장 마지막에 입력된 데이터가 가장 먼저 제거되는 구조

- 처리 방식

    - push : 스택에 데이터를 삽입하는 동작 -> append 사용

    - pop : 스택에서 데이터를 제거하는 동작 -> pop 사용

- 스택 활용 사례

    - 함수 호출 스택

    - 웹 브라우저 방문 기록 (뒤로가기)

    - 괄호 검사와 같은 문자열 처리

 

스택 구현

class Stack():
	def __init__(self):
    	self.stack = []
    
    def push(self, data): # push 메서드
    	self.stack.append(data)
    
    def pop(self): # pop 메서드
        if not self.is_empty():
        	return self.stack.pop()
        return
    
    def is_empty(self): # 유무 확인
    	if len(self.stack) == 0:
        	return True
        return False
    
    def peak(self): # top 확인
    	if not self.is_empty():
        	return self.stack[-1]
        return
    
    def status_stack(self): # 스택 상태
    	return self.stack

 

 

2. 큐 (Queue)

- 데이터를 처리하는 기본 자료구조

- 선입선출(First In First Out, FIFO) 형태로 데이터 처리

   - 마지막에 데이터를 입력하고 가장 먼저 입력된 데이터가 먼저 제거하는 구조

- 처리 방식

    - Enqueue : 큐에 데이터를 삽입하는 동작

    - Dequeue : 큐에서 데이터를 제거하는 동작

- 큐 활용 사례

    - 프로세스 관리 (e.g. 작업 대기열)

    - BFS (너비 우선 탐색) 구현

 

큐 구현

class Queue():
    def __init__(self):
        self.queue = []
    
    def enqueue(self, data): # enqueue 메서드
        self.queue.append(data)
    
    def dequeue(self):
        if not self.is_empty(): # dequeue 메서드
            return self.queue.pop(0) # pop 인덱스를 준 것만 stack과 다름
        return
    
    def is_empty(self): # 데이터 유무 확인
        if len(self.queue) == 0:
            return True
        return False

    def status_queue(self): # 큐 상태 반환
        return self.queue

3. 덱 (Deque; Double Ended QUEue)

- 양쪽 끝에서 삽입과 삭제가 가능한 자료구조

- 스택과 큐를 병합한 형태의 자료구조

- 파이썬 내장 모듈 collections 활용

- 덱 활용 사례

    - 회전 큐 (e.g. 슬라이딩 윈도우)

    - 문자열 회문 검사

- 처리 방식

    - append : 마지막 추가

    - appendleft : 처음 추가

    - pop : 마지막 제거

    - popleft : 처음 제거

- from collections import deque 활용