Skip to content

Week2

Directory actions

More options

Directory actions

More options

Latest commit

 

History

History

Week2

readme.md

파일명 분류 설명
browser_history.py 알고리즘 두 개의 스택을 활용하여 웹 브라우저의 '뒤로 가기'와 '앞으로 가기' 기능을 시뮬레이션합니다. 하나의 스택은 '뒤로 가기'를 위한 방문 기록을 저장하고, 다른 스택은 '앞으로 가기'를 위한 기록을 저장합니다. 새로운 페이지를 방문하면 '앞으로 가기' 스택이 초기화되는 실제 동작까지 정교하게 구현하는 방법을 보여줍니다.
josephus_problem.py 알고리즘 N명의 사람이 원형으로 앉아 K번째 사람을 계속해서 제거해 나갈 때 최후에 남는 사람을 찾는 고전적인 요세푸스 문제를 풉니다. 이 문제 해결에 collections.deque가 얼마나 효과적인지 보여줍니다. deque를 사용하면 K-1명의 사람을 맨 앞에서 빼서 맨 뒤로 보내는 작업을 O(1) 시간 복잡도로 효율적으로 처리할 수 있습니다.
parentheses_validator.py 알고리즘 스택 자료구조를 이용하여 괄호 (), {}, []의 짝이 올바른지 검사하는 알고리즘을 구현합니다. 여는 괄호가 나오면 스택에 넣고(push), 닫는 괄호가 나오면 스택에서 꺼낸(pop) 괄호와 짝이 맞는지 확인합니다. 모든 문자열을 순회한 후 스택이 비어있으면 유효한 괄호임을 판단하는 과정을 보여줍니다.
postfix_calculator.py 알고리즘 컴퓨터가 수식을 계산하는 방식 중 하나인 후위 표기법(Postfix Notation)을 스택을 이용해 계산하는 방법을 설명합니다. 피연산자는 스택에 넣고, 연산자가 나오면 스택에서 피연산자 두 개를 꺼내 계산한 뒤 그 결과를 다시 스택에 넣는 과정을 반복하여 최종 결과를 도출하는 계산기 로직을 구현합니다.
printer_queue_simulation.py 알고리즘 먼저 들어온 요청이 먼저 처리되는 선입선출(FIFO) 구조의 가장 대표적인 예인 프린터 대기열을 시뮬레이션합니다. collections.deque를 큐로 사용하여 새로운 인쇄 작업이 들어오면 큐의 뒤에 추가(append)하고, 프린터가 인쇄를 시작할 때는 큐의 앞에서 작업을 꺼내오는(popleft) 방식으로 실제 프린터의 동작 원리를 보여줍니다.
queue_with_deque.py 자료구조 큐(Queue)를 구현할 때 일반 list 대신 collections.deque를 사용해야 하는 이유를 명확히 보여줍니다. 리스트의 pop(0)는 O(n)의 비효율적인 연산이지만, deque의 popleft()는 O(1)이므로, 데이터가 많아질수록 큐의 핵심 연산인 Dequeue의 성능에서 큰 차이가 발생함을 강조합니다.
queue_with_two_stacks.py 자료구조 스택(LIFO) 두 개를 이용하여 큐(FIFO)의 동작을 구현하는 고전적인 컴퓨터 과학 문제입니다. 하나의 스택은 데이터 입력(Enqueue) 전용으로, 다른 하나는 데이터 출력(Dequeue) 전용으로 사용합니다. 출력 스택이 비었을 때 입력 스택의 모든 데이터를 옮기면 순서가 뒤집혀 FIFO가 구현되는 원리를 설명합니다.
recursive_factorial.py 알고리즘 함수가 자기 자신을 다시 호출하는 재귀(Recursion)의 개념을 팩토리얼 계산을 통해 설명합니다. 재귀 호출이 일어날 때마다 함수 실행 정보가 콜 스택(Call Stack)에 쌓이고, 재귀가 멈추는 베이스 케이스(Base Case)에 도달하면 스택의 맨 위부터 차례대로 함수가 반환되며 최종 결과가 계산되는 과정을 시각적으로 이해하기 쉽게 보여줍니다.
reverse_string_with_stack.py 알고리즘 스택의 후입선출(LIFO) 특징을 가장 직관적으로 활용하는 예제인 문자열 뒤집기를 보여줍니다. 문자열의 각 문자를 순서대로 스택에 모두 넣은 다음, 스택이 빌 때까지 다시 하나씩 꺼내면 가장 나중에 들어간 문자부터 나오게 되어 자연스럽게 문자열의 순서가 뒤집히는 원리를 설명합니다.
stack_with_list.py 자료구조 파이썬의 기본 자료구조인 list를 이용하여 스택(Stack)을 얼마나 간단하게 구현할 수 있는지 보여줍니다. 리스트의 맨 뒤에 데이터를 추가하는 append() 메소드가 스택의 Push 연산에 해당하고, 맨 뒤에서 데이터를 꺼내는 pop() 메소드가 Pop 연산에 해당하며, 두 연산 모두 O(1)의 효율적인 시간 복잡도를 가짐을 설명합니다.