스택(Stack)

1. 스택

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

• 선형 구조: 자료 간 관계가 1:1, 즉 한 줄로 늘어선 형태. 다른 요소의 앞과 뒤를 통해 표현된다.
  • 비선형 구조는 자료 간 관계가 1:N 또는 N:M 관계
• LIFO(후입선출): 자료를 넣은 역순으로 자료를 꺼낼 수 있다.

 

자료구조

마지막으로 저장된 요소의 위치를 'top'이라고 부른다.

 

연산

1) 저장(삽입): "push"

2) 삭제: 꺼내는 것. "pop"

3) 공백인지 확인: "isEmpty"

공백이 아닌지 확인: "isNotEmpty" (주로 isEmpty가 없어서 !isEmpty로 활용하지 못할 때 사용)

4) top 요소를 읽어오기: "peek" (※ 꺼내는 것 아님)

 

스택의 구현

• 공백 스택: 요소가 없으니 top은 바닥을 가리킴 (top의 초기값은: -1)
• push가 들어오면
  • i) top이 가리키는 자리를 이동시키고, ii) 가리키는 자리에 요소를 저장한다.
• pop이 들어오면
  • i) top이 가리키는 요소를 꺼내고, ii) top을 감소시킨다.
  • 또는 i) top을 감소시키고, ii) top+1 의 요소를 반환한다.
    • top의 자리만 이동시켜도 된다. 나중에 push할 때 새롭게 top이 가리키는 자리에 새 요소가 들어와 대체할 수 있기 때문이다. (stack pointer을 이용하는 방법)
• 주로 스택의 크기를 미리 정해두고 사용한다. (예: 0으로 채워진 리스트)
  • 크기를 미리 정해둔 스택을 사용할 경우, 스택이 꽉 차면 더 이상 push 할 수 없고, 비어있으면 pop이 안 된다. (스택의 크기를 정해두지 않는다면 .append()를 이용하여 push할 수 있다.)

 

※ 참고

1차원 배열을 사용할 경우, 구현하기 용이하지만 스택의 크기를 변경하기 어렵다는 단점이 있다.
⇒ 동적 연결리스트를 활용하여 저장소를 동적으로 할당하는 방법을 사용할 수 있다. 이는 메모리 상에서 실제로 연결된 형태 대신에, 떨어진 덩어리를 만들어 연속된 공간이 아니라 분리된 공간에, 다음 정보의 위치에 대한 정보를 포함하여 저장하는 방법이다. 이 방법은 구현이 복잡하지만 메모리를 효율적으로 활용할 수 있도록 해준다.

 

스택의 응용: 괄호검사

정상적인 괄호 쌍이 되기 위해서는:

• 여는 괄호와 닫는 괄호의 개수가 일치해야 한다.
• 여는 괄호가 먼저 나온 상태에서 닫힌 괄호가 나와야 한다.
• 여는 괄호와 닫는 괄호의 종류가 일치해야 한다.

 

해법

• 여는 괄호((, {)가 나오면 스택에 push하고, 닫는 괄호가 나오면 스택에서 요소를 pop한다.
  • pop 했을 때, 반환되는 괄호와 해당 괄호의 종류가 같아야 한다.
• 모든 요소의 push, pop이 끝난 후 stack은 모두 비어있어야 한다.

 

스택의 응용: function call

프로그램에서 함수 호출과 복귀에 따른 수행 순서를 관리할 때에도 스택 구조가 활용된다.

• 가장 마지막에 호출된 함수가 결과값을 상위 함수에 반환하고 실행을 완료, 복귀하는 LIFO 구조
• 함수 호출이 발생하면, 함수의 변수 및 복귀 주소 등의 정보가 스택 프레임(stack frame)에 저장되어 시스템 스택에 삽입된다. 실행이 끝나면, 스택 프레임이 삭제되며 복귀 주소로 돌아간다.
• 전체 프로그램이 수행되고 나면 스택 프레임은 공백이 된다.

 

 

2. 재귀호출

똑같이 생긴 함수를 여러 번 호출하는 것 (자기 자신을 호출하여 순환 수행)

• 호출 부분과 중단되는 부분(base case)으로 구성되어야 한다. 그래서 주로 if~ else~ 구문으로 되어 있다.
• 함수를 간단하게 작성할 수 있지만, 깊이가 깊어지면 수행시간이 기하급수적으로 증가한다.
• 증가하는 방향으로 재귀호출을 한다면, 접근할 위치와 경계값을 같이 넘겨준다.
• 예) 배열에 접근 — 접근할 위치, 배열의 크기, 찾으려는 값을 전달

 

3. Memoization

재귀함수의 '중복 호출 문제'에 대처하기 위한 방법

• 컴퓨터 프로그램을 실행할 때, 이전 계산의 결과값을 메모리에 저장하여 같은 계산을 반복하지 않도록 함으로써 실행속도를 향상시키는 기술
• 동적계획법(DP)의 핵심

 

예) 피보나치

def fibo_m(n):
    global memo
    if n >= 2 and len(memo) <= n:
        memo.append(fibo(n-1) + fibo(n-2)) # 리스트 memo에 계산에 활용할 수 있는 이전값이 저장됨
    return memo[n]

memo = [0, 1]

 

4. DP (Dynamic Programming, 동적 계획법)

최적화 알고리즘으로, 작은 부분 문제들을 해결함으로써 큰 문제를 해결하는 알고리즘

• 반복 구조, 저장된 값에 접근, 길이만큼만 연산하면 됨
• 구현 방식
  • recursive: 재귀 사용
  • iterative: 반복구조 (일반적인 DP)

 

방법

1) 수식으로 정리한다.
2) 구현 방법을 궁리한다 (어떤 게 적절할지)

 

예) 피보나치

def fibo_d(n):
    f = [0, 1]
    for i in range(2, n+1):
        f.append(f[i-1] + f[n-2]))
    return f[n]

 

5. DFS (Depth First Search, 깊이 우선 탐색)

시작 정점의 한 방향으로 갈 수 있을 때까지 깊이 탐색하다가, 갈 곳이 없으면 가장 최근에 지나온, 갈림길이 있는 정점으로 돌아와, 다른 방향으로의 탐색을 반복하여 모든 정점을 방문하는 순회방법

• 탐색과 가장 최근의 정점으로 돌아가기를 해야 하므로, LIFO 구조의 스택을 사용할 수 있다.
• 참고: BFS (Breadth First Search, 너비 우선 탐색)

• 스택을 썼기 때문에 DFS가 아니라, 경로를 후입선출로 꺼내기 위해 스택을 사용할 수 있다는 사실!

 

스택을 사용한 DFS 알고리즘

준비물: stack, visited 배열, 시작점 v

1) 시작 정점 v를 결정한다. (문제에 따라 모든 점에서 각각 시작해 봐야 할 수도 있다.)
2) 직접 연결된 정점 중에서
  (1) 방문 여부는 visited 배열로 관리한다.
  (2-1) 방문하지 않은 정점 w가 있으면
    → v 를 스택에 넣고, w 를 새로운 v 로 설정하여 반복한다.
  (2-2) 방문하지 않은 정점이 없으면
    → 최근 정점으로 되돌아가기 위해 스택에서 pop한 정점을 v로 설정하고 반복한다.
3) 스택이 공백이 될 때까지 반복한다.

※ 참고: 재귀로 DFS를 할 때는 스택을 사용하지 않는다. 이전 호출 단계에 방문 경로가 저장되어 있기 때문이다.

 

6. 계산기

스택을 통해 문자열로 표현된 계산식을 계산할 수 있다!

1) 중위 표기법을 후위 표기법으로 바꿔 표현한 후,
2) 스택을 활용해 계산값을 도출한다.

후위 표기법(postfix notation)

피연산자(operand) 사이에 연산자(operator)를 표기하는 중위표기법과 달리, 피연산자 뒤에 연산자를 표기하는 방법

(예) 53*

후위 표기법으로 바꾸는 방법

문자열을 앞에서부터 읽어오며

1) 피연산자면, 그대로 출력한다.
2) 연산자면,

  (1) 스택이 비어있거나, 스택의 마지막 연산자보다 우선순위가 높으면 → 스택에 추가한다.

  (2) 스택의 마지막 연산자보다 우선순위가 낮거나 같으면
  → 더 낮은 우선순위의 연산자가 나오거나, 스택이 빌 때까지 요소를 pop하여 출력한다.
  그리고 해당 연산자를 스택에 추가한다.
  👉 확인해보기: 블로그 글

(3) 문자열이 끝났을 때, 스택에 남은 연산자가 있다면 모두 pop해서 출력해준다.

• 우선순위 (*숫자가 클수록 높은 것)

 

후위 표기법으로 표현된 수식을 계산하는 방법

1) 피연산자라면, 스택에 추가한다.
2) 연산자라면, 연산자에 필요한 만큼의 피연산자를 스택에서 pop하여 (사칙연산은 2개), 먼저 꺼낸 피연산자를 연산자의 우측에 두고, 나중 피연산자를 연산자의 좌측에 두어 계산한 결과를 스택에 추가한다.
3) 수식이 끝나면, 스택에 마지막으로 남은 값을 pop한다 → 결과
※ 참고: 파이썬의 eval() 함수

 

7. 백트래킹(Backtracking)

어떤 노드의 유망성을 점검하여, 유망하지 않다면 부모 노드로 돌아가 다음 자식 노드로 가는 것.

해답의 가능성이 있으면 유망한 것, 없으면 유망하지 않다.

※ 가지치기(pruning): 유망하지 않은 노드가 포함된 경로는 더 이상 고려하지 않는다.

• 재귀를 이용한 DFS에 대한 이해가 되어 있어야 한다.
• 최적화(optimisation) 문제와 결정(decision) 문제를 해결할 수 있다.
  • 최적화 문제: 최단거리 등
  • 결정 문제: 문제의 조건을 만족하는 해가 존재하는지 여부를 답하는 문제(Y/N)
    • 미로 찾기, n-Queen, Map coloring, 부분집합의 합 등

 

(예) 미로 찾기

DFS에서처럼, 현재의 위치 $v$와 갈 위치 $w$를 정하고, visited 배열을 기록하고, 지나간 경로를 스택에 저장한다.

더 이상 진행할 수 없으면, 경로를 거슬러 다른 방향으로 진행할 수 있는 상태로 되돌아가는 것이 핵심이다.

사방을 순서대로 탐색하여 가능한 새로운 경로를 탐색할 수 있다.

 

백트래킹과 DFS의 차이

백트래킹은 노드가 유망하지 않으면 해당 경로에 대한 탐색을 중단함으로써, 전체 시도 횟수를 줄인다.
즉, 불필요한 경로를 조기에 차단함으로써 경우의 수를 줄일 수 있다.
다만, 일반적으로 경우의 수가 줄지만, 최악의 경우에는 여전히 지수함수 시간을 요한다.

 

백트래킹 방법

DFS를 실시하고, 중간에 노드의 유망성을 점검하는 조건식을 통해 점검하여, 노드가 유망하지 않으면 부모 노드로 돌아가 다른 경로로 검색을 실시한다.