[알고리즘 설명][Python] 스택(stack)

이 게시글은 CS(컴퓨터공학) 프로그래밍 기초를 어느 정도 알고 있다고 가정하고 아주 간단하게 설명하는 게시글입니다.

혹시나 모르는 부분이 있으면 댓글로 질문해주세요.

 

한 줄 요약 : Python에서 스택 자료 구조 구현하는 방법? list에서 append(), pop() 2개만 사용하면 스택 구현 끝!

 

스택 자료구조는 LIFO(Last In First Out) 자료구조이며 이것의 의미는 아래에 있는 소스 코드를 확인해주세요.

import sys

input = sys.stdin.readline

website_visited_memory:list = []

print("현재 접속한 사이트 목록 ->", *website_visited_memory)

# 가장 먼저 구글에 접속합니다.
website_visited_memory.append("구글")
print("접속했던 사이트 목록 ->", *website_visited_memory)

# 그 다음으로 다음, 네이버, 티스토리 순서대로 방문하여 방문 기록을 확인합니다.
website_visited_memory.append("다음")
website_visited_memory.append("네이버")
website_visited_memory.append("티스토리")
print("접속했던 사이트 목록 ->", *website_visited_memory)

# 여기가 가장 중요한데 뒤로 가기로 이전 사이트를 확인할려면
# 스택에서 pop()으로 가장 마지막에 들어간 사이트(Last In)를 가장 먼저 나오도록(First Out) 합니다.
website_visited_memory.pop()
print("현재 방문하고 있는 사이트 ->", website_visited_memory[-1])

스택은 진짜로 별거 없습니다.

그냥 list로 원소 추가할 때 append(), 원소 삭제할 때 pop()으로 하면 끝이니까요.

즉, 맨 오른쪽에 가장 최신 정보를 넣어주고 마지막으로 들어간 정보(Last In)를 가장 먼저 빼는(First Out) 방식이 바로 스택 자료구조입니다.

한 번 Python 온라인 컴파일러에 가서 직접 실행해보세요!

 

추가로 회전초밥집에서 접시 별로 색깔과 가격이 다 다릅니다.

이 때 어떤 손님이 회전 초밥을 맛있게 먹어서 하나씩 접시들을 올립니다.

그 뒤 손님이 초밥 다 먹고 직원이 정산하기 위해 맨 위에 있는 접시들을 하나씩 보면서 가격을 계산합니다.

 

이 때 Gemini를 활용해서 최대한 실제 정산과 비슷하게 시뮬레이션 소스 코드를 만들었습니다.

제가 중간에 수동으로 디버깅도 같이 했습니다.

# 초밥 객체 정의 (백엔드 엔티티)
class Sushi :
    def __init__(self, code, name) :
        self.code = code
        self.name = name

# 접시 등급 및 가격 테이블 (실제 데이터베이스)
SUSHI_PLATE_TABLE = [
    ("Premium 블랙/금분 접시", 10000, [Sushi("S001", "참다랑어 오도로"), Sushi("S002", "성게알 군함")]),
    ("VIP 보라 접시", 8000, [Sushi("S003", "참다랑어 주도로"), Sushi("S004", "생참치 등살")]),
    ("스페셜 레드 접시", 6500, [Sushi("S005", "민물장어"), Sushi("S006", "살치살 직화구이")]),
    ("하이 골드 접시", 5200, [Sushi("S007", "간장새우"), Sushi("S008", "연어 뱃살 아부리")]),
    ("미디움 블루 접시", 4300, [Sushi("S009", "국산 활광어"), Sushi("S010", "생연어")]),
    ("레귤러 그린 접시", 3200, [Sushi("S011", "구운 계란새우"), Sushi("S012", "가리비")]),
    ("이코노미 옐로우 접시", 2100, [Sushi("S013", "초새우"), Sushi("S014", "떡갈비")]),
    ("가성비 화이트 접시", 1500, [Sushi("S015", "계란말이"), Sushi("S016", "유부초밥")])
]

# 조회 인덱스 생성
code_to_info:dict = {}
for plate_name, price, sushi_list in SUSHI_PLATE_TABLE :
    for sushi in sushi_list:
        code_to_info[sushi.code] = {"name": sushi.name, "price": price, "plate": plate_name}

def run_sushi_settlement() :
    # 1. 손님이 먹은 초밥 주문 로그 (Stack : 마지막 요소가 맨 위의 접시)
    order_logs = ["S001", "S001", "S003", "S005", "S005", "S007", "S009", "S009", "S011", "S013", "S015", "S015"]
    
    print("[현장 고증 정산 시스템] 직원이 접시 탑에서 하나씩 걷어내며 분류 시작")
    
    total_counts:dict = {plate[0]: 0 for plate in SUSHI_PLATE_TABLE}
    
    # 2. [LIFO 정석] reverse() 없이 pop()을 통해 맨 위 접시부터 현실적으로 처리
    while order_logs :
        code:int = order_logs.pop() # 직원이 맨 위 접시를 집어 들음
        info:dict = code_to_info[code]
        
        # 실제 직원이 접시를 색깔별로 따로 분류(카운팅)하는 과정
        total_counts[info["plate"]] += 1
        print(f"작업 처리 : (코드 : {code}){info['name']} 확인 -> {info['plate']} 구역으로 분류 완료")
    
    print("\n--- [DP 정산 체인] 분류된 접시들을 가격순으로 정산 ---")
    
    dp:list = [0 for _ in range(len(SUSHI_PLATE_TABLE) + 1)]
    
    # 3. 정산 : 이제 모든 분류가 끝났으니, DP 테이블을 채우며 총액 산출
    for i in range(1, len(SUSHI_PLATE_TABLE) + 1):
        plate_name, plate_price, _ = SUSHI_PLATE_TABLE[i-1]
        count:int = total_counts[plate_name]
        
        # dp[i] = dp[i-1] + alpha (정산 체인)
        alpha:int = count * plate_price
        dp[i] = dp[i-1] + alpha
        
        print(f"정산 단계 {i} ({plate_name}) : {count}개 * {plate_price}원 = {alpha:,}원 누적되어 현재 정산액 {dp[i-1]}원 -> {dp[i]}원")
        
    print(f"\n[최종 정산] 총 결제 금액 : {dp[-1]:,}원")

run_sushi_settlement()

[실행 결과]

[현장 고증 정산 시스템] 직원이 접시 탑에서 하나씩 걷어내며 분류 시작
작업 처리 : (코드 : S015)계란말이 확인 -> 가성비 화이트 접시 구역으로 분류 완료
작업 처리 : (코드 : S015)계란말이 확인 -> 가성비 화이트 접시 구역으로 분류 완료
작업 처리 : (코드 : S013)초새우 확인 -> 이코노미 옐로우 접시 구역으로 분류 완료
작업 처리 : (코드 : S011)구운 계란새우 확인 -> 레귤러 그린 접시 구역으로 분류 완료
작업 처리 : (코드 : S009)국산 활광어 확인 -> 미디움 블루 접시 구역으로 분류 완료
작업 처리 : (코드 : S009)국산 활광어 확인 -> 미디움 블루 접시 구역으로 분류 완료
작업 처리 : (코드 : S007)간장새우 확인 -> 하이 골드 접시 구역으로 분류 완료
작업 처리 : (코드 : S005)민물장어 확인 -> 스페셜 레드 접시 구역으로 분류 완료
작업 처리 : (코드 : S005)민물장어 확인 -> 스페셜 레드 접시 구역으로 분류 완료
작업 처리 : (코드 : S003)참다랑어 주도로 확인 -> VIP 보라 접시 구역으로 분류 완료
작업 처리 : (코드 : S001)참다랑어 오도로 확인 -> Premium 블랙/금분 접시 구역으로 분류 완료
작업 처리 : (코드 : S001)참다랑어 오도로 확인 -> Premium 블랙/금분 접시 구역으로 분류 완료

--- [DP 정산 체인] 분류된 접시들을 가격순으로 정산 ---
정산 단계 1 (Premium 블랙/금분 접시) : 2개 * 10000원 = 20,000원 누적되어 현재 정산액 0원 -> 20000원
정산 단계 2 (VIP 보라 접시) : 1개 * 8000원 = 8,000원 누적되어 현재 정산액 20000원 -> 28000원
정산 단계 3 (스페셜 레드 접시) : 2개 * 6500원 = 13,000원 누적되어 현재 정산액 28000원 -> 41000원
정산 단계 4 (하이 골드 접시) : 1개 * 5200원 = 5,200원 누적되어 현재 정산액 41000원 -> 46200원
정산 단계 5 (미디움 블루 접시) : 2개 * 4300원 = 8,600원 누적되어 현재 정산액 46200원 -> 54800원
정산 단계 6 (레귤러 그린 접시) : 1개 * 3200원 = 3,200원 누적되어 현재 정산액 54800원 -> 58000원
정산 단계 7 (이코노미 옐로우 접시) : 1개 * 2100원 = 2,100원 누적되어 현재 정산액 58000원 -> 60100원
정산 단계 8 (가성비 화이트 접시) : 2개 * 1500원 = 3,000원 누적되어 현재 정산액 60100원 -> 63100원

[최종 정산] 총 결제 금액 : 63,100원

이 소스 코드는 스택 자료구조의 활용 예시를 설명한 것이지만 django에서 models.py에 Entity 및 DTO를 설정하고, 데이터베이스는 MySQL같은 외부 DB에 연동하고, view.py, service.py에서 비즈니스 로직을 설계하면 실제 백엔드 설계와 유사합니다.

이 내용을 추가한 이유는 단순한 알고리즘 및 자료구조가 나중에 어떻게 백엔드로 연결되는지 간단하게 짚어야 할 필요성을 느꼈습니다.

 

이렇게 해서 오늘 초간단하게 스택 자료구조를 알게 되었습니다.

스택은 말 그대로 리스트에서 맨 앞에 추가, 맨 앞에 제거 이 2가지만 실행하는 자료구조 정도로만 아시면 됩니다.