Stack 1

알고리즘

Stack 1

Disciple428 2024. 2. 7. 20:57

스택의 특성

자료를 쌓아올린 형태의 자료 구조

마지막에 삽입한 자료를 가장 먼저 꺼내게 된다. (후입선출)

스택에서 마지막으로 삽입된 원소의 위치를 top이라 부른다.

스택에 저장된 자료는 선형 구조를 갖는다.

cf) 선형구조 : 자료 간의 관계가 1대1 관계를 갖음

비선형구조 : 자료 간의 관계가 1대N 관계를 갖음 (ex : 트리)

스택 연산

삽입 : 저장소에 자료를 저장 (=push)

삭제 : 저장소에서 자료를 꺼내고 지움. 꺼낸 자료는 삽입한 역순으로 꺼낸다 (=pop)

isEmpty : 스택이 공백인지 아닌지를 확인

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

스택의 push 알고리즘

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

배열과 비교하면 그림을 가로로 그리냐 세로로 그리냐의 차이

스택의 구현

프로그램에서 스택을 구현하기 위해 필요한 것 → 자료구조(저장소) + 연산

자료를 선형으로 저장할 저장소 : 배열을 사용할 수 있음

저장소 자체를 스택이라 부르기도 한다.

스택에서 마지막으로 삽입된 원소의 위치를 top이라 부른다. (=리스트 마지막 원소의 인덱스를 저장하는 변수인 셈)

사실상 파이썬에서는 list가 스택이랑 똑같이 구현되어 있는 셈이다.

스택의 push = 리스트의 append

스택의 pop = 리스트의 pop

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();
    # 용량이 부족한 거 밝히려는 디버깅 목적이 아니라면 그냥 바로 pop 호출해도 된다.

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

풀어 쓰면 이런 느낌 22

print(pop())

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

스택 연습하기

def push(n):
    global top  # 글로벌 변수 지정해주기!
    top += 1
    if top == size:
        print('overflow!')  # out of range 아니다!
    else:                   # 저장공간이 넘치는건 오버플로우라고 한다.
        stack[top] = n

top = -1
size = 10
stack = [0] * size    # 최대 10개 푸시 가능

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

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

push(30)    # push (30)

# 싹~ 다 꺼내기
while top >= 0:
    top -= 1
    print(stack[top+1])

스택 구현 고려 사항

1차원 배열을 사용해서 구현하면 구현이 용이한 대신 스택 크기 변경이 어렵다는 단점이 있다.

동적 연결리스트를 이용해서 구현하면 이런 단점을 극복할 수 있지만 구현이 복잡하다.

스택을 이용한 괄호 검사

여는 괄호를 넣을 때 스택에 삽입해서 저장

괄호를 닫을 때 top에 있는 괄호를 꺼내서 짝이 맞는지 비교

이때 괄호 짝이 맞지 않거나 스택에서 꺼낼 괄호가 없이 비어있으면 오류!

또는 괄호 수식이 끝났는데 스택에 괄호가 남아있어도 오류!

괄호는 반드시 짝이 있고 가장 마지막에 쓴 괄호부터 닫기 때문에 스택의 특성과 맞물리는 것.

스택의 응용 : function call

프로그램에서의 함수 호출과 복귀에 따른 수행 순서를 관리

→ 가장 마지막에 호출된 함수가 가장 먼저 실행을 완료하고 복귀하는 후입선출 구조이므로, 스택을 이용하여 수행순서를 관리할 수 있다.

함수 호출이 발생하면 호출한 함수 수행에 필요한 지역 변수, 매개 변수 및 수행 후 복귀할 주소 등의 정보를 스택 프레임에 저장하여 시스템 스택에 삽입한다.

스택의 top = 현재 실행 중인 함수

함수의 실행이 끝나면 시스템 스택의 top 원소(스택 프레임)를 삭제(pop) 하면서 프레임에 저장되어 있던 복귀 주소를 확인하고 복귀한다.

함수 호출과 복귀에 따라 이 과정을 반복하여 전체 프로그램 수행이 종료되면 시스템 스택은 공백 스택이 된다.

재귀 호출

필요한 함수가 자신과 같으면 자신을 다시 호출하는 구조

재귀 호출 방식을 사용하면 프로그램의 크기를 줄이고 간단하게 작성할 수 있다.

구조적으로는 다른 함수를 호출하는 것과 동일하다. 실제로 메모리도 같은 걸 쓰는게 아니라 함수가 호출되면서 별도로 만들어진다. 즉, 그냥 다른 함수 호출한다고 보는게 더 편하고 그게 맞다.

재귀 호출의 예) factorial

또 다른 재귀 호출의 예 : 피보나치 수열

0과 1로 시작하고 이전 두 수의 합을 다음 항으로 하는 수열

재귀 함수로 구현해보면?

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

fibo(2) = 1 + 0

Memoization

피보나치 수열을 재귀 함수로 구현하면 중복호출이 어마어마하게 많아지는 문제가 있다.

메모이제이션은 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 실행속도를 빠르게 하는 기술이다.

Memoization 방법을 적용한 피보나치 수열 알고리즘

# 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)  # n 까지 있어야 해서 (n+1) 개를 할당함.
memo[0] = 0
memo[1] = 1

재귀함수와 메모이제이션 사용 시 시간 차이

import time

# 재귀함수 이용
def fibo(n):
    global cnt
    cnt += 1
    if n < 2:
        return n
    else:
        return fibo(n - 1) + fibo(n - 2)

# Memoization 이용
def fibo1(n):
    global cnt
    cnt += 1
    # global memo
    # if n >= 2 and memo[n] == 0:
    #     memo[n] = fibo1(n - 1) + fibo1(n - 2)
    # return memo[n]
    if n != 0 and memo[n] == 0:
        memo[n] = fibo1(n - 1) + fibo1(n - 2)
    return memo[n]

n = 35

cnt = 0
start_fibo = time.time()
ans = fibo(n)
end_fibo = time.time()
print(f'fibo {ans} cnt: {cnt} {end_fibo - start_fibo:.5f} sec')

cnt = 0
start_fibo1 = time.time()
memo = [0] * (n + 1)
memo[0] = 0
memo[1] = 1
ans = fibo1(n)
end_fibo1 = time.time()
print(f'fibo1 {ans} cnt: {cnt} {end_fibo1 - start_fibo1:.5f} sec')

stack 구현하기 (보충)

# 미리 크기가 결정된 저장 공간을 생성
size = 3
stack = [0] * size     # 저장공간
top = -1

def push(item):
    global top
    # 스택이 꽉 찼는지 확인하기
    if top == size - 1:
        # 적절히 조치 (사용자에게 알려주는 등)
        # 함수를 호출한 쪽에 상황을 알린다.
        return
    top += 1
    stack[top] = item

def pop():
    global top
    # 꺼내올 것이 없는 경우 체크가 필요
    # empty check 필요
    if top == -1:
        # 적절한 조치
        return
        # 보통은 이렇게 안에서 안하고 pop 하기 전에 empty 함수를 써서 확인한다고 함
    ret = stack[top]
    # top 을 감소시키고 나서 리턴해줄거라 미리 리턴할 값을 저장
    top -= 1
    return ret

def isEmpty():
    return top == -1

stack 을 구현하기가 힘들다?

그럼 list 써서 그냥 append, pop 써도 된다.

IM, A형 등급까지는 괜찮다! 속도 차이도 별로 안남.

S = []  # 빈 스택
arr = [10, 20, 30]
for val in arr:
    S.append(val)

while S:
    print(S.pop())

조합의 재귀적 정의

def comb(n, r):
    if r == 0 or n == r:
        return 1
    return comb(n-1, r-1) + comb(n-1, r)

print(comb(5, 3))