[C/Python] 알고리즘 (스택 / 큐)

💡 1. 스택(Stack)의 기본: 가장 최근의 과거를 확인하다

스택은 '방금 내가 한 행동'이나 '가장 최근의 데이터'를 확인하고 지울 때 강력한 힘을 발휘합니다.

• 연속된 중복 제거 (같은 숫자는 싫어)
  • 별도의 상태 변수 없이 결과 배열 자체를 스택으로 활용합니다.
  • 파이썬은 answer[-1], C++은 **answer.back()**을 통해 맨 윗부분을 확인하여 다를 때만 데이터를 추가(push)합니다. 빈 배열 참조 에러를 막기 위한 단락 평가(or, ||)는 필수입니다.
• 짝 맞추기와 O(1) 공간 최적화 (올바른 괄호)
  • 열린 괄호는 넣고, 닫힌 괄호는 빼는 것이 기본 원리입니다.
  • 하지만 괄호의 종류가 단 하나(())일 때는, 무거운 배열(리스트)을 쓰는 대신 정수형 변수(count) 하나만으로 상태를 추적하여 공간 복잡도를 O(1)로 극적으로 최적화할 수 있습니다.

💡 2. 큐(Queue)와 시뮬레이션: 시간의 흐름을 통제하다

큐는 현실 세계의 '대기열'을 구현하는 시뮬레이션 문제에서 주로 등장합니다.

• 수학적 전처리와 배포 로직 (기능개발)
  • '앞의 기능이 끝나야 뒤의 기능이 배포된다'는 완벽한 큐 구조입니다.
  • 매일 진도를 더하는 대신, (100 - 진도) / 속도 공식을 통해 '각 기능의 완성 소요일'을 미리 계산해 두면 단 한 번의 루프(O(N))로 배포 그룹을 묶어낼 수 있습니다. (C++에서는 나머지 연산을 이용한 올림 처리 트릭 활용)
• 빈 공간을 활용한 길이 유지 (다리를 지나는 트럭)
  • 큐의 크기를 '다리의 길이'로 고정하고, 1초마다 큐를 회전시키는 시뮬레이션의 정석입니다.
  • 트럭이 올라가지 못할 때 의미 없는 데이터인 0을 큐에 밀어 넣어 길이를 유지하는 기법과, 하중을 매번 sum()으로 구하지 않고 변수 하나로 가감산하는 최적화가 필수적입니다.

💡 3. 자료구조의 응용과 심화

기본적인 push/pop을 넘어, 데이터를 어떻게 가공해서 넣을 것인지가 관건입니다.

• 식별자 부여와 우선순위 탐색 (프로세스)
  • 중복된 우선순위 숫자들 속에서 '내가 원했던 특정 프로세스'를 추적하려면 데이터에 이름표를 달아주어야 합니다.
  • 파이썬은 enumerate를 활용해 튜플 묶음으로, C++은 pair를 활용해 큐에 삽입합니다. 최고 우선순위를 찾을 때 C++은 priority_queue를 추가로 도입하면 탐색 속도를 극대화할 수 있습니다.
• 값이 아닌 '인덱스(시간)' 저장하기 (주식가격)
  • 이중 for문(O(N^2))을 스택(O(N))으로 바꾸는 마법 같은 문제입니다.
  • 스택에 주식의 가격을 넣는 것이 아니라, '아직 가격이 떨어지지 않은 시점(인덱스)'을 기록해 두었다가, 가격이 떨어지는 순간 현재 시간 - 과거 시간으로 버틴 기간을 계산해 내는 발상의 전환이 핵심입니다.

---

🛠️ 언어별 필수 암기 무기 (Python vs C++)

🐍 Python의 큐(Queue) 절대 원칙

• 큐를 다룰 때 기본 리스트의 pop(0)을 사용하면 데이터가 앞으로 당겨지며 O(N)의 시간이 걸려 무조건 시간 초과가 납니다.
• 반드시 **from collections import deque**를 선언하고 **popleft()**를 사용하여 O(1) 속도로 처리해야 합니다.

⚡ C++의 Pop 분리 원칙

• 파이썬과 달리 C++의 queue.pop()이나 stack.pop()은 데이터를 반환하지 않고 허공으로 날려버립니다(void).
• 따라서 데이터를 확인하려면 지우기 전에 반드시 **front() 또는 top()**으로 먼저 읽은 다음, pop()을 호출하는 두 단계 분리 작업을 잊지 말아야 합니다.