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

그래프의 저장

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

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

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

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

  • 인접 행렬

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

  • 인접 리스트

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

  • 간선들의 리스트


그래프의 구분

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

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

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

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

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

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

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

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

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

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

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

    • 우선순위 : 토큰 > 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())