스택(Stack)

[lukasjhan]

특징

• LIFO(Last In First Out) 활용
  • 가장 최근 데이터와 비교/처리가 필요한 경우
  • 마지막에 들어온 데이터를 먼저 처리해야 하는 경우
  • 이전 상태로 돌아가야 하는 경우
• 짝/쌍 매칭
  • 괄호 짝 맞추기
• 히스토리/상태 관리
  • 상태 저장 및 복원

문제로 부터 유추할 수 있는 키워드

• "괄호", "태그"
• "가장 최근의", "마지막"
• "되돌리기", "취소"
• "짝을 이루는"
• "서로 맞는"
• "이전 상태"

푸는 방법

1. 스택 맨 위에 있는 데이터의 의미를 정의한다.

• 스택에 어떤 데이터가 쌓이는지
• 스택 맨 위 데이터가 어떤 의미를 가지는지

예) 스택 맨 위 = 아직 더 따뜻한 날을 못 찾은 가장 최근 날짜

2. 스택 연산의 의미 정의

• push: 언제 데이터를 넣을 것인지
• pop: 언제 데이터를 뺄 것인지

예)
push: 현재 온도가 스택 top의 온도보다 낮거나 같을 때
pop: 현재 온도가 스택 top의 온도보다 높을 때

3. 스택 데이터 정의

• 문제 해결에 필요한 정보를 스택에 저장할 형태로 정의

예) [인덱스, 온도정보] 2가지 정보를 스택에 저장

4. 스택 연산 실행

규칙에 의해 실행하여 문제해결

[lukasjhan]

빼먹엇는데 종료조건도 중요합니다.