Stack 자료구조

선형구조를 가지는 자료구조

특징

  1. 물건을 쌓아 올린듯 자료를 쌓아 올린 형태의 자료구조 (ex. 접시)

  2. Stack에 저장된 자료는 선형구조를 가짐

    • 자료 간의 관계가 1 : 1 의 관계를 가짐
    • 앞의 자료가 뒤의 자료에 영향을 미친다, 뒤의 자료는 앞의 자료에 종속적인 성격을 가짐
    • 반대로 비선형구조는 자료 간의 관계가 1 : N의 관계를 가짐(Ex.Tree)

	Ex) 괄호검사문제 - `(())` 와 같은 괄호가 있을때 열고 닫는 한 쌍이 `()` 존재하는지 확인하는 문제 같은 경우, 앞의 (( 여는 괄호가 있냐 없냐에 따라 뒤에 닫는 괄호가 )) 필요하고 필요 없고가 결정된다. 즉, 앞의 자료가 뒤에 자료에 영향을 미치거나 미쳐야 하는 경우 Stack 자료구조를 사용해야 한다.
  1. Stack에 자료를 삽입(PUSH)/삭제(POP) 할 수 있음
  2. LIFO : 마지막에 삽입한 자료가 가장 먼저 꺼내짐 후입선출(Last-In-First_Out)

사용법

  • push() : Stack에 자료를 저장, 스택의 가장 윗 자리(top)이 가리키는 자리 위에 삽입된다. top은 하나 증가
  • pop() : Stack에 자료를 꺼냄 출력, 그리고 출력한 데이터를 Stack에서 삭제한다. top은 하나 감소
  • empty() : Stack이 비어 있는지 아닌지 확인, 비어있을시 1(True)을 return, 값이 들어있으면 0(False)을 return
  • top() : Stack의 제일 위에 있는(제일 마지막에 삽입한 자료)를 반환함, 만약 비어있다면 -1 혹은 정의불가 상태임

구현

1차원 배열을 이용하여 구현하면, 구현이 쉬운반면에 Stack의 크기를 변경하기가 어렵다. 그래서 —> Stack을 동적으로 할당하여 구현하는것이 더 좋은 방법이 되겠다. 동적 Linked List를 이용해서 구현해보자. 그러면 메모리를 효율적으로 사용가능하다.

#=> 소스코드 입력

Call Stack

  • 프로그램에서 함수 호출과 return에 의한 복귀에 따른 수행 순서를 관리하기 위해 Stack자료구조를 사용

Memoization

재귀함수를 사용할때 무수한 중복호출을 방지하는 방법. (DP : Dynamic Programming, 동적계획법)의 핵심이 되는 기술

예를들어 피보나치 수열을 구하는 문제의 실행 Tree를 살펴보면 똑같은 함수호출이 반복된다는 것을 알 수 있다.

#=> Tree 사진

이전의 계산한 값을 메모리에 저장해서 매번 다시 연산하지 않도록 해서 실행속도를 높이는 방법

DP(Dynamic Programming, 동적계획법)

음….상향식의…문제풀이 방법??

  • Greedy Algorithm 설계 기법과 같이 최적화 문제를 해결하는 설계기법
  • 일단 입력크기가 작은 부분 문제들을 모두 해결한 후에 그 해들을 이용하여 더 큰 덩어리를 해결
  • 최종적으로 원래 주어진 입력으로 문제를 해결

피보나치 수열 구하는것과 같이

  1. 부분문제로 분할 가능한지 확인하고 가능하면 부분 문제로 분할하고
  2. 분할 한 작은 부분으로 작은 부분부터 문제를 해결하고
  3. 그 결과를 테이블에 저장하고, 테이블에 저장된 부분 문제의 해를 이용하여 그 위의 문제의 정답을 구함

구현방식

  • 재귀(Recursive)방식
    • 재귀적 구조는 내부에 시스템 호출 Stack을 사용하는 Overhead가 발생할 수 있음
  • 반복문(Iteractive)방식
    • Memoization을 재귀적 구조에 사용하는 것보다 반복문과 같이 DP를 구현하는 것이 성능면에서 보다 효율적이라고 한다.