[2024.02.07] Stack 1

체리마루·2024년 2월 7일

SSAFY

스택

스택의 특성

물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조이다.
스택에 저장된 자료는 '선형 구조'를 갖는다.
선형구조: 자료 간의 관계가 1대 1의 관계를 갖는다.
비선형구조: 자료간의 관계가 1대 N의 관계를 갖는다. (예: 트리)
스택에 자료를 삽입하거나 스택에서 자료를 꺼낼 수 있다.
마지막에 삽입한 자료를 가장 먼저 꺼낸다. 후입선출 (LIFO, Last-In-First-Out)
예를 들어 스택에 1,2,3 순으로 자료를 삽입한 후 꺼내면 역순으로 즉 3,2,1 순으로 꺼낼 수 있다.

스택의 구현

자료구조: 자료를 선형으로 저장할 저장소
배열을 사용할 수 있다.
저장소 자체를 스택이라 부르기도 한다.
스택에서 마지막 삽입된 원소의 위치를 top이라 부른다.
연산
- 삽입: 저장소에 자료를 저장한다. 보통 push라고 부른다.
- 삭제: 저장소에서 자료를 꺼낸다. 꺼낸 자료는 삽입한 자료의 역순으로 꺼낸다. 보통 pop이라고 부른다.
- 스택이 공백인지 아닌지를 확인하는 연산. isEmpty
- 스택의 top에 있는 item(원소)을 반환하는 연산. peek

스택의 삽입/삭제 과정

스택의 push 알고리즘

append 메소드를 통해 리스트의 마지막에 데이터를 삽입

def push(item):
	s.append(item)

[참고] 스택의 구현

def push(item, size):
	global top
    top += 1
    if top == size:
    	print('overflow!')
    else:
    	stack[top] = item
        
size = 10
stack = [0] * size
top = -1

push(10, size)
top += 1 			#push(20)
stack[top] = 20

스택의 pop 알고리즘

def pop():
	if len(s) == 0:
    # underflow
    return
    
   	else:
    return s.pop()

[참고] 스택의 구현

def pop():
	global top
    if top == -1
    	print('underflow')
        return 0
    else:
    	top -= 1
        return stack[top+1]

print(pop())

if top > -1:    # pop()
	top -= 1
    print(stack[top+1])

#스택이라는 기본 자료형의 자료구조(리스트)
stack = []

#스택에 필요한 연산 (뒤 삽입 / 뒤 삭제)
def push(x): #x를 삽입
    stack.append(x)

def pop(): #마지막 요소를 빼내고 반환
    #리스트 비어있다면 (예외처리)
    if len(stack) == 0:
        return 
    return stack.pop()

def peek(): #마지막 요소의 값을 반환
    #리스트 비어있다면 (예외처리)
    if len(stack) == 0:
        return
    return stack[-1]

스택의 응용: function call

function call

프로그램에서의 함수 호출과 복귀에 따른 수행 순서를 관리
가장 마지막에 호출된 함수가 가장 먼저 실행을 완료하고 복귀하는 후입선출 구조이므로, 후입선출 구조의 스택을 이용하여 수행순서 관리
함수 호출이 발생하면 호출한 함수 수행에 필요한 지역변수, 매개변수 및 수행 후 복귀할 주소 등의 정보를 스택 프레임에 저장하여 시스템 스택에 삽입
함수 실행이 끝나면 시스템 스택의 top 원소(스택 프레임)를 삭제(pop)하면서 프레임에 저장되어 있던 복귀주소를 확인하고 복귀
함수 호출과 복귀에 따라 이 과정을 반복하여 전체 프로그램 수행이 종료되면 시스템 스택은 공백 스택이 된다.

재귀호출

필요한 함수가 자신과 같은 경우 자신을 다시 호출하는 구조
함수에서 실행해야 하는 작업의 특성에 따라 일반적인 호출방식보다 재귀호출방식을 사용하여 함수를 만들면 프로그램의 크기를 줄이고 간단하게 작성
ex) factorial

n에 대한 factorial (by 재귀함수)

1부터 n까지의 모든 자연수를 곱하여 구하는 연산

n! = n * (n-1)!
(n-1)! = (n-1) * (n-2)!
(n-2)! = (n-2) * (n-3)!
...
2! = 2 * 1!
1! = 1

마지막에 구한 하의 값을 이용하여 상위 값을 구하는 작업 반복

Fibonacci (by 재귀함수)

0과 1로 시작하고 이전의 두 수의 합을 다음 항으로 하는 수열 => 0, 1, 1, 2, 3, 5, 8, 13, ...
피보나치 수열의 i번째 값을 계산하는 함수 F
F0 = 0, F1 = 1
Fi = Fi-1 + Fi-2 (for i >=2)

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

-> 피보나치 수 재귀함수의 단점: 엄청난 중복 호출이 존재

Memoization

컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다.
글자 그대로 해석하면 '메모리에 넣기'라는 의미이며, '기억되어야 할 것'이라는 뜻이라는 라틴어에서 파생되었다.
재귀로 구현된 피보나치 알고리즘에서 fibo(n)의 값을 계산하자마자 저장하면, 실행시간을 Θ(n)으로 줄일 수 있다.

Memoiztion 알고리즘

#memo를 위한 배열을 할당하고, 모두 0으로 초기화
#memo[0]을 0으로 memo[1]은 1로 초기화

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

memo = [0] * (n+1)
memo[0] = 0
memo[1] = 1