스택(Stack) & Memoization

스택(Stack)의 특징

• 스택에 저장된 자료는 선형구조를 갖는다. (이때 선형구조란, 자료가 연속적으로 연결되어 있는 구조를 말하며, 자료간의 관계가 1:1인 구조이다.)
• 마지막에 삽입한 자료를 가장 먼저 꺼낸다. 후입선출(LIFO, Last-In-First-Out)
• 자료를 선형으로 저장할 저장소가 필요하다. 

스택의 연산

• 삽입 :  보통 push라고 부르며, 저장소에 자료를 저장한다.

s = []
def push(item):
	s.append(item)

 

• 삭제 : 보통 pop이라고 부르며, 저장소에 자료를 꺼낸다. 이때, 자료는 삽입한 자료의 역순으로 꺼낸다.

def pop():
    if len(s) == 0:
    	print("Stack underflow") #underflow, 에러메세지 삽입
        return
    else:
    	return s.pop()

 

• isEmpty : 스택이 공백인지 아닌지 확인하는 연산, 스택이 비어있으면 1, 아니면 0을 반환

def isEmpty():
    return len(s.top) == 0

 

• peek : 스택의 top에 있는 item(원소)를 삭제하지 않고 반환하는 연산

def peek():
    if not s.isEmpty():
    	return s.top[-1]
    else:
    	print("underflow")
        return

---

Memoization

=> 컴퓨터 프로그래밍이 동일한 계산을 반복할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술. DP(동적계획법)의 핵심이 되는 기술.

 

• 피보나치 수열을 구하는 함수의 알고리즘

def fibo(n):
    if n < 2:
    	return n
    else:
    	return fibo(n-1) + fibo(n-2)

=> 엄청난 중복 호출이 생기는 문제점이 생김. 이 때, 메모이제이션을 써서 불필요한 계산을 없애줌.

 

• Memoization 방법을 적용한 알고리즘

def fibo1(n):
    global memo
    if n >= 2 and len(memo) <= n:
    	memo.append(fibo1(n-1) + fibo1(n-2))
    return memo[n]
    
memo = [0, 1]

# memo를 위한 리스트를 생성하고,
# memo[0]을 0으로 memo[1]은 1로 초기화