Mars를 이용한 계산기 프로그램(괄호 연산 가능)

괄호 계산을 위해서 공부한 내용은 후위 표기법이었다. 중위 표기법은 *와 /가 +와 - 보다 더 우선순위가 높은 규칙을 따르기 때문에 우선 순위를 높이기 위해 괄호를 사용하지만 후위 표기법은 연산자의 위치에 따른 계산을 하기 때문에 구현하기가 더 쉬울 것이라 생각했다.

후위 표기법 변환 방법

후위표기법으로 바꾸는 규칙은 다음과 같다.
1. 수(operand)는 무조건 배열에 삽입
2. 여는 괄호 (가 나오면 무조건 스택에 push
3. 계산의 우선 순위는 *, / >>> +, - >>> ( 이다.
4. 연산자 스택이 비어있으면 연산자를 무조건 스택에 push
5. 연산자 스택에 있는 연산자가 우선순위가 더 높거나 같으면 스택에 있는 연산자를 pop해서 후위표기법 배열에 삽입하고 현재 연산자를 스택에 push. 현재 연산자의 우선순위가 더 높은 경우에는 연산자를 push만 한다.
6. 닫는 괄호 ')'가 나오면 '('를 만날 때까지 연산자를 pop해서 배열에 삽입
7. 수식이 종료되면 연산자 스택에 있는 모든 연산자를 pop해서 배열에 삽입

후위 표기법 변환 예시

수식 : 12 / ( 3 + 3 ) - 2

Code

변수 정의

    .data
sol:    .asciiz "= "
exp:    .word 0:100
size:    .word 100
st_op: .space 100        #연산자 스택
st_ans:    .space 100        #계산 스택
ar_pos:    .word 0:20        #후위 표기법 배열
error:    .asciiz "error"
nan:    .asciiz "Not a Number => operand2 of '/' must not be ZERO"

    .globl main
    .text

문제를 풀기 위해 사용된 대략적인 변수라고 할 수 있다. 컴퓨터 구조나 운영체제에서 배웠지만 프로그램 실행에 필요한 변수들은 모두 스택에 저장이 된다.

main 함수

main:
    la $a0 exp        #입력을 받아 $a0에 저장
    la $a1 size

    li $v0 8
    syscall

    la $s0 st_op        # $s0 = 연산자 스택의 주소
    li $s1 0        # 연산자 스택의 탑
    la $s2 st_ans        # $s2 = 계산과정 스택의 주소
    li $s3 0        # 계산과정 스택의 탑
    la $s4 ar_pos        #후위표기법을 위한 배열
    li $s5 0        #배열의 사이즈 측정
    jal convert
    jal operate
    jal print

    li $v0 10        #프로그램 종료
    syscall

프로그램의 메인함수이다. $v0에 8을 입력하고 system call을 하면 입력을 받는다.
그 이후에는 $s0, $s2, $s4에 연산자 스택, 계산과정 스택, 후위 표기법 저장을 위한 배열로 각각 정의한다.

후위 표기법 변환

convert:            #중위 표기법을 후위 표기법으로 변환
    addi $sp $sp -4    
    sw $ra 0($sp)

    li $t0 0        # $t0 = 입력값의 주소를 읽기 위해 더해주는 값을 저장하는 레지스터
    li $t2 0        # $t2 = 숫자 입력값이 있는지 알아보기 위한 값을 저장하는 레지스터
    li $t3 0        # $t3 = 입력된 수의 임시 저장 레지스터
    li $t9 10        # $t9 = 입력값의 자릿수를 만들어 주기 위한 값을 저장하는 레지스터

$t0는 수식이 저장된 배열의 포인터이다.
$t2는 연산자 전에 숫자 입력값이 있었는지 확인하는 플래그이다.
$t3은 여러 자리의 수를 만들기 위해 임시로 수를 저장하는 값이다.
$t9는 자릿수가 증가할 때마다 10을 곱해주기 위해서 사용된다.

load_input:            #입력값을 load
    add $t1 $t0 $a0
    lb $t1 0($t1)        # $t1 = 입력된 값을 한바이트씩 받아오는 레지스터
    addi $t0 $t0 1

    beq $t1 10 _ret_convert    # enter를 만나면 변환 종료  10 = \n
    beq $t1 '(' bracket    # 괄호를 만나면 bracket으로 이동
    beq $t1 '*' muldiv    # *나 /를 만나면 muldiv로 이동
    beq $t1 '/' muldiv
    beq $t1 '+' addsub    # +나 -를 만나면 addsub로 이동
    beq $t1 '-' addsub
    beq $t1 ')' close    #괄호가 닫히면 close로 이동

    blt $t1 47 error_print    # 숫자 또는 사칙연산이 아닌 경우
    bgt $t1 58 error_print

    addi $t1 $t1 -48    # 숫자를 정수형으로 고치기 위해 빼줌
    mul $t3 $t3 $t9        # '0'의 아스키 코드 값 = 48
    add $t3 $t1 $t3
    addi $t2 $t2 1        # $t2에 1을 더한다.

    j load_input        #load_input 반복

문자열을 순회하면서 입력 값에 따라 각각의 함수로 분기한다.

error_print:            # error를 출력하고 프로그램을 종료한다.

    la $a0 error
    li $v0 4
    syscall

    li $v0 10
    syscall

_ret_convert:    
    jal operand        # 숫자가 남아 있으면 숫자를 먼저 배열에 넣고
    jal pop_all        # 남은 연산자 모두를 pop해서 배열에 넣어준다.
    lw $ra 0($sp)
    addi $sp $sp 4

    jr $ra            # main으로 돌아간다.

입력 문자가 \\n인 경우 마무리 작업을 한다.

operand:
    bgt $t2 0 push_int    # $t2가 0보다 크다는 $t3에 숫자가 있다는 것을 의미한다.
                # 숫자가 있으면 정수를 배열에 넣어준다.
    jr $ra
push_int:        
    sll $t4 $s5 2        # 배열 사이즈에 4를 곱한 후 배열 주소에 더해
    add $t4 $s4 $t4        # 정수를 저장한다.
    sw $t3 0($t4)

    addi $s5 $s5 1
    li $t2 0        # 입력된 수가 없어진다는 것을 의미한다.
    li $t3 0        # 입력된 수를 초기화
    jr $ra            # oprand로 돌아가지 않고 각각의 함수로 돌아간다.
                # $ra의 값은 oprand 함수에 있는 $ra값과 같다.
                # 즉 $ra는 operand를 불러온 jal이 있는 주소 + 4 이다.

각각의 연산전에 수가 나왔다면 수를 먼저 후위 표기법 배열에 넣어준다.

bracket:            # 괄호는 무조건 push한다.
    jal operand

    j push
muldiv:                # muldiv는 스택의 탑에 저장된 연산자가 *나 /이면
                # 이전 것을 pop하고 자기 자신을 집어넣는다.
    jal operand

    beq $s1 0 push        # stack에 아무것도 없으면 push한다.

    lw $t5 0($s0)
    beq $t5 '+' push
    beq $t5 '-' push
    beq $t5 '(' push

    jal pop            # 이 경우는 이전 탑에 *나 /가 있던 경우이다.

    j muldiv

addsub:
    jal operand

    beq $s1 0 push        # stack에 아무것도 없으면 push한다.

    lw $t5 0($s0)
    beq $t5 '(' push    # (를 만나면 스택에 아무것도 없을 때와 같이 실행한다.

    jal pop            # 앞의 연산자들을 pop한다.

    j addsub
close:                # 괄호가 닫히면 '('를 만날 때 까지 pop한다.
    jal operand

    lw $t5 0($s0)
    beq $t5 '(' pop_bracket

    jal pop

    j close

push:                # 연산자를 스택의 탑에 넣는다.
    addi $s1 $s1 1
    addi $s0 $s0 4
    sw $t1  0($s0)

    j load_input

pop:                # 탑에 있는 연산자를 스택에서 꺼내 배열에 넣는다.
    lw $t5 0($s0)
    addi $s0 $s0 -4
    addi $s1 $s1 -1

    sll $t4 $s5 2
    add $t4 $s4 $t4
    mul $t5 $t5 -1        # 이 때 정수값들과 비교하기 위해 -를 곱해서 넣어준다.
    sw $t5 0($t4)

    addi $s5 $s5 1        # 배열의 크기 증가

    jr $ra
pop_bracket:            # '('는 후위 표기법의 배열에 필요 없으므로
                # 스택의 포인터만 낮춰준다. 
    addi $s0 $s0 -4

    addi $s1 $s1 -1
    j load_input

pop_all:            # 입력값을 모두 읽었으면 남아 있는 모든 연산자를 pop한다.
    addi $sp $sp -4
    sw $ra 0($sp)
    jal pop
    lw $ra 0($sp)
    addi $sp $sp 4
    bgtz $s1 pop_all    # 연산자 스택의 탑이 0보다 크면 다시 pop을 한다.

    jr $ra

후위 표기법 계산

operate:
    addi $sp $sp -4
    sw $ra 0($sp)

    li $t0 0        # 배열의 사이즈 만큼만 읽기 위한 count        

Loop:    
    seq $t6 $s3 1        # 스택에 값이 하나가 있고
    seq $t7 $t0 $s5        # count가 배열의 사이즈와 같으면 연산종료 
    and $t8 $t6 $t7
    beq $t8 1 _ret_operate
    beq $t7 1 error_print    # count가 배열의 사이즈와 같은데 스택의 탑이 1이 아니면 오류
                # 이 오류는 연산자 뒤에 바로 연산자가 올 때
                # 혹은 숫자 다음에 바로 '(' 나 ')' 가 올때 적용
    sll $t1 $t0 2        # count * 4
    add $t1 $s4 $t1        
    lw $t1 0($t1)
    addi $t0 $t0 1        # count++

    beq $t1 -45 op_sub    # '-' = 45
    beq $t1 -43 op_add    # '+' = 43
    beq $t1 -42 op_mul    # '*' = 42
    beq $t1 -47 op_div    # '/' = 47

    jal push_number        # 연산자가 아니라면 숫자를 push해준다.

    j Loop
push_number:
    addi $s2 $s2 4        # 스택에 한칸을 만들어 숫자를 저장
    sw $t1 0($s2)
    addi $s3 $s3 1        # Top Of Stack ++

    jr $ra

op_add:                
    lw $t2 0($s2)        # 탑에 있는 값을 pop해서 opernad 2로 설정
    addi $s2 $s2 -4        # Top of Stack --
    addi $s3 $s3 -1    
    lw $t3 0($s2)        # 다시 탑에 있는 값을 pop 해서 oprand 1로 설정
                # 이 주소에 다시 저장해야 되기 때문에 Top of Stack --를 안함
    add $t4 $t3 $t2        # operand 1 + opernad 2
    sw $t4 0($s2)        # 스택의 탑에 값을 저장

    j Loop
op_sub:
    lw $t2 0($s2)        # 탑에 있는 값을 pop해서 opernad 2로 설정
    addi $s2 $s2 -4        # Top of Stack --
    addi $s3 $s3 -1        
    lw $t3 0($s2)        # 다시 탑에 있는 값을 pop 해서 oprand 1로 설정
                # 이 주소에 다시 저장해야 되기 때문에 Top of Stack --를 안함

    sub $t4 $t3 $t2        # operand 1 - operand 2
    sw $t4 0($s2)        # 스택의 탑에 저장

    j Loop
op_mul:                
    lw $t2 0($s2)        # 탑에 있는 값을 pop해서 opernad 2로 설정
    addi $s2 $s2 -4        # Top of Stack --
    addi $s3 $s3 -1
    lw $t3 0($s2)        # 다시 탑에 있는 값을 pop 해서 oprand 1로 설정
                # 이 주소에 다시 저장해야 되기 때문에 Top of Stack --를 안함

    mul $t4 $t3 $t2        # operand 1 * opernad 2
    sw $t4 0($s2)        # 스택의 탑에 저장

    j Loop
op_div:
    lw $t2 0($s2)        # 탑에 있는 값을 pop해서 opernad 2로 설정
    addi $s2 $s2 -4        # Top of Stack --
    addi $s3 $s3 -1
    lw $t3 0($s2)        # 다시 탑에 있는 값을 pop 해서 oprand 1로 설정
                # 이 주소에 다시 저장해야 되기 때문에 Top of Stack --를 안함

    beqz $t2 NaN_print    # 분모가 0이 되면 오류
    div $t4 $t3 $t2        # operand 1 / operand 2
                # 단 여기서 나머지는 계산되지 않음
    sw $t4 0($s2)        # 스택의 탑에 저장

    j Loop

NaN_print:
    la $a0 nan        # 오류메시지 출력
    li $v0 4
    syscall

    li $v0 10        # 프로그램 종료
    syscall
_ret_operate:            # main 으로 돌아감

    lw $ra 0($sp)
    addi $sp $sp 4

    jr $ra

print:                # 마지막 계산된 값을 print
    la $a0 sol
    li $v0 4
    syscall

    lw $a0 0($s2)
    li $v0 1
    syscall

    jr $ra

예외 처리

1. 괄호를 제외한 연산자 2개가 연속되는 경우
2. 연산자의 수가 초과되는 경우    ex. "5+4*" 
3. 곱셈을 생략하는 경우    ex. 5(3+2)
4. 숫자나 연산자가 아닌 다른 문자가 수식에 있는 경우
5. 나눗셈을 할 때 분모가 0인 경우

프로그램의 한계점

1. 정수 계산기이다.
    나눗셈의 결과값은 정수가 된다. 예를 들어 15/4는 3.75가 아니라 3으로 계산된다.
2. 음수는 입력을 받을 때 (0-5)와 같은 형태를 취해야 한다.

프로그램을 짜면서 int() 같은 함수에도 감사함이 느껴졌다. 괄호 연산 또한 고급 언어에서는 기본적으로 가능하기 때문에 구현이 복잡할 거라 생각하지 못했다. Mars를 이용해 디버깅을 하면서 컴퓨터 구조 시간에 배웠던 것 처럼 데이터가 스택에 저장되어 어떻게 사용이 되고 레지스터를 이용해서 데이터를 저장하는 등의 이론적인 부분에 이해도가 높아지는 기분이었다.

내가 이 코드를 작성할 때는 오직 신과 나만이 그것이 무엇을 하는 코드인지 알았다 하지만 지금은... 오직 신만이 안다

[백준][파이썬] 2210번 - 숫자판 점프

문제 번호 : 2210
문제 출처 : https://www.acmicpc.net/problem/2210

Code

import sys


def recursive(x, y, count):
    if count == 5:
        number.append(numbers[x][y])
        answer_set.add(tuple(number))
    else:
        number.append(numbers[x][y])
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if -1 < nx < 5 and -1 < ny < 5:
                recursive(nx, ny, count + 1)
    number.pop()

numbers = [sys.stdin.readline().split() for _ in range(5)]

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

answer_set = set()
number = []
for r in range(5):
    for c in range(5):
        recursive(r, c, 0)

print(len(answer_set))

Idea

1. 각각의 시작점에서 가능한 방향으로 모두 방문하며 list에 숫자를 추가
2. 숫자 리스트를 집합 자료형에 입력함으로써 중복을 제거
3. 재귀함수가 호출 되고나서 입력받은 리스트와 같은 새로운 리스트를 만들지 않고 기존의 리스트를 append와 pop을 사용해서 스택으로 사용

집합의 요소로는 리스트가 들어갈 수 없다. 그래서 집합에 add를 할 때 리스트를 tuple이나 str로 변환하여 입력해주어야 했다. 집합은 직접 수정이 불가능한 자료형인데 리스트는 주소에 의한 수정이 가능해져서가 아닐까 추측해본다.

[백준][파이썬] 15686번 치킨 배달

문제 번호 : 15686
문제 출처 : https://www.acmicpc.net/problem/15686

Code

import sys
from itertools import combinations

## 입력
n, m = map(int, input().split())
city = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

distance = []   # 집 별로 치킨 집과의 거리 저장
chickens = []   # 치킨 집의 위치와 치킨 집의 번호 저장
houses = []     # 집의 위치 저장
n_chicken = 0
for i in range(n):
    for j in range(n):
        if city[i][j] == 1:
            houses.append([i, j])
        elif city[i][j] == 2:
            chickens.append([i, j, n_chicken])
            n_chicken += 1

for i in range(len(chickens)):
    distance.append([])
    for house in houses:
        distance[i].append(abs(chickens[i][0] - house[0]) + abs(chickens[i][1] - house[1]))

cases = combinations(chickens, m)

answer = 1e9

for case in cases:
    d = []
    for i in range(m):
        d.append(distance[case[i][2]])

    d = list(map(min, zip(*d)))
    answer = min(sum(d), answer)

print(answer)

Idea

1. N x N 크기의 배열을 모두 탐색하면서 집의 위치와 치킨 집의 위치를 모두 저장
2. 치킨 집의 위치를 저장할 때에는 치킨 집의 number를 차례로 부여
3. 집마다 각 치킨집과의 거리를 저장
4. 치킨 집의 갯수에서 M개의 조합을 생성
5. M개의 조합을 모두 탐색하며 치킨 거리가 최소인 답을 구함

이번 문제에서 zip 함수와 map 함수, 그리고 * 을 사용해서 각 거리들 중 최단 거리를 구했다.
d = list(map(min, zip(*d))) 를 해석해보겠다.
iterable앞에 *을 붙이게 되면 iterable형의 요소들을 모두 반환한다.
예시를 들자면 다음과 같다.

def print_all(a, b, c):
    print(a)
    print(b)
    print(c)

li = [1, 2, 3]
print_all(*li)

### 실행결과
# 1
# 2
# 3

코드에서 d 는 2차원 리스트이므로 여러 개의 1차원 리스트들을 반환한다.
zip함수는 여러개의 iterable이 입력으로 들어오면 index가 같은 요소들끼리 튜플로 합쳐서 반환한다. d의 각 1차원 리스트들은 각 집에서 치킨집들까지의 거리이고 zip함수를 사용하고 나면 각 치킨 집마다의 집들까지의 거리가 된다.
여기에 map함수로 각 리스트별로 min함수를 사용해서 리스트로 반환한다.
처음에 2차원 배열을 모두 돌면서 각 치킨집 별로 최소 거리를 구하는 방법을 사용했고 시간이 400ms가 나왔다. 그런 과정을 저 한 줄의 코드로 변환해서 확인한 결과 112ms로 시간이 많이 줄어들었다.

[백준][파이썬]

문제 번호 : 17088
문제 출처 : https://www.acmicpc.net/problem/17088

Code

# 등차 수열이려면 첫 번째 차와 두 번째 차가 같은 경우여야 함

n = int(input())
a = list(map(int, input().split()))

if n < 3:  # 숫자가 하나 또는 2개면 무조건 등차수열
    print(0)
else:
    diff = []   # 수열에서 한 칸당 차이를 저장
    for i in range(n - 1):
        diff.append(a[i] - a[i + 1])
    if len(set(diff)) == 0: # 차이가 모두 같으면 집합으로 했을 때 값이 하나밖에 없다.
        print(0)
        exit(0)

    op = (-1, 0, 1)     # 연산의 종류
    cases = []
    answer = n + 1      # 최소값을 찾을 거고 값은 연산횟수는 n을 넘어갈 수 없다.
    for i in op:
        for j in op:
            for k in op:
                count = abs(i) + abs(j) + abs(k)
                d1, d2 = diff[0] + i - j, diff[1] + j - k
                if d1 == d2:    # 0번와 1번, 1번와 2번의 차가 같은 경우 cases에 저장
                    cases.append((a[0] + i, d1, count))

    for case in cases:      # 저장된 케이스들만 생각
        start = case[0]
        sub = case[1]
        cnt = case[2]
        if n == 3:          # A3까지 모두 연산을 해봤기 때문에 길이가 3인 경우 답은 cnt일 확률이 높다.
                            # 아닌경우도 있을 듯
            answer = min(answer, cnt)
        for idx in range(3, n):
            tmp = a[idx] - (start - (sub * idx))    # idx 번째의 값이 예상 값보다 1 이상 차이나면
            if abs(tmp) > 1:                        # +-1 연산만으로 등차수열을 만들 수 없다.
                break
            elif abs(tmp) == 1:                     # 값이 1밖에 차이 안나면 +든 -든 연산을 해야된다.
                cnt += 1                            # 뭘할지 정할 필요는 없고 횟수만 세면 된다.
            if idx == n - 1:
                answer = min(answer, cnt)

    print(answer if answer <= n else -1)            # answer가 n+1이면 -1을 출력, 아니면 answer를 출력

Idea

1. 입력된 수가 2개 이하이면 항상 등차수열이 된다. 그런 경우 연산을 0번 진행하기 때문에 print(0)를 하고 프로그램을 종료한다.
2. 입력된 수가 3개 이상인 경우를 생각해보면 A1, A2, A3 에 각각 연산을 한 후 A1 - A2 과 A2-A3가 같아지는 경우들만 cases에 추가해준다. 이 때 연산 횟수는 -1, 1 은 각 한 번씩, 0은 연산을 하지 않은 것으로 생각하기 위해서 절대값을 취해줬다.
3. cases에 추가된 경우들에서 4번 째 수부터 첫 번째 수와 차를 이용해서 구한 예상값과 차이가 1보다 크면 등차수열이 만들어질 수 없다.
4. 예상값과 차이가 1이면 연산횟수를 1 더해주고 0이면 그냥 넘어간다. 마지막 수까지 예상값과 차이가 1 이하이면 answer에 cnt의 최소값을 넣어준다.
5. 처음에 answer = n + 1 로 정의했기 때문에 등차수열을 만들 수 있는 case가 존재하지 않으면 answer > n 이기 때문에 -1을 출력하도록 한다.

[백준][파이썬] 15683번 감시

문제 번호 : 15683
문제 출처 : https://www.acmicpc.net/problem/15683

Code

import sys


def watch(watched_set, index):              # index : count, cctv 개수 만큼 탐색
    if index == len(cctvs):
        result.append(len(watched_set))
        return
    else:
        for cctv in cctvs[index]:           # cctv[index] 에는 한 cctv의 경우의 수가 모두 저장
            new_s = set(watched_set)
            view(cctv, new_s)               # 각도에 따라서 cctv로 볼 수 있는 위치를 집합에 저장
            watch(new_s, index + 1)


def view(cc, viewd):
    x, y, cctv_type, angle = cc
    d = []
    for idx in range(4):
        d = direction[cctv_type][(idx + angle) % 4] # cctv type과 angle이 정해졌을 때 방향
        if d == 1:
            nx, ny = x + dx[idx], y + dy[idx]
            while -1 < nx < h and -1 < ny < w and office[nx][ny] != 6:
                if office[nx][ny] == 0:     # cctv 있는 위치는 저장 안하도록
                    viewd.add((nx, ny))
                nx = nx + dx[idx]
                ny = ny + dy[idx]


h, w = map(int, input().split())
office = [list(map(int, sys.stdin.readline().split())) for _ in range(h)]

angles = [4, 2, 4, 4, 1]        # type별로 가능한 각도 수
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
direction = [[0, 0, 0, 1], [0, 1, 0, 1], [0, 0, 1, 1], [0, 1, 1, 1,], [1, 1, 1, 1]] # 각도 별로 shift할 리스트

cctvs = []
answer = 0
result = []

for i in range(h):
    for j in range(w):
        if 0< office[i][j] <6:  # cctvs 에 하나의 cctv에서 가능한 각도를 하나의 리스트에 모두 저장
            cctvs.append([[i, j, office[i][j] - 1, angle] for angle in range(angles[office[i][j] - 1])])
        if office[i][j] == 0:   # 0의 개수 세기기
            answer+= 1
watched = set([])

watch(watched, 0)
answer = answer - max(result)   # 0의 개수에서 cctv로 본 위치의 수 빼서 답 구하기
print(answer)

Idea

1. cctv 종류 별로 가능한 각도 수가 다르다.
2. 처음에는 cctv로 본 곳을 #으로 표시했는데 시간이 많이 걸렸다.
3. 입력받은 이차원 리스트를 수정하지 않고 cctv가 본 위치를 저장하는 집합을 만들었다.
4. cctv가 본 위치가 가장 많은 상황에서 0의 개수에서 집합의 길이를 빼면 사각지대를 구할 수 있다.