김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 4970 디지털 회로 개론 파이썬(Python)

문제 링크

3차 논리식을 파싱하고 해당 논리식을 참으로 만드는 값들을 찾는 문제.
입력이 그다지 크지 않아서 쉽게 할 수 있다.
먼저 3차 논리를 처리하기 위한 lnot, land, lor 함수를 만든 다음, 그 함수들을 3차원 리스트에 매핑하기 위한 함수를 만들었다.
그 후 스택을 가지고 논리식의 기호를 순회하면서, 괄호가 등장하는 경우 괄호 안을 계산해주고, -가 등장하는 경우 다음 기호에 따라 --를 상쇄하거나, 뒤에 등장하는 식에 not 연산을 해주고, 원자적인 값이 등장하는 경우 해당 값을 3차원 리스트로 만든다.
이 3차원 리스트 ret[i][j][k]는 \(P=i\), \(Q=j\), \(R=k\)인 경우에 논리식의 결과값이 된다.
논리식의 순회가 끝나면 스택에는 모든 연산을 완료한 이후의 값이 담기고, 여기서 참, 즉 2의 개수를 세어서 출력해주면 된다.

#!python

from sys import stdin
input = stdin.readline

# 0, 1, 2, P, Q, R을 파싱해서 3 * 3 * 3 리스트로 반환하는 함수
# ret[i][j][k]는 P=i, Q=j, R=k일 때 결과값
def parse(a):
    ret = [[[0 for _ in range(3)] for _ in range(3)] for _ in range(3)]
    match a:
        # 0, 1, 2인 경우는 P, Q, R에 상관없이 결과가 고정
        case '0' | '1' | '2':
            ret = [[[int(a) for _ in range(3)] for _ in range(3)] for _ in range(3)]
        # P인 경우 나머지는 don't care하고 P 값에 따라 결과가 결정
        case 'P':
            for i in range(3):
                for j in range(3):
                    for k in range(3):
                        ret[i][j][k] = i
        # Q인 경우 나머지는 don't care하고 Q 값에 따라 결과가 결정
        case 'Q':
            for i in range(3):
                for j in range(3):
                    for k in range(3):
                        ret[i][j][k] = j
        # R인 경우 나머지는 don't care하고 R 값에 따라 결과가 결정
        case 'R':
            for i in range(3):
                for j in range(3):
                    for k in range(3):
                        ret[i][j][k] = k
    return ret

# 3 * 3 * 3 리스트에 lnot을 매핑
def gnot(a):
    return [[[lnot(a[i][j][k]) for k in range(3)] for j in range(3)] for i in range(3)]

# 3 * 3 * 3 리스트에 land을 매핑
def gand(a, b):
    return [[[land(a[i][j][k], b[i][j][k]) for k in range(3)] for j in range(3)] for i in range(3)]

# 3 * 3 * 3 리스트에 lor을 매핑
def gor(a, b):
    return [[[lor(a[i][j][k], b[i][j][k]) for k in range(3)] for j in range(3)] for i in range(3)]

# not 연산
def lnot(a):
    return 2 - a

# and 연산
def land(a, b):
    if 0 in (a, b):
        return 0
    if 1 in (a, b):
        return 1
    return 2

# or 연산
def lor(a, b):
    if 2 in (a, b):
        return 2
    if 1 in (a, b):
        return 1
    return 0

while 1:
    # 입력을 받고 입력이 .이면 탈출
    exp = input().rstrip()
    if exp == '.':
        break
    stack = []
    for e in exp:
        # --를 상쇄시킴
        if e == '-' and stack and stack[-1] == '-':
                stack.pop()
        # 기호가 값인 경우 파싱하고 스택에 리스트를 넣되 앞에 -가 있었으면 not 연산하여 넣음
        elif e in ('0', '1', '2', 'P', 'Q', 'R'):
            temp = parse(e)
            if stack and stack[-1] == '-':
                stack.pop()
                temp = gnot(temp)
            stack.append(temp)
        # 괄호가 닫힌 경우 괄호 안의 기호들을 꺼내서 파싱하고 계산
        elif e  == ')':
            a, op, b = stack.pop(), stack.pop(), stack.pop()
            stack.pop()
            if op == '*':
                temp = gand(a, b)
            else:
                temp = gor(a, b)
            # -가 있었으면 not 연산하여 넣음
            if stack and stack[-1] == '-':
                stack.pop()
                temp = gnot(temp)
            stack.append(temp)
        # 그 외의 경우 추후 계산을 위해 기호 삽입
        else:
            stack.append(e)

    # 2의 개수를 세어서 출력
    print(sum(map(lambda x: sum(map(lambda y: y.count(2), x)), stack[-1])))

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑