[알고리즘 기초] 04_Stack 1 / Python

[알고리즘 기초] 04_Stack 1 / Python

[알고리즘 기초] 04_Stack 1 / Python

1. Stack(스택)

• 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조 이다.
• 스택에 저장된 자료는 선형 구조를 갖는다.
  • 선형구조 : 자료 간의 관계가 1대 1의 관계를 갖는다.
  • 비선형구조 : 자료 간의 관계가 1대 N의 관계를 갖는다. (ex. 트리 구조)
    • 트리구조: 트리구조는 가지치기형으로 생긴 구조이다. 부모자식 관계로 형성.

• 스택에 자료를 삽입하거나 스택에서 자료를 꺼낼 수 있다.
• 마지막에 삽입한 자료를 가장 먼저 꺼낸다. LIFO(후입선출) 이라고 부른다.
  • ex) 1, 2, 3 순으로 삽입 -> 3, 2, 1 순으로 꺼낼 수 있음

 

2. 스택의 구현

- 스택을 프로그램에서 구현하기 위해 필요한 자료구조와 연산

• 자료구조: 자료를 선형으로 저장할 저장소
  • C언어 - 배열
  • 저장소 자체를 스택이라 부르기도 한다.
  • 스택에서 마지막 삽입된 원소의 위치를 top이라 부른다.
• 연산
  • 삽입: 저장소에서 자료를 저장한다. 보통 push
  • 삭제: 저장소에서 자료를 꺼낸다. 꺼낸 자료는 삽입한 자료의 역순, 보통 pop
  • 스택이 공백인지 확인하는 연산 - .isEmpty
  • 스택의 top에 있는 item(원소)를 확인하는 연산(꺼내지는 않음) - .peek

 

- 스택의 삽입/삭제 과정

• 빈 스택에서 원소 A,B,C를 차례로 삽입 후 한번 삭제 하는 연산과정
  1. stack = none, top = none
  2. push A, top = 0
  3. push B, top = 1
  4. push C, top = 2
  5. pop C, top = 1

 

3. 스택 구현 고려 사항

• 1차원 배열을 사용하여 구현할 경우 구현이 용이하다는 장점이 있지만 스택의 크기를 변경하기가 어렵다는 단점이 있다.
• 이를 해결하기 위하여 저장소를 동적으로 할당하여 스택을 구현하는 방법이 있다. 동적 연결리스트를 이용하여 구현하는 방법을 의미한다.

 

 

4. 스택의 구현: Funtion call

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

 

5. 재귀호출

• 자기 자신을 호출해서 순환 수행되는 것
  1. factorial : n에 대한 factorial : 1부터 n까지의 모든 자연수를 곱하여 구하는 연산
  2. 피보나치 수열 : 0과 1로 시작하고 이전의 두 수 합을 다음 항으로 하는 수열

# 피보나치 재귀함수 - 중복 호출 존재
def fibo(n):
    if n < 2:
        return n
    else:
        return fibo(n-1) + fibo(n-2)

 

 

 

6. Memoization

• 메모이제이션은 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 실행속도를 빠르게 하는 기술
• Memoization - '메모리에 넣기'
• 피보나치 수를 구하는 알고리즘에서 fibo(n)의 값을 계산하자마자 저장하면 실행시간을 O(n)으로 줄일 수 있다.

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

memo = [0, 1]

 

 

7. DP(Dynamic Programming)

• 동적 계획(Dynamic Programming) 알고리즘은 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘이다
• 먼저 입력 크기가 작은 부분 문제들을 모두 해결한 후에 그 해들을 이용하여 큰 크기의 부분 문제들을 해결, 최종적으로 주어진 문제를 해결하는 알고리즘
• 피보나치 수 DP 적용
  1. 문제를 부분 문제로 분할
     • fibo(n) = fibo(n-1) + fibo(n-2)
     • fibo(n-1) = fibo(n-2) + fibo(n-3)
     • ...
     • fibo(2) = fibo(1) + fibo(0)
     • fibo(n) 은 fibo(n-1), fibo(n-2), ..., fibo(2), fibo(1), fibo(0)의 부분집합으로 나뉜다
  2. 가장 작은 부분 문제부터 해를 구한다
  3. 그 결과는 테이블에 저장하고, 테이블에 저장된 해를 이용하여 상위 문제의 해를 구한다. (bottom-up)

 

#피보나치 수 DP 적용 알고리즘
def fibo(n):
    f = [0, 1]
    
    for i in range(2, n+1):
        f.append(f[i-1] + f[i-2])
        
    return f[n]

Table Index	저장되어 있는 값
[0]	0
[1]	1
[2]	1
[3]	2
[4]	3
...	...
[n]	fibo(n)

 

• DP의 구현 방식
  • recursive 방식 : fib1()
  • iterative 방식 : fib2()
• memoization을 재귀적 구조에 사용하는 것보다 반복적 구조로 DP를 구현한 것이 성능 면에서 보다 효율적이다
• 재귀적 구조는 내부에 시스템 호출 스택을 사용하는 오버헤드가 발생하기 때문이다.
• 비선형구조인 그래프 구조는 모든 자료를 빠짐없이 검색하는 것이 중요함
• 두 가지 방법
  • 깊이 우선 탐색 (Depth First Search, DFS)
  • 너비 우선 탐색 (Breadth First Search, BFS)
• 가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택 사용