dfs를 이런느낌으로 응용할수 있구나를 알았다. 괄호 제거는 좀 설명이 부족해서 질문되있는거 보고 테스트케이스 해보고 해결했다. 중복이 안되고, 제데로 된 수식이 아니면 진행하지 않는다는걸 좀 문제에 써주지;; 14888번 123456789101112131415161718192021222324252627282930313233# 깊이 위주 탐색def dfs(now, index, ns): n1, n2, n3, n4 = ns # 만약 입력값 넘어가면 탐색 종료 if index == c: r.append(now) return # + if n1 > 0: dfs(now + l[index], index + 1, (n1 - 1, n2, n3, n4)) # - if n2 > 0: dfs(now - l[index], in..

dfs는 간단하게 재귀로서 구현할수 있다. 하지만 최적화 하려면 반복문으로 구현해야하는게 사실이긴 하지만 여기선 다 2초줘서 적당히 풀었다. 1182번 123456789101112131415161718192021222324252627a, b = map(int, input().split(' '))l = list(map(int, input().split(' '))) c = 0 # 깊이 위주 서치def dfs(now, index): global c # 배열 길이보다 더 텀색할순 없으니 if index == a: return # 만약 합이 제시된것과 같으면 if now + l[index] == b: # 카운터 추가 c += 1 # 현재값에서 서치된곳의 값을 합치고 넘기고 dfs(now + l[index], in..

큐는 스택이랑 반대쪽인 제일 앞만 건드릴수 있는 자료구조이다. 2161번 12345678q = [i + 1 for i in range(int(input()))] while len(q) != 1: print(q.pop(0), end=' ') q.append(q.pop(0)) print(q[0]) Colored by Color Scriptercs 1966번 12345678910111213141516171819202122232425for i in range(int(input())): a, b = map(int, input().split(' ')) # 프린터 큐 q = [i for i in range(a)] # 랭킹 큐 r = list(map(int, input().split(' '))) n = 0 while ..

스택은 가장 최근에 넣은(마지막에 넣은) 값을 보는 자료구조이다. 파이썬에선 별로 의미가 없지만 스택이라고 생각하고 구현하였다. 10848번 1234567891011121314151617181920212223242526272829stack = list() for i in range(int(input())): in_str = input().split(' ') # PUSH if in_str[0] == 'push': stack.append(int(in_str[1])) # POP if in_str[0] == 'pop': if len(stack) == 0: print(-1) else: print(stack.pop()) # SIZE if in_str[0] == 'size': print(len(stack)) # EM..

lis는 lcs보다 훨씬 쉬워서 놀랐다. 그리고 갱신한 부분 뒤를 신경을 안써도(?) 된다는게 좀 무책임 하다고 생각하지만 최적화가 잘 되서 신기했다. 1234567891011121314151617181920212223c = int(input())l = list(map(int, input().split(' '))) # lis 사용lis = [0, l[0]] for i in range(1, c): # 만약 맨마지막 lis값보다 크면 마지막에 추가 if l[i] > lis[-1]: lis.append(l[i]) else: # 이전 lis를 탐색하며 사이값을 갱신 for j in range(len(lis) - 1, -1, -1): # 만약 탐색중인 것보다 작으면 패스 if l[i] lis[j]: lis[j +..

dp가 재밌어서 은근 많이 했는데 이제 슬슬 그만두고 다음부턴 lcs lis를 공부해볼까 한다. 11057번12345678910a = int(input()) # dp용 배열dp = [None, [1 for i in range(10)]] for i in range(2, a + 1): # 높은 index의 값을 다 더해서 저장 dp.append([sum(dp[i - 1][z:]) for z in range(10)]) print(sum(dp[a]) % 10007)cs2193번12345678910111213a = int(input()) # dp용 배열dp = [None, [1, 1]] for i in range(2, a + 1): # 0으로 시작할떈 다음에 1로시작해도 되고 0으로 시작하도 되고 # 1로 시작할..

dp실력이 늘었다고 생각한다. 어느정도 생각하고 푸니 풀려서 놀랐다. 123456789101112131415161718192021a = int(input()) # dp용 배열 생성dp = [None, [1 for i in range(10)]] # 자리수마다 입력값까지 dp를 생성for i in range(2, a + 1): # 0으로 시작하는 경우는 이전 결과의 0 + 1 값이 이전됨 tmp = [dp[i - 1][1]] # 1~8으로 시작하는 경우는 이전 결과의 i + 1 값과 i - 1 값의 합이 이전됨 for j in range(1, 9): tmp.append(dp[i - 1][j - 1] + dp[i - 1][j + 1]) # 9로 시작하는 경우는 이전 결과의 9 - 1 값이 이전됨 tmp.app..

점화식은 생각났지만 구현하는 부분이 감이 안오다가 바로 깨우치고 만들었다. 1234567891011121314a = int(input())l = list(map(int, input().split(' ')))\ # dp용 배열dp = [0, l[0]] for i in range(2, a + 1): # 이전까지의 계산결과를 dp에 저장하고 # l[i] 와 (여기선 한칸씩 앞으로 되있으니까 i - 1로 코딩) # dp[1] + dp[i - 1], dp[2] + dp[i - 2].... 을 비교해서 가장 큰걸 dp[i]로 넣는다. dp.append(max([dp[z+1] + dp[i - z - 1] for z in range(i//2)] + [l[i - 1]])) print(dp[-1]) Colored by C..

이런 류의 문제를 어떻게 접근할지 몰랐는데 찾아보니 점화식으로 하면 된다더라.그래도 이해가 안되서 5번째까지 직접 써보니 이해가 됐다. 11726번123456789101112131415a = int(input()) # 점화식은 a[n] = a[n - 1] + a[n - 2] 이다# 하지만 피보나치 수열과 다르게 시작은 1번쨰부터 1, 2로 시작한다# 새로 놓여질 블럭이 세로로 세워지면 a[n - 1]의 경우의수,# 새로 놓여질 블럭이 앞에 블럭과 가로로 세워지면 2칸 전인 a[n - 2]의 경우의수를 가진다.dp = [0, 1, 2] for i in range(2, a): dp.append((dp[i] + dp[i-1]) % 10007) print(dp[a]) Colored by Color Scripte..

예전에 풀었던 계단 오르기의 하위호환인데 왜 차례는 더 아래라 그때 고생했을까... 매우 간단하게 풀었다. 1234567891011121314151617181920l = list()for i in range(int(input())): l.append(int(input())) # dp를 위한 배열r = [(0, l[0], l[0])] for i in range(1, len(l)): r.append( ( # 0번쨰 마시는 경우는 이번꺼 합 안하고 이전 경우중 가장 큰거로 저장 max(r[i - 1]), # 1번째랑 2번째는 각각 0번쨰랑 1번쨰에서 지금 양 더해서 저장 r[i-1][0] + l[i], r[i-1][1] + l[i] ) ) # 결과print(max(r[-1]))Colored by Color S..