Coding 공부

import sys

input = sys.stdin.readline
def calc_operator(operator,x,y):
    if operator == '*':
        return x*y
    elif operator == '-':
        return x-y
    elif operator == '+':
        return x+y


def calc():
    new_num_list = []
    new_operator_list = []
    ind = 0
    while ind<len(num_list):
        if ind < len(num_list)-1:
            if not open_bracket[ind]:
                new_num_list.append(num_list[ind])
                new_operator_list.append(operator_list[ind])
                ind += 1
            else:
                new_number = calc_operator(operator_list[ind],num_list[ind],num_list[ind+1])
                if ind == len(num_list)-2:
                    new_num_list.append(new_number)
                else:
                    new_num_list.append(new_number)
                    new_operator_list.append(operator_list[ind+1])
                ind += 2
        else:
            new_num_list.append(num_list[ind])
            ind+= 1
    ind = 0
    value = new_num_list[0]
    while ind < len(new_num_list)-1:
        value = calc_operator(new_operator_list[ind],value,new_num_list[ind+1])
        ind += 1
    return value







def dfs(index):
    global result
    if index == len(num_list)-1:
        result = max(calc(),result)
        return
    else:
        if visited[index]:
            visited[index] = False
            visited[index+1] = False
            open_bracket[index] = True
            dfs(index+1)
            visited[index] = True
            visited[index+1] = True
            open_bracket[index] = False
        dfs(index+1)

N = int(input())
arr = list(input())
if N == 1:
    print(arr[0])
else:
    num_list = []
    operator_list = []
    for i in range(N):
        if i%2:
            operator_list.append(arr[i])
        else:
            num_list.append(int(arr[i]))
    result = -float('inf')
    visited = [True]*len(num_list)
    open_bracket = [False]*len(num_list)
    dfs(0)
    print(result)

import sys

input = sys.stdin.readline
def calc(operator,x,y):
    if operator == '*':
        return x*y
    elif operator == '-':
        return x-y
    elif operator == '+':
        return x+y
def dfs(idx,value):
    global result
    if idx == length_num-1:
        result = max(result,value)
        return
    temp = calc(operator_list[idx],value,num_list[idx+1])
    dfs(idx+1,temp)

    if idx < length_num-2:
        next_value = calc(operator_list[idx+1],num_list[idx+1],num_list[idx+2])
        temp = calc(operator_list[idx],value,next_value)
        dfs(idx+2,temp)



N = int(input())
origin_input = list(input().strip())
num_list = []
operator_list = []

for ind in range(len(origin_input)):
    if ind%2:
        operator_list.append(origin_input[ind])
    else:
        num_list.append(int(origin_input[ind]))
result = -float('inf')
length_num = len(num_list)

dfs(0,num_list[0])
print(result)

import sys
input = sys.stdin.readline
def check(num):
    visited[num] = True
    stack = [num]

    while stack:
        node = stack.pop(0)

        for next_node in tree[node]:
            if tree[node][next_node] == 1:
                if not visited[next_node]:
                    visited[next_node] = True
                    stack.append(next_node)
                    tree[node][next_node] = 0
                    tree[next_node][node] = 0
                else:
                    return False
    return True
            


tc = 1
while True:
    N,M = map(int,input().split())
    if N+M == 0:
        break
    parent_cnt = [0]*(N+1)
    tree = [{} for _ in range(N+1)]
    for _ in range(M):
        x,y = map(int,input().split())
        tree[x][y] = 1
        tree[y][x] = 1
    cnt = 0
    visited = [False]*(N+1)
    for num in range(1,N+1):
        if not visited[num]:
            if check(num):
                cnt += 1
    if cnt == 0:
        print(f'Case {tc}: No trees.')
    elif cnt == 1:
        print(f'Case {tc}: There is one tree.')
    else:
        print(f'Case {tc}: A forest of {cnt} trees.')


    tc += 1

def find_prime_number():
    global N
    numbers = [True]*(N+1)
    numbers[0] = False
    numbers[1] = False

    for num in range(2,N+1):
        if numbers[num]:
            for num_multi in range(num*2,N+1,num):
                numbers[num_multi] = False
    prime_number = []
    for num in range(N+1):
        if numbers[num]:
            prime_number.append(num)
    return prime_number



N = int(input())


prime_numbers = find_prime_number()
DP = [0]*40001



DP[0] = 1
for prime_number in prime_numbers:
    for num in range(prime_number,N+1):
        DP[num] = (DP[num]+DP[num-prime_number])%123456789


print(DP[N])

from collections import defaultdict
from collections import deque
import sys
input = sys.stdin.readline
N, D,K,C = map(int,input().split())
a = defaultdict(int)

sushi = deque()
max_value = 0
# D 초밥의 가짓수
# K 는 연속해서 먹은 초밥의 수
# C 쿠폰번호
sushi_dict = defaultdict(int)
cnt = 0
sushi_list = [int(input()) for _ in range(N)]
for left in range(N+K+1):
    sushi_input = sushi_list[left%N]
    if len(sushi)<K:
        sushi.append(sushi_input)
        if sushi_dict[sushi_input] == 0:
            cnt += 1
        sushi_dict[sushi_input] += 1
        if len(sushi) == K:
            if sushi_dict[C]>0:
                max_value = max(max_value,cnt)
            else:
                max_value = max(max_value,cnt+1)
    else:
        remove_sushi = sushi.popleft()
        sushi_dict[remove_sushi] -= 1
        if sushi_dict[remove_sushi] == 0:
            cnt -= 1
        sushi.append(sushi_input)
        if sushi_dict[sushi_input] == 0:
            cnt += 1
        sushi_dict[sushi_input] += 1
        if sushi_dict[C]>0:
            max_value = max(max_value,cnt)
        else:
            max_value = max(max_value,cnt+1)

print(max_value)

def check(x,y,size):
    for nx in range(x,x+size):
        for ny in range(y,y+size):
            if result[nx][ny] != 0:
                return False
    return True


def divide_and_fill(x,y,size):
    global numbers
    numbers += 1
    next_size = size//2
    input_position = [[x+next_size-1,y+next_size-1],[x+next_size,y+next_size-1],[x+next_size-1,y+next_size],[x+next_size,y+next_size]]
    for ind,val in enumerate([[x,y],[x+next_size,y],[x,y+next_size],[x+next_size,y+next_size]]):
        sx,sy = val
        input_x,input_y = input_position[ind]
        if check(sx,sy,next_size):
            result[input_x][input_y] = numbers

    if size == 2:
        return
    divide_and_fill(x,y,next_size)
    divide_and_fill(x+next_size,y,next_size)
    divide_and_fill(x,y+next_size,next_size)
    divide_and_fill(x+next_size,y+next_size,next_size)




k= int(input())
N = 2**k
input_x,input_y = map(int,input().split())
x = N-input_y
y = input_x-1
result = [[0 for _ in range(N)] for _ in range(N)]
result[x][y] = -1

numbers = 0
divide_and_fill(0,0,N)
for row in result:
    print(*row)

1

import sys

input = sys.stdin.readline

def union(A,B):
    X = find_parent(A)
    Y = find_parent(B)
    if X != Y:
        if rank[X] < rank[Y]:
            X,Y = Y,X
        make_set[Y] = X
        if rank[X] == rank[Y]:
            rank[X] += 1

def find_parent(ind):
    if make_set[ind] == ind:
        return ind
    else:
        make_set[ind] = find_parent(make_set[ind])
        return make_set[ind]


N,M = map(int,input().split())

make_set = [i for i in range(N+1)]
rank =  [1 for _ in range(N+1)]
for _ in range(M):
    command, A,B = map(int,input().split())

    if command:
        if find_parent(A) == find_parent(B):
            sys.stdout.write('YES\n')
        else:
            sys.stdout.write('NO\n')
    else:
        union(A,B)

import sys

input = sys.stdin.readline

N = int(input())

M = int(input())
S = [0]*N
E = [0]*N
for _ in range(M):
    x, y = map(lambda x : x-1 ,list(map(int,input().split())))

    S[x] += 1
    E[y] += -1




ind = 0
result = 0
big_cnt = 0
while ind<N:
    if big_cnt:
        big_cnt += S[ind] + E[ind]
        if big_cnt == 0:
            result += 1
        ind += 1
    else:
        if S[ind] == 0:
            result += 1
        else:
            big_cnt += S[ind]
        
        ind += 1
print(result)

import sys

input = sys.stdin.readline


N = int(input())
tree = [[-1 for _ in range(2)] for _ in range(N+1)]
for i in range(1,N+1):
    left_ndoe,right_node = map(int,input().split())
    tree[i][0] = left_ndoe
    tree[i][1] = right_node



K = int(input())
cu_node = 1
while K >=0:
    left_or_right = K%2
    
    if tree[cu_node][0] != -1 and tree[cu_node][1] != -1:
        if left_or_right:
            cu_node = tree[cu_node][0]
        else:
            cu_node = tree[cu_node][1]
        K = K//2 + left_or_right
    else:
        if tree[cu_node][0] == -1 and tree[cu_node][1] == -1:
            break
        elif tree[cu_node][1] == -1:
            cu_node = tree[cu_node][0]
        else:
            cu_node = tree[cu_node][1]

print(cu_node)