알고리즘 정리 - 스택

jonghyuck’s velog·2022년 8월 21일
알고리즘
0

알고리즘

목록 보기
5/5

💿 Stack
🔍 스택의 활용 예시
Memoization
DP(Dynamic Programming)

💿 Stack

스택이란?

  • 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조
  • 스택에 저장된 자료는 선형 구조를 갖는다
    • 선형 구조 : 자료 간의 관계가 1:1의 관계를 갖는다
    • 비선형 구조 : 자료 간의 관계가 1대 N의 관계를 갖는다(예: 트리)
  • 스택에 자료를 삽입하거나 스택에서 자료를 꺼낼 수 있다.
  • 마지막에 삽입한 자료를 가장 먼저 끄낸다(LIFO, Last-In-First-Out)

특징

  1. 자료를 선형으로 저장할 저장소 필요
  2. 저장소 자체를 스택이라 부르기도 한다.
  3. 스택에서 마지막 삽입된 원소의 위치를 top이라고 부른다.

연산

  • 삽입 : 저장소에 자료를 저장한다. 보통 push라고 부른다.
  • 삭제 : 저장소에서 자료를 꺼낸다. 꺼낸 자료는 삽입한 자료의 역순으로 꺼낸다. 보통 pop이라고 부른다.
  • 스택이 공백인지 아닌지를 확인하는 연산 = isEmpty
    • 비어 있으면 True, 하나라도 채워있으면 False
  • 스택의 top에 있는 원소를 반환하는 연산 = peek

python code


# 스택구현해서 값 넣어보기
# class로 구현해보기 
class Stack:
    '''
    속성 : 실제 데이터를 저장할 배열(리스트) - 고정길이,top
           마지막 원소를 가리키는 변수 ( Stack pointer )
    기능 : push, pop, peek, size, is_Empty
    '''
    def __init__(self, length):
        self.stack = [None]*length
        self.top = -1
        '''
        top의 초기화 값 : -1 default
        '''
    # 요소를 stack 마지막에 저장하고, 만약에 가득차서 못넣을 경우, 'overflow' 출력
    def push(self, val):
        if self.is_full():
            print('overflow')
        else:
            self.top += 1
            self.stack[self.top] = val

    # 마지막 요소를 삭제하고, 반환, 요소가 없는 경우 'underflow' 출력
       def pop(self):
        if self.is_empty():
            print('underflow가났습니다.')
            return None
        else:
            self.top -= 1
            return self.stack[self.top + 1]
            

    # 마지막 요소를 반환, 요소가 없으면 'underflow'
    def peek(self):
        if self.is_empty():
            print('underflow가났습니다.')
            return None
        else:
            return self.stack[self.top]

    # 현재 요소의 개수 반환
    def size(self):
        return self.top+1
    

    def is_empty(self):
        if self.top == -1:
            return True
        return False

    # 요소가 가득 찼으면 True, 아니면 False
    def is_full(self):
        if self.top == len(self.stack)-1:
            return True
        return False

my_stack = Stack(10)
my_stack.push(1)
my_stack.push(2)
my_stack.push(3)
my_stack.push(4)
my_stack.push(5)
my_stack.push(6)
my_stack.push(7)
my_stack.push(8)
my_stack.push(9)
my_stack.push(10)
print(my_stack.pop())
print(my_stack.pop())
print(my_stack.pop())
print(my_stack.pop())
print(my_stack.pop())
print(my_stack.pop())
print(my_stack.pop())
print(my_stack.pop())
print(my_stack.peek(), my_stack.size(), my_stack.is_full(), my_stack.is_empty())

🔍 스택의 활용 예시

Function call

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

재귀 호출

  • 자기 자신을 호출하여 순환이 수행되는 것
  • 함수에서 실행해야 하는 작업의 특성에 따라 일반적인 호출방식보다 재귀 호출방식을 사용하여 함수를 만들면 프로그램의 크기를 줄이고 간단하게 작성 가능

factorial 함수에서 n=4인 경우의 실행

피보나치를 구하는 재귀함수 (python code)

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

Memoization

재귀함수로 앞에서 피보나치를 구하는 함수를 작성했는데, 여기에는 큰 문제가 있다.
바로, fibo함수의 호출 수가 커질수록 ”엄청난 중복 호출이 존재” 하게 된다는 것이다.

이 문제를 해결하기 위해서 아주 간단한 아이디어를 사용하면 된다.
바로, 프로그램이 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술이다. == Memoization

이는, 동적 계획법의 핵심이 되는 기술이다.

Memoization을 활용한 fibo함수 (python code)

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

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]

DP(Dynamic Programming)

앞에서 Memoization을 공부하며 동적 계획법의 핵심이 되는기술 이라는 표현을 사용햇는데, 그렇다면 동적계획(Dynamic Programming)이란 뭘까?

  • 동적 계획이란 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘이다.
  • 동적 계획 알고리즘은 먼저 입력 크기가 작은 부분 문제들을 모두 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여, 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘이다.

피보나치 DP 적용

  • 피보나치 수는 부분 문제의 답으로부터 본 문제의 답을 얻을 수 있으므로 최적 부분 구조로 이루어져 있다.
  1. 문제를 부분 문제로 분할한다.
  • Fibo(n)함수는 Fibo(n-1), Fibo(n-2)의 합
  • Fibo(n-1)함수는 Fibo(n-2), Fibo(n-3)의 합
  • Fibo(n) = Fibo(n-1) + Fibo(n-2) + … + Fibo(1) + Fibo(0)
    Fibo(n)함수는 위와 같은 부분집합으로 나뉜다.

  1. 부분 문제로 나누는 일을 끝냈으면 가장 작은 부분 문제부터 해를 구한다.

  2. 그 결과는 테이블에 저장하고, 테이블에 저장된 부분 문제의 해를 이용하여 상위 문제의 해를 구한다.

테이블 인덱스저장되어 있는 값
[0]0
[1]1
[2]1
[3]2
[4]3
[5]5
[6]8
……
[n]fibo(n)

피보나치 DP 적용 알고리즘(python code)

def fibo2(n):
    f = [0, 1]

    for i in range(2, n + 1):
        f.append(f[i+1] + f[i-2])

return f[n]

DP 구현 방식

  1. recursive( 재귀) : fibo1()
  2. iterative : fibo2()
  • memoization을 재귀적 구조에 사용하는 것보다 반복적 구조로 DP를 구현한것이 성능 면에서 보다 효율적이다.
  • 재귀적 구조는 내부에 시스템 호출 스택을 사용하는 오버헤드가 발생하기 쉽기 때문
profile
jonghyuck’s velog
:)
이전 포스트

알고리즘 정리 - 문자열(String)

0개의 댓글