백준(BaekJoon) 1918번 풀이 - [AP 프로그래밍 - 4월 과제]

(3월 과제)

2024.03.23 - [프로그래밍/문제 풀이] - 백준(BaekJoon) 17951번 풀이 - [AP 프로그래밍 - 3월 과제]

백준(BaekJoon) 17951번 풀이 - [AP 프로그래밍 - 3월 과제]

 

이번 4월달 과제는 자료구조입니다. 자료구조 문제 중 1918번을 풀어보도록 하겠습니다.

https://www.acmicpc.net/problem/1918

1918번: 후위 표기식

---

사전 탐구

4월 과제의 주제는 '자료구조'입니다. 따라서 자료구조에 대해 먼저 간략하게 알아보겠습니다.

 

자료구조는 데이터를 효율적으로 사용할 수 있도록 정리하는 방법을 말합니다. 각각의 자료구조에는 모두 장단점이 존재하여 어떤 자료구조를 선택해 문제를 풀지를 정하는 것이 굉장히 중요한 요소라고 할 수 있습니다. 

 

자료 구조의 종류는 다음과 같습니다.

자료 구조의 종류

 

자료구조는 여러 속성을 기반으로 분류할 수 있으며, 데이터의 연결 방식을 기준으로 크게 선형 자료구조와 비선형 자료구조로 나눌 수 있습니다.

 

선형 자료구조 (Linear Data Structure)는 데이터 요소를 순서대로 정렬하는 구조로 배열, 리스트, 큐, 스택 등이 여기 포함됩니다. 선형 자료구조는 개별 요소 하나하나에 접근하는 과정에 대해 더 효율적이고, 데이터의 순회가 쉬워 요소 전체를 변경하기가 쉽습니다.

비선형 자료구조 (Nonlinear Data Structure)는 데이터를 비연속적으로 연결하는 구조로 트리, 그래프 등이 여기 포함됩니다. 비선형 자료구조는 선형 자료구조와 달리 데이터의 저장, 호출 등이 중점이 아닌 자료의 표현이 중점입니다. SNS 상의 데이터 등은 비선형 자료구조로 표현하는 것이 더 효율적입니다.

 

자료구조는 크기의 고정성에 따라 정적 자료구조와 동적 자료구조로 나뉘기도 합니다.

정적 자료구조 (Static Data Structure)는 크기가 고정되어 있는 자료구조로, 반드시 일정량의 메모리를 할당해야 합니다. 파이썬에는 정적 자료구조가 없으나, C 같은 Low-Level 언어에는 정적 자료구조가 지원됩니다. 정적 자료구조에 요소를 새로 할당하려면 새 자료구조를 만들어 새로 메모리를 할당하고, 여기에 정보들을 옮겨야 하므로 정보들의 개수를 알 수 없다면 정적 자료구조는 좋은 선택이 아닙니다. 그러나, 요소의 개수를 알고 있으면 정적 자료구조가 더 효율적이라고 할 수 있습니다.

 

동적 자료구조 (Dynamic Data Structure)는 크기가 바뀔 수 있는 자료구조입니다. 동적 자료구조에 요소를 새로 할당할 때는 컴퓨터가 스스로 메모리를 할당하고, 덕분에 요소 추가나 제거 과정이 상대적으로 효율적이어서 메모리를 더 효율적으로 사용합니다. 따라서 메모리 공간이 한정적이라면 동적 자료구조가 더 효율적이라고 할 수 있습니다.

---

문제 선정 과정

여러 자료구조의 종류 중 저는 스택을 골라보았습니다. 스택을 고른 이유는 제가 자료구조들 중 가장 많이 접해보기도 했고, 다른 자료구조들은 복잡한 구현을 필요로 하는 반면에 스택은 파이썬의 리스트를 이용해 쉽게 구현할 수 있기 때문입니다. 또, 학교에서 수업 시간에 컴퓨터에 메모리가 스택의 형식으로 저장된다는 것을 배운 기억이 있어 스택 문제를 고르게 되었습니다.

 

그래서 여러 스택 문제들 중 전에 푼 골드 4보다는 난이도가 높되 적당히 재미있어 보이는 문제를 고르기로 했고, 상당히 흥미로워보이는 주제인 '후위 표기식'을 다루는 1918번을 고르게 되었습니다.

---

문제 풀이 전략

이제 문제가 어떻게 생겼는지를 살펴보겠습니다.

백준 1918번 - 후위 표기식

 

문제를 요약해보자면 우리는 주로 연산자를 숫자들 사이에 끼워넣는 중위 표기식을 사용하지만, 연산자를 숫자들 맨 뒤로 보내는 후위 표기식이란 게 있습니다. 중위 표기식이 입력되면 이를 후위 표기식으로 바꿔 출력해주는 것이 이 문제의 목표입니다.

 

이제 문제를 어떻게 풀지 고민해보도록 하겠습니다. 사실 이런 문제들은 주로 코드를 짜는데서 어려움을 겪는게 아닌, 규칙을 찾고 이를 알고리즘으로 만드는 과정이 어려운 것이라 알고리즘만 잘 구현하면 쉽게 해결할 수 있습니다.

 

문제 풀이 전략은 다음과 같습니다.

• 스택 사용 : 연산자들을 따로 저장해두기 위한 스택을 제작. 스택은 (뒤에서 자세히 설명하겠지만) 후입선출 구조이기 때문에, 뒤에 있는 연산자를 꺼내서 쓸 일이 많은 후위 표기식을 구현할 때 효과적으로 이용될 수 있음.
• 연산자 우선순위 설정 : *, /이 +, -보다 먼저 계산되기 때문에 이 두 연산자의 우선순위를 +, -보다 높게 지정해주어 먼저 연산함.
• 알고리즘 구현
  • 문자(A, B, C 등)를 만나면 : 바로 결과식에 추가
  • ' ( '를 만나면 : 괄호 안의 연산자를 먼저 써줘야 하므로 일단 스택에 추가
  • ' ) '를 만나면 : (   ) 사이의 연산자를 먼저 써줘야 함 → 스택 맨 위의 연산자가 ( 이 될 때까지 스택에서 연산자를 빼내서 결과식에 추가
  • ' + ', ' - ', ' * ', ' / '를 만나면 : 스택이 비어있지 않고, 스택 맨 위의 연산자의 우선순위가 현재 연산자의 우선순위보다 크면 스택 맨 위의 연산자를 빼내서 결과식에 추가. 그 후 현재 연산자를 스택에 추가.
  • 입력을 다 받으면 스택에 남은 연산자들을 맨 위부터 차례대로 결과식에 추가

(제가 설명하긴 했지만) 말로만 들으면 무슨 말인지 도저히 이해가 안 되는 설명이므로 간단한 예시를 통해서 보도록 하겠습니다.

 

제가 A*(B+C)-D/E 이라는 중위 표기식을 후위 표기식으로 바꾼다고 가정하겠습니다.

1. A를 만남: A는 연산자가 아니므로, 바로 결과 문자열에 추가합니다.
   •     결과식 : A
   •     스택 : (비어있음)
2. *를 만남: 스택이 비어 있으므로, *를 스택에 추가합니다.
   •     결과식 : A
   •     스택 : *
3. (를 만남: (를 스택에 추가합니다. 괄호 안의 표현식은 우선 처리됩니다.
   •     결과식 : A
   •     스택 : *, (
4. B를 만남: B는 연산자가 아니므로, 바로 결과 문자열에 추가합니다.
   •     결과식 : AB
   •     스택 : *, (
5. +를 만남: (가 우선순위가 없으므로, +를 스택에 추가합니다.
   •     결과식 : AB
   •     스택 : *, (, +
6. C를 만남: C는 연산자가 아니므로, 바로 결과 문자열에 추가합니다.
   •     결과식 : ABC
   •     스택 : *, (, +
7. )를 만남: (를 만날 때까지 스택에서 연산자를 빼내고 결과 문자열에 추가합니다. 그 후 (를 스택에서 제거합니다.
   •     결과식 : ABC+
   •     스택 : *
8. -를 만남: 스택의 맨 위에 있는 * 의 우선순위가 - 보다 높으므로, 스택이 비어 있거나 우선순위가 낮은 연산자를 만날 때까지 스택에서 연산자를 팝하고 결과 문자열에 추가합니다. 그 후 - 를 스택에 추가합니다.
   •     결과식 : ABC+*
   •     스택 : -
9. D를 만남: D는 연산자가 아니므로, 바로 결과 문자열에 추가합니다.
   •     결과식 : ABC+*D
   •     스택 : -
10. /를 만남: 스택의 맨 위에 있는 - 보다 / 의 우선순위가 높으므로, / 를 스택에 추가합니다.
    •     결과식 : ABC+*D
    •     스택 : -, /
11. E를 만남: E는 연산자가 아니므로 바로 결과 문자열에 추가합니다.
    •     결과식 : ABC+*DE
    •     스택 : -, /
12. 입력이 끝남: 스택에 남은 연산자를 순서대로 결과 문자열에 추가합니다.
    •     최종 결과 문자열: ABC+*DE/-

---

자료 구조 설명

스택 (Stack)

스택은 이름에서도 알 수 있듯 '차곡차곡 쌓여진 더미'를 의미합니다. 통 안에 상자들을 넣는다고 생각하면 편한데요. 통 안에 상자들을 넣고 상자를 빼고자 하면 당연히 제일 위에 있는, 즉 제일 늦게 들어간 상자를 뺄 수 밖에 없겠죠. 

 

이렇게 스택은 LIFO(Last In First Out), 즉 후입선출의 형태를 갖는다는 것이 특징입니다.

스택에서 가장 위에 있는 정보를 top이라고 하고, 가장 아래 있는 정보는 bottom이라고 합니다. 따라서 스택에서 뭔가를 빼낼때는 반드시 top에서 빼내야 하죠. 스택에서 뭔가를 빼낼 때는 pop, 뭔가를 넣을 때는 push라는 용어를 사용합니다.

 

스택의 모습

 

위 사진에서 볼 수 있듯, push와 pop 연산을 진행할때마다 스택에서의 top은 계속해서 바뀝니다. 이런 스택은 C++ 등에서는 따로 구현을 해줘야 하지만, 파이썬에서는 리스트를 활용해 정말 간단하게 구현할 수 있습니다.

스택의 명령어	기능	파이썬의 대체어
top()	스택 최상단의 데이터 반환	list[-1]
push()	스택 최상단에 데이터 삽입	list.append()
pop()	스택 최상단의 데이터 삭제 & 반환	list.pop()
isempty()	스택이 비어있으면 'True', 아니면 'False' 반환	len(list) == 0
isfull()	스택이 비어있으면 'False', 아니면 'True' 반환	len(list) != 0

 

이렇게 스택에서 쓰는 모든 명령어들을 파이썬의 리스트로 대체할 수 있으므로, 코드를 짤 때 리스트를 이용할 것입니다.

---

문제 풀이 과정

이제 문제를 풀기 위해 코드를 짜겠습니다.

가장 먼저 중위 표기식을 입력받고, 연산자들의 우선순위를 지정해줍니다. 이때, 연산자 별로 우선순위라는 고유한 값이 지정돼야하므로 딕셔너리를 이용하도록 하겠습니다. +, - 보다 *, / 의 우선순위가 크므로 각각 key 값을 0, 1로 지정하고 (, ) 의 경우에는 -1로 지정해주었습니다. (이유는 후에 설명하도록 하겠습니다.) 그리고 결과식을 저장할 리스트(postfix)와 스택(stack)을 지정하였습니다.

infix = list(input())
operand = {'+' : 0, '-' : 0, '*' : 1, '/' : 1, '(' : -1, ')' : -1}
postfix = []
stack = []

 

그리고 입력받은 식들의 모든 요소에 대해 아까 짠 알고리즘을 적용시키겠습니다.

먼저 만나는 요소가 연산자가 아닐 경우(문자)부터 짜겠습니다. 문자를 만난다면 바로 결과식에 추가하게 하였습니다.

for i in range(len(infix)) :
  if infix[i] not in operand :
    postfix.append(infix[i])

 

이후 만약 ' ( ' 연산자를 만나게 된다면 stack에 추가하는 코드를 짜줬습니다.

else :
  if infix[i] == '(':
    stack.append(infix[i])

 

이제 ' ) ' 연산자를 만났을 때의 코드를 짜보겠습니다. (여기부터 약간 어지러워집니다.)

 

' ) ' 연산자를 만나면 stack이 비어있지 않을 때, stack의 맨 위 요소(이하 stack[-1])가 ' ( '이 될 때까지 stack에서 연산자를 pop하여 결과식에 추가해주어야 합니다. 여기서 while문은 stack[-1]이 ' ( '일 때 끝나므로 스택이 비어있지 않으면 한 번 더 pop을 진행해주어야 합니다.

elif infix[i] == ')' :
  while len(stack) != 0 and stack[-1] != '(' :
    postfix.append(stack.pop())
  if len(stack) != 0 :
    stack.pop()

 

그리고 + - * / 연산자를 만났을 때의 코드를 짜겠습니다.

+ - * / 연산자를 만나면 stack이 비어있지 않을 동안, 현재 연산자의 우선순위가 stack[-1]의 우선순위보다 작으면 stack[-1]을 pop하여 결과식에 추가해주어야 합니다. 이후, 현재 연산자를 stack에 추가해야 합니다.

else :
  while len(stack) != 0 and operand[infix[i]] <= operand[stack[-1]] :
    postfix.append(stack.pop())
  stack.append(infix[i])

 

드디어 알고리즘은 다 구현했고, 마지막 자잘한 코드만 짜면 됩니다.

입력이 끝나면(반복문이 끝나면) stack의 모든 요소를 pop하여 결과식에 추가해주어야 합니다. 이후, 결과식의 모든 요소들을 출력해주면 문제 해결입니다!

while len(stack) != 0 :
  postfix.append(stack.pop())

for i in range(len(postfix)) :
  print(postfix[i], end = '')

 

아래는 전체 코드입니다.

infix = list(input())
operand = {'+' : 0, '-' : 0, '*' : 1, '/' : 1, '(' : -1, ')' : -1}
postfix = []
stack = []

for i in range(len(infix)) :
  if infix[i] not in operand :
    postfix.append(infix[i])

  else :
    if infix[i] == '(':
      stack.append(infix[i])

    elif infix[i] == ')' :
      while len(stack) != 0 and stack[-1] != '(' :
        postfix.append(stack.pop())
      if len(stack) != 0 :
        stack.pop()

    else :
      while len(stack) != 0 and operand[infix[i]] <= operand[stack[-1]] :
        postfix.append(stack.pop())
      stack.append(infix[i])

while len(stack) != 0 :
  postfix.append(stack.pop())

for i in range(len(postfix)) :
  print(postfix[i], end = '')

---

시행착오

처음에 stack[-1]을 통해 stack의 최상위 데이터를 불러올 수 있단 걸 까먹고 stack[len(stack)-1] 이따구로 코드를 다 짜놨습니다...

 

또, 리스트 내에서 pop() 함수를 기본적으로 제공한다는 걸 까먹고 pop() 함수를 직접 정의하여 사용하려 했습니다. 그런데 함수 이름을 pop으로 지정하는 바람에 이미 있던 pop() 함수와 겹쳐 에러가 뜨게 되었고, 결국 구글링을 통해 기본적으로 제공되는 pop() 함수를 사용하여 문제를 고쳤습니다. (이럴거면 파이썬 공부는 왜 했나 싶네요.)

 

그리고, 처음에 연산자들의 우선순위를 지정해줄 때 실제 수학에서의 우선순위를 생각하고 ( , ) 의 우선순위를 *, / 보다 높은 2로 지정해놓았습니다. 그런데, 이렇게 되면 ' ( ' 연산자가 stack에 저장되고 +, - 등의 연산자가 입력되면 ' ( ' 연산자의 우선순위와 현재 연산자의 우선순위를 비교하고, ' ( ' 연산자의 우선순위가 더 크므로 ' ( '를 결과식으로 보낸다는 문제가 있었습니다. 따라서 이를 해결하기 위해 ( , ) 의 우선순위를 -1로 지정해주었고, 에러를 고칠 수 있었습니다.

---

느낀 점

스택(Stack)이라는 자료구조를 이용해 문제를 풀어보며, 자료구조가 얼마나 프로그래밍에 도움이 되고, 유용한 것인지를 느껴볼 수 있었습니다. 스택을 사용하지 않고 문제를 풀려 했으면 시간이 한참 걸렸을 것 같은데, 자료구조를 활용하니 문제가 금방 풀리는 걸 보면서 자료구조의 유용함에 대해 생각해보았습니다.

 

문제의 난이도가 좀 올라가서 (3월 : Gold IV → 4월 : Gold II) 알고리즘을 찾아내는 것이 상당히 힘들었던 것 같고, 이를 실제로 구현하는데도 예상치 못한 에러가 떠서 당황했던 것 같습니다. 그래도 에러를 다 고치고 문제를 풀고 나니 굉장히 뿌듯한 감정이 들었습니다.

 

5월달 과제도 자료구조이던데 이때도 스택을 할지 아니면 다른 자료구조를 할지 좀 생각해봐야 할 것 같네요.