📚 스택(Stack)

• 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조임
  • 선형구조 : 자료 간의 관계가 1:1 관계를 가짐
  • 선형구조 VS 비선형 : 자료간의 관계가 1 대 N의 관계를 가짐 ex) 트리구조

---

• LIFO
  • 구현 조건
    • 자료를 선형으로 저장할 저장소가 필요 : 배열을 사용
    • 마지막에 삽입된 원소의 위치를 TOP
  • 연산
    • 자료를 저장 PUSH
    • 역순으로 꺼내기 POP
    • isempty()
    • peek : top에 있는 원소 끝내기
      

• 1차원 배열로 구현 vs 동적할당으로 구현
  장점 : 구현용이 <-> 가변적임
  단점 : stack의 크기를 변경하기 어려움 <-> 구현에 어려움
  

---

🍭 대표 문제

1. 괄호검사

2. 함수호출

• 프로그램에서 함수호출과 복귀에 따른 수행순서를 관리
  => 함수 호출이 발생하면 호출에 필요한 지역변수, 매개변수 / 수행 후 복귀할 주소 등
  정보를 stack 프레임에 저장하여 시스템 stack에 삽입
  = > 함수의 실행이 끝나면 시스템 stack의 top 원소를 삭제(pop 하면서 프레임에
  저장되어있던 복귀주소를 확인하고 복귀
  => 함수 호출과 복귀에 따라 이과정을 반복하여 전체 프로그램 수행이 종료되면
  시스템 stack 은 공백이 됨.

  ex) 재귀호출
  * Memoization (파보나치 수열)을 구하는 함수
  - 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하는 기술
  - DP 의 핵심기술

3.DP 동적 계획법 : 최적화 문제를 해결하는 알고리즘 설계 기법

• 입력 크기가 작은 부분 문제들을 해결 후에 큰 문제들을 해결하는 계획법.
  • 구현 방식
    1. 재귀방법 : 오버헤드 발생
    2. 반복문 : 메모리제이션 보다 효율적

🎨 그래프

• 비선형구조
• 빠짐없이 다 검색하는 것이 중요!
  종류 : 깊이우선탐색 : stack
  너비우선탐색 : queue