[Algorithm] Stack의 활용 : 그래프, DFS, 계산기

TOC

• 그래프 구조
  • DFS
  • DFS 알고리즘
  • DFS 구현
• 계산기
  • 중위표기식 → 후위표기식 1 : 손으로 하나하나
  • 중위표기식 → 후위표기식 2 : 스택 이용
  • 후위표기식 → 중위표기식
  • 우선순위 고려한 구현 코드

그래프 구조

• 실세계의 모습을 추상화하는 도구
• 정점(vertex, V)들과 간선(edge, E)들의 집합
• 동등한 관계(쌍방) - 의존적 관계(일방)
• 비선형구조인 그래프 구조는 그래프로 표현된 모든 자료를 빠짐없이 검색하는 것이 중요

그래프의 저장

• 간선들의 정보를 저장하는 것

• 각 정점마다 인접정점들의 정보 저장

• 간선 하나의 표현에는 두 정점의 정보가 필요

• V : 정점들의 집합, |V|: 정점수, E : 간선들의 집합, |E| : 간선수

• 인접 행렬

  • 양방향인 경우
  • |V| x |V| 크기의 2차원 배열에 저장
  • 정점의 개수가 많아질수록 메모리 사용, 연산 시간이 커진다.

• 인접 리스트

  • 일방향인 경우
  • 특정 정점을 인덱스로 하는 리스트에 도착 정점 번호 자체를 저장
  • 연산시간과 메모리 부분에서 인접 행렬보다 효율적

• 간선들의 리스트

그래프의 구분

• 깊이 우선 탐색(DFS; Depth First Search)
• 너비 우선 탐색(BFS; Breadth First Search)

DFS

• 시작 정점의
• 가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색 반복
• 후입선출(LIFO) 구조의 스택 사용

DFS 알고리즘

• 시작 정점 v를 결정하여 방문
• 정점 v에 인접한 정점 중에서
  • 방문하지 않은 정점 w가 있으면, 정점 v를 스택에 push하고 w를 방문
  • w를 v로 하여 다시 반복
  • 방문하지 않은 정점이 없으면, 탐색의 방향을 바꾸기 위해 스택 pop
  • 가장 마지막 방문 정점을 v로 하여 다시 반복
• 스택이 공백이 될 때까지 반복

DFS 구현

• stack은 출발 정점부터 이동 경로를 저장
• 어느 노드를 도착했을 때 해당 노드와 연결된 방문하지 않은 다른 노드가 있다면 노드를 스택에 push
• 방문하지 않은 연결된 다른 노드를 방문함과 동시에 visited 배열에 True를 표시
• 어느 노드를 방문했는지의 여부는 False인지 아닌지 확인하면 된다.
• 어느 노드에 도착했을 때 추가로 방문할 수 있는 노드가 없다면 stack의 마지막을 pop해서 다시 이동 가능 노드를 확인
• 스택이 모두 비면 다시 처음으로 돌아가는 것

계산기

• 문자열로 된 계산식이 주어질 때, 스택을 이용해 계산 가능
• 문자열 수식 계산의 일반적 방법
  • 중위 표기법의 수식을 후위 표기법으로 변경(스택 이용)
  • 후위 표기법의 수식을 스택을 이용하여 계산

중위 표기법(infix notation) : A+B
후위 표기법(postfix notation) : AB+

중위표기식 → 후위표기식 1 : 손으로 하나하나

• 각 연산자에 대해서 우선순위에 따라 괄호 사용하여 다시 표현
• 각 연산자를 그에 대응하는 닫는 괄호의 뒤로 이동
• 괄호 제거

A*B-C/D

step 1. ((A*B)-(C/D))
step 2. ((AB)*(CD)/)-
step 3. AB*CD/-

중위표기식 → 후위표기식 2 : 스택 이용

• 입력 받은 중위 표기식에서 토큰 읽기

• 토큰은 수식을 구성하는 연산자나 피연산자 하나하나를 의미

• 토큰이 피연산자이면 토큰 출력

• 토큰이 연산자(괄호포함)일 때

  • 우선순위 : 토큰 > stack[top]의 연산자 → 스택에 push
  • 우선순위 : 토큰 < stack[top]의 연산자 → 토큰이 더 커질 때까지 stack에서 pop후 토큰의 연산자 push
  • 만약 top에 연산자가 없으면 push

• 토큰이 ')'이면 스택 top에 왼쪽 괄호 '('가 올 때까지 스택에 pop 연산 수행

• pop한 연산자 출력

• 왼쪽 괄호 만나면 pop만 하고 출력하지는 않는다.

• 중위 표기식에 더 읽을 것이 없다면 중지

• 더 읽을 것이 있다면 처음부터 다시 반복

• 스택에 남아있는 연산자를 모두 pop하여 출력

• 스택 밖의 왼쪽 괄호는 우선순위가 가장 높다. 스택 안의 왼쪽 괄호는 우선순위가 가장 낮다.

• 열린 괄호가 닫히기 전에 또 열린 괄호가 스택에 들어오는 경우 괄호 밖에서는 우선순위가 가장 높으므로 일단 스택에 들어와서 가장 낮은 우선순위로 초기화

후위표기식 → 중위표기식

• 피연산자를 만나면 스택에 push
• 연산자를 만나면 필요한 만큼의 피연산자를 스택에서 pop하여 연산
• 연산결과를 다시 스택에 push
• 수식이 끝나면 마지막으로 스택을 pop하여 출력

우선순위 고려한 구현 코드

icp(incoming priority) = {'+':1, '*':2, '(':3}
isp(instack priority) = {'(':0, '+':1, '*':2}

N = int(input())
infix = input()
postfix = []
stack = []

for token in infix:
    if token in icp:
        while stack and isp[stack[-1]] >= icp[token]:  # 스택이 비어있지 않아야 한다는 조건 필수
            postfix.append(stack.pop())
        stack.append(token)
    else:
        postfix.append(token)

while stack:
    postfix.append(stack.pop())

for token in postfix:
    if token in icp:  # 연산자인 경우
        b = stack.pop()
        a = stack.pop()

        if token == '+':
            stack.append(a+b)
        elif token == '*':
            stack.append(a*b)
    else:             # 피연산자인 경우
        print(stack.pop())