[PS] BOJ 6568 / 귀도 반 로썸은 크리스마스날 심심하다고 파이썬을 만들었다

Minjun Kim

09 Jun 2025 • 9 min read

문제 링크: https://www.acmicpc.net/problem/6568

Thumbnail: Photo by Amr Taha™ (Unsplash)

문득 solved.ac 디스코드를 둘러보다가 보인 문제인데, 재밌어 보여서 풀어봤습니다.
간만에 구현 문제라 Python3에 타입힌트랑 주석까지 써가면서 만들었네요 ㅎㅎ

풀이

귀도 반 로썸은 크리스마스날 심심하다고 파이썬을 만들었다

귀도 반 로썸은 정말 심심하다고 파이썬을 만들어버렸는데, 이 문제에서도 파이썬 수준은 아니지만 정말 간단한 8bit짜리 명령어 32줄로 구성된 프로그램을 실행하는 코드를 작성하면 됩니다.

인터프리터를 만드는 느낌을 받을 수 있습니다! 덕분에 풀면서 재밌었습니다 😄

구조 분석

문제에서 명령어를 실행하는 PC 환경은 다음과 같이 설명되어 있습니다:

하나의 프로세서
32바이트 메모리
- 폰 노이만 구조를 표방하여 이 컴퓨터는 메모리와 프로그램 구문을 공유한다.
8비트짜리 가산기
5비트짜리 프로그램 카운터(pc)

여기서, 메모리와 프로그램 구문을 공유한다는 뜻은 메모리에 어떤 값을 덮어쓸 때 덮어씌워진 값이 새로운 명령어로도 기능한다는 뜻이며, 간단히 생각하면 그냥 메모리와 명령어를 하나의 단일 배열로 읽고 쓰면 됩니다.

class Interpreter:
    pc: int = 0
    acc: int = 0
    memory: list[str] = ["" for _ in range(32)]

    def init(self):
        """실행 환경 초기화"""
        for i in range(32):
            self.memory[i] = input().rstrip()
            # 로컬에서 테스트 케이스 돌릴 때 빈 문자열이 들어와서 예외처리함.
            if self.memory[i] == '':
                raise EOFError()
        self.pc = 0
        self.acc = 0

인터프리터 객체 및 실행 환경 초기화 메소드

명령어 구현

사실 굳이 별도 객체로 감쌀 필요는 없지만, 명령어 실행 과정을 단순화하고, 8bit 길이의 명령어 중 뒤 5bit에 해당하는 x를 미리 정수 값으로 변환해두기 위해서 만들었습니다.

CodeTypes = {
    "000": "sta",
    "001": "lda",
    "010": "beq",
    "011": "nop",
    "100": "dec",
    "101": "inc",
    "110": "jmp",
    "111": "hlt"
}

class Code:
    c_type: str     # 3자리 명령어 유형 값
    address: int    # 5자리 메모리 주소값
    __slots__ = ("c_type", "address") # 객체의 메모리 사용량을 줄이기 위함.

    def __init__(self, c_type: str, address: int):
        self.c_type = c_type
        self.address = address

    @classmethod
    def parse(cls, bytecode: str) -> "Code":
        """Parse a single line of byte code."""
        return cls(CodeTypes[bytecode[:3]], int(bytecode[3:], 2))

각 줄의 명령어 정보를 가공하는 Code 객체

명령어 실행 구현

명령어 실행 과정은 아래와 같이 구현했습니다.

프로그램이 종료될 때 까지 다음을 반복합니다:
- 메모리에서 현재 pc값에 해당하는 8bit 이진수를 가져와, Code객체로 변환합니다.
- 이후, pc값을 1 증가시킵니다.
  - 단, pc값은 5bit이므로 32가되면 5bit의 표현 범위를 넘어가 오버플로우로 인해 0이 되야 합니다.
- 이후, 해석된 Code객체를 참조해 해당하는 명령어의 동작을 수행합니다.
  - 프로그램의 종료 여부 (HLT 명령어의 동작 여부)를 판단합니다.
현재 가산기에 저장된 값(acc)를 8bit 2진수의 형태로 출력합니다.

class Interpreter:
    # ... (중략)
    def run(self):
        while True:
            c = Code.parse(self.memory[self.pc])
            self.pc = self.pc + 1 if self.pc < 31 else 0
            halt = getattr(self, c.c_type)(c.address)
            if halt:
                break
        print(format(self.acc, "08b"))   # pc는 언제나 음이 아닌 정수

어라? 왜 코드가 이모양일까요?

앞서 Code객체의 정의를 보면, c_type에는 CodeTypes 딕셔너리를 통해 변환한 명령어의 이름이 들어 있습니다. 그리고, 해당하는 이름을 Interpreter 객체 안에서 찾아, 명령어의 뒤 5bit (address)를 매개변수로 전달해 실행하고 있습니다. 이후, 실행 결과를 halt 변수에 받아오고 있습니다.

실제로 Interpreter 객체 내부에 각 명령어와 같은 이름의 함수로 실제 명령어 동작을 구현해 두었습니다. 구조는 다음과 같습니다:

class Interpreter:
    def cmd(self: Self, x: int) -> bool:
        """CMD x 꼴의 명령어를 정의합니다
        @param x: 5bit 메모리 주소값.
        """
        return False # 프로그램 종료 여부. HLT 명령어에서만 True를 반환합니다.

self의 타입 힌트인 Self는 Interpreter의 인스턴스임을 의미합니다.

각 명령어의 구현은 아래와 같습니다:

class Interpreter:
    # Code Functions
    def sta(self, x: int) -> bool:
        """STA x: 메모리의 x번째 주소에 현재 가산기 값을 저장한다.
        @param x: 5bit짜리 메모리 주소값.
        """
        self.memory[x] = format(self.acc, "08b")
        return False
    
    def lda(self, x: int):
        """LDA x: 메모리의 x번째 주소에 있는 값을 현재 가산기로 불러온다.
        @param x: 5bit짜리 메모리 주소값.
        """
        self.acc = int(self.memory[x], 2)
        return False
  
    def beq(self, x: int):
        """BEQ x: 현재 가산기의 값이 0이라면, PC를 x로 바꾼다.
        @param x: 5bit짜리 메모리 주소값.
        """
        if self.acc == 0:
            self.pc = x
        return False
    
    def nop(self, x: int):
        """NOP -: 아무 연산도 하지 않는다.
        @param x: 5bit짜리 메모리 주소값. (사용되지 않는다.)
        """
        return False
    
    def dec(self, x: int):
        """DEC -: 가산기 값을 1 감소시킨다.
        @param x: 5bit짜리 메모리 주소값. (사용되지 않는다.)
        """
        self.acc -= 1
        if self.acc < 0:
            self.acc = 255
        return False
    
    def inc(self, x: int):
        """INC -: 가산기 값을 1 증가시킨다.
        @param x: 5bit짜리 메모리 주소값. (사용되지 않는다.)
        """
        self.acc += 1
        if self.acc > 255:
            self.acc = 0
        return False
    
    def jmp(self, x: int):
        """JMP x: PC 값을 x로 바꾼다.
        @param x: 5bit짜리 메모리 주소값.
        """
        self.pc = x
        return False
    
    def hlt(self, x: int):
        """HLT -: 프로그램을 종료한다.
        @param x: 5bit짜리 메모리 주소값. (사용되지 않는다.)
        """
        return True

여러 개의 테스트 케이스 처리

문제에서는 여러 개의 테스트 케이스를 제공합니다. 다만, 테스트 케이스의 개수는 사전에 알려주지 않으며, EOF를 통해 입력이 종료됨을 판단해야 합니다. 따라서, 무한 반복을 하며 EOFError가 발생할 시 반복문을 종료하도록 구현했습니다.

반복문에서 실행해야 하는 메소드는 2가지입니다.

Interpreter().init()
- 인터프리터의 초기 환경 설정을 수행합니다. pc, acc, memory를 모두 초기 상태로 설정합니다.
Interpreter().run()
- 입력받은 프로그램(32줄의 명령어)를 실행합니다.

interpreter = Interpreter()
while True:
    try:
        interpreter.init()
        interpreter.run()
    except EOFError:
        break

전체 코드

input = open(0).readline

CodeTypes = {
    "000": "sta",
    "001": "lda",
    "010": "beq",
    "011": "nop",
    "100": "dec",
    "101": "inc",
    "110": "jmp",
    "111": "hlt"
}

# 메모리 주소값은 2진수 정수값 문자열로 인식하고 파싱한다.
class Code:
    c_type: str     # 3자리 명령어 유형 값
    address: int    # 5자리 메모리 주소값
    __slots__ = ("c_type", "address")

    def __init__(self, c_type: str, address: int):
        self.c_type = c_type
        self.address = address

    @classmethod
    def parse(cls, bytecode: str) -> "Code":
        """Parse a single line of byte code."""
        return cls(CodeTypes[bytecode[:3]], int(bytecode[3:], 2))

class Interpreter:
    pc: int = 0
    acc: int = 0
    memory: list[str] = ["" for _ in range(32)]

    def init(self):
        # 코드 입력 받기
        for i in range(32):
            self.memory[i] = input().rstrip()
            # 로컬에서 테스트 케이스 돌릴 때 빈 문자열이 들어와서 예외처리해둠.
            if self.memory[i] == '':
                raise EOFError()
        self.pc = 0
        self.acc = 0

    # Code Functions
    def sta(self, x: int) -> bool:
        """STA x: 메모리의 x번째 주소에 현재 가산기 값을 저장한다.
        @param x: 5bit짜리 메모리 주소값.
        """
        self.memory[x] = format(self.acc, "08b")
        return False
    
    def lda(self, x: int):
        """LDA x: 메모리의 x번째 주소에 있는 값을 현재 가산기로 불러온다.
        @param x: 5bit짜리 메모리 주소값.
        """
        self.acc = int(self.memory[x], 2)
        return False
  
    def beq(self, x: int):
        """BEQ x: 현재 가산기의 값이 0이라면, PC를 x로 바꾼다.
        @param x: 5bit짜리 메모리 주소값.
        """
        if self.acc == 0:
            self.pc = x
        return False
    
    def nop(self, x: int):
        """NOP -: 아무 연산도 하지 않는다.
        @param x: 5bit짜리 메모리 주소값. (사용되지 않는다.)
        """
        return False
    
    def dec(self, x: int):
        """DEC -: 가산기 값을 1 감소시킨다.
        @param x: 5bit짜리 메모리 주소값. (사용되지 않는다.)
        """
        self.acc -= 1
        if self.acc < 0:
            self.acc = 255
        return False
    
    def inc(self, x: int):
        """INC -: 가산기 값을 1 증가시킨다.
        @param x: 5bit짜리 메모리 주소값. (사용되지 않는다.)
        """
        self.acc += 1
        if self.acc > 255:
            self.acc = 0
        return False
    
    def jmp(self, x: int):
        """JMP x: PC 값을 x로 바꾼다.
        @param x: 5bit짜리 메모리 주소값.
        """
        self.pc = x
        return False
    
    def hlt(self, x: int):
        """HLT -: 프로그램을 종료한다.
        @param x: 5bit짜리 메모리 주소값. (사용되지 않는다.)
        """
        return True

    def run(self):
        while True:
            c = Code.parse(self.memory[self.pc])
            self.pc = self.pc + 1 if self.pc < 31 else 0
            halt = getattr(self, c.c_type)(c.address)
            if halt:
                break
        print(format(self.acc, "08b"))   # pc는 언제나 음이 아닌 정수

    
interpreter = Interpreter()
while True:
    try:
        interpreter.init()
        interpreter.run()
    except EOFError:
        break

solution.py