[2024.02.14] Stack 2

• 부분집합의 합

def f(i, k, s, t): #k개의 원소를 가진 배열 A에서 부분집합의 합이 t인 경우를 찾는 함수
    global cnt
    cnt += 1
    if s == t: #목표값이면
        for j in range(k):
            if bit[j]: #A[j]가 포함된 경우
                print(A[j], end=' ')
        print() #부분집합 출력

    elif i == k: #모든 원소를 고려했으나 s!=t
        return

    elif s > t: #고려한 원소의 합이 t보다 큰 경우
        return

    else:
        for j in range(1, -1, -1):
            bit[i] = j
            f(i+1, k, s+A[i]*j, t)
        # bit[i] = 1
        # f(i+1, k, s+A[i], 10)
        # bit[i] = 0
        # f(i+1, k, s, t)

N = 10
A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
bit = [0] * N #bit[i]는 A[i]가 부분집합에 포함되는지 표시
cnt = 0 #호출 횟수
f(0, N, 0, 10)
print(f'cnt : ', cnt)

• 강사님 코드

# {1~10}의 powerset 중 원소의 합이 10인 부분집합을 구하시오. (DFS 방식 only)
# 1부터 10까지 값을 가지고 있는 전체 집합 A
A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

def dfs(i, subset):
    # 기저조건: i가 A의 길이만큼 진행했다면 종료
    if i == len(A):
        # 부분집합의 합이 10인 경우라면 출력
        if sum(subset) == 10:
            print(subset)
        return

    # 재귀호출
    # 해당 i번째 인덱스의 요소를 포함 O
    subset.append(A[i]) # 결정
    dfs(i+1, subset)

    # 해당 i번째 인덱스의 요소를 포함 X
    subset.pop() # 복구
    dfs(i+1, subset)

dfs(0, [])

def f(i, N):
    # 기저조건 : 순열이 완성된 경우
    if i == N:
        print(P)
        return
    for j in range(i, N):
        P[i], P[j] = P[j], P[i] # <-> 교환
        f(i+1, N)
        P[i], P[j] = P[j], P[i] # 원상복구

P = [1, 2, 3]
N = len(P)
f(0, N)

• 순열

# 순열
def f(i, k):
    global min_v
    if i == k:
        #print(*P)
        s = 0 #선택한 원소의 합
        for j in range(k): #j행에 대해
            s += arr[j][P[j]] #j행에서 P[j]열을 고른 경우의 합 구하기
        if min_v > s:
            min_v = s

    else:
        for j in range(i, k): #P[i] 자리에 올 원소 P[j]
            P[i], P[j] = P[j], P[i] #P[i] <-> P[j]
            f(i+1, k)
            P[i], P[j] = P[j], P[i] #원상복구

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]
    P = [i for i in range(N)]
    min_v = 100
    f(0, N)
    print(f'#{tc}', min_v)

# 순열 - 가지치기!
def f(i, k, s): #i-1까지 선택한 원소의 합
    global min_v
    global cnt
    cnt += 1
    if i == k:
        #print(*P)
        if min_v > s:
            min_v = s

    elif s >= min_v:
        return

    else:
        for j in range(i, k): #P[i] 자리에 올 원소 P[j]
            P[i], P[j] = P[j], P[i] #P[i] <-> P[j]
            f(i+1, k, s+arr[i][P[i]])
            P[i], P[j] = P[j], P[i] #원상복구

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]
    P = [i for i in range(N)]
    min_v = 100
    cnt = 0
    f(0, N, 0)
    print(f'#{tc}', min_v, cnt)

-계산기1 (강사님 코드)

import sys
sys.stdin = open('input (1).txt', 'r')

T = 10
for tc in range(1, T+1):
    #입력
    #문자열 길이 N
    N = int(input())
    #문자열 계산식
    infix = input().rstrip()

    #로직
    #중위식->후위식 변경
    #'+' 연산자
    stack = []
    postfix = '' #후위식
    #중위식->후위식으로 순회하며 변경
    for ch in infix:
        #숫자(피연산자)
        if ch.isdigit():
            postfix += ch
        #+(연산자)
        elif ch == '+':
            #연산 우선순위가 같거나 높은 스택 바로 위의 요소는 빼내줘야 함
            while len(stack) > 0 and stack[-1] == '+':
                postfix += stack.pop()
            #연산자는 stack push
            stack.append(ch)

    #스택에 남아있는 연산자들을 모두 후위식에 추가
    while len(stack) > 0:
        postfix += stack.pop()

    #후위표현식 계산을 실시
    stack = []
    #후위표현식을 순회하며
    for ch in postfix:
        #스택에다가 피연산자를 넣는다
        if ch.isdigit():
            stack.append(ch)
        elif ch == '+': #연산자가 나올 때마다 숫자 2개를 꺼내 연산을 하고,
            #다시 스택에 넣는다
            b = int(stack.pop())
            a = int(stack.pop())
            tmp = a + b
            stack.append(tmp)

    #스택에 단 하나의 결과를 꺼내어 출력
    result = stack.pop()

    #출력
    print(f'#{tc} {result}')