너무 어려웠다. 아직도 로직이 이해가 안간다. 12345678910111213141516171819202122232425262728293031323334while True: l = list(map(int, input().split(' '))) n = l[0] # 0이면 탈출 if n == 0: break l = l[1:] mx = 0 stack = [0] # 전체 탐색 for i in range(1, n): # 스텍이 비어있지 않고, 탐색할 곳이 지금보다 클때 while len(stack) != 0 and l[stack[-1]] > l[i]: # 맨 위의 값 출력 tmp = stack.pop() # 만약 출력하고 스택이 비면 if len(stack) != 0: w = i - stack[-1] - 1 el..

bfs를 사용하면 된다는 것은 바로 감이왔다. 방법을 2가지를 만들었다. 첫째는 이미 간 곳을 count로 저장하여 돌아가는 로직 둘째는 이중 반복으로 q를 끝까지 다 돌아야지 count를 1씩 올리는 로직 1번 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849a, b = map(int, input().split(' ')) # 카운터 저장용visited = [-1 for i in range(100002)]# 첫번째 카운터는 0visited[a] = 0# 큐에 넣기q = [a] while q: # 앞쪽 값을 뺴옴 now = q.pop(0) # 결과값이랑 같으면 출력 if now == b: prin..

dfs는 스택, bfs는 큐를 활용한다는걸 스택이랑 큐를 배우고 나서 알았다. 재귀로 구현할땐 아니긴 하지만 for문으로 최적화할땐 꼭 필요해보인다. 1260번 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152d, c, r = map(int, input().split(' ')) # 그래프 만들기graph = dict()for i in range(1, d+1): graph[i] = list() for i in range(c): a, b = map(int, input().split(' ')) graph[a].append(b) graph[b].append(a) for i in range(d..

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..