one Book a Day

행렬의 곱셈을 연습하는 문제이다. 각 항을 어떻게 표현 할 것인가? 2x2 행렬의 i행 j열의 요소는 두개의 요소의 곱이 두개씩 합해져 들어간다. def matrix_mult(a, b): ret = [[0 ,0], [0, 0]] for i in range(2): for j in range(2): for k in range(2): ret[i][j] += (a[i][k] * b[k][j]) % MOD return ret n = bin(int(input()))[2:] MOD = 1000000007 base = [[1, 1], [1, 0]] answer = [[1, 0], [0, 1]] for i in range(1, len(n) + 1): if n[-i] == '1': answer = matrix_mult(a..

플로이드 워셜 기본문제 각 기점에 대해 모든 경로를 전수조사한다. 한번당 기점 하나를 거치는 경로이다. import sys input = sys.stdin.readline n, m = int(input()), int(input()) bus_datas = [[float('inf')] * n for _ in range(n)] for _ in range(m): a, b, c = map(int, input().split()) bus_datas[a - 1][b - 1] = min(bus_datas[a - 1][b - 1], c) for k in range(n): bus_datas[k][k] = 0 for i in range(n): for j in range(n): if bus_datas[i][j] > bus_da..

분할 정복 in_order로 root기준 오른쪽 왼쪽을 나누고 post_order로 root를 찾는다. import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) def find_tree(in_left, in_right, post_left, post_right): if in_left > in_right or post_left > post_right: return root = post_order[post_right] root_idx = in_order_idx[root] pre_order.append(root) left_size = root_idx - in_left find_tree(in_left, root_idx - 1, post_left, po..

오랜만에 푸는 LCS(substring), string과 편집거리도 같이 연습했습니다. import sys input = sys.stdin.readline a, b = input().strip(), input().strip() n, m = len(a), len(b) dp = [[0] * (m + 1) for _ in range(n + 1)] for i in range(n): for j in range(m): dp[i + 1][j + 1] = dp[i][j] + 1 if a[i] == b[j] else max(dp[i + 1][j], dp[i][j + 1]) print(dp[-1][-1])

시작정점을 어디로 두어야 하는가? 초기 최단거리값을 float('inf)가 아닌 정수로 두어야 하는 이유가 무엇인가? 두가지에 대해 고민해볼 필요가 있는 문제 두 가지 조건에 따라 시작 지점에서 도달 할 수 있는 또는 도달할 수 없는 음수 사이클 판별 가부가 결정된다. import sys input = sys.stdin.readline def bellman_ford(start): dists[start] = 0 for cycle in range(n): for cur_node, next_node, cost in edges: if dists[cur_node] + cost < dists[next_node]: dists[next_node] = dists[cur_node] + cost if cycle == n - ..

그리디하게 맨 뒷 자리가 짝수면 2로 나누고 1이면 1빼면 된다. import sys input = sys.stdin.readline A, B = map(int, input().split()) cnt = 1 while A != B: if A > B or (B % 10 != 1 and B % 2 != 0): cnt = -1 break if B & 1: B //= 10 cnt += 1 else: B //= 2 cnt += 1 print(cnt)

시간초과가 나오는 code이다. import sys input = sys.stdin.readline from bisect import bisect_right from math import factorial MOD = int(1e9) + 7 for test in range(int(input())): n, m, k = map(int, input().split()) arr = list(map(int, input().split())) arr.sort() done = {} answer = 0 for i in range(n - m + 1): if arr[i] not in done: right = bisect_right(arr, arr[i] + k) done[arr[i]] = right length = done[ar..

map으로 나보다 2큰수의 위치를 저장해둔 후 거기까지 사이의 갯수에서 나포함 3개를 뽑으면 된다. import sys input = sys.stdin.readline from bisect import bisect_left for test in range(int(input())): n = int(input()) arr = list(map(int, input().split())) arr.sort() done = {} answer = 0 for i in range(n - 2): if arr[i] not in done: right = bisect_left(arr, arr[i] + 3) done[arr[i]] = right length = done[arr[i]] - i if length > 2: length -..

숫자의 합이 되는 최소 길이의 숫자조합을 구합니다. 최소길이이므로 큰수부터 빼주며 숫자를 만들면 됩니다. 1~45까지의 모든 수는 표현이 가능하다는 것만 이해하면 됩니다. import sys input = sys.stdin.readline for test in range(int(input())): x = int(input()) answer, flag = '', 0 for num in range(9, 0, -1): if x >= num: x -= num answer += str(num) if not x: print(answer[::-1]) break else: print(-1)

2020을 한번만 제외하고 만들 수 있는지 여부를 확인하는 문제입니다. 중간에 한번밖에 못띄우니 앞, 뒤에 2020의 모든 숫자가 존재해야합니다. import sys input = sys.stdin.readline for test in range(int(input())): n = int(input()) s = input().rstrip() answer = '2020' if s[0] + s[-3:] == answer or s[:2] + s[-2:] == answer or s[:3] + s[-1] == answer or s[:4] == answer or s[-4:] == answer: print("YES") else: print("NO")