one Book a Day

움직인 구름의 경우 추후 제외하고 구름을 생성하기 위해 set으로 관리. 움직이기 전 구름은 list로 뺐다 넣었다 하면서 관리. 이동은 N의 나머지로 관리 import sys input = sys.stdin.readline N, M = map(int, input().split()) A = [list(map(int, input().split())) for _ in range(N)] moves = [tuple(map(int, input().split())) for _ in range(M)] delta = ((0, 0), (0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1)) check = ((-1, 1), (1, 1), (-1, -1),..

단순히 영역을 나누는 문제였습니다. 대각선에 대해 4번 범위 설정이 필요한 문제였습니다. 핵심은 1개씩 늘어나거나 줄어드는 dx, dy설정을 어떻게 할 것인가? 결국 i에서 i의 초깃값을 빼주면 0부터 시작한 다는 것을 알 수 있었습니다. import sys input = sys.stdin.readline N = int(input()) matrix = [list(map(int, input().split())) for _ in range(N)] answer = float('inf') total = 0 for i in range(N): for j in range(N): total += matrix[i][j] for x in range(N - 1): for y in range(1, N - 1): for d1 ..

처음에 상어끼리 잡아먹는다는 문장을 못봐서 헤멤. 본 후에는 heap기반 -> 2차원 배열 직접 생성으로 바꿔서 품. import sys input = sys.stdin.readline def move_shark(): new_board = [[0 for _ in range(C)] for _ in range(R)] for x in range(R): for y in range(C): if not board[x][y]: continue t_x, t_y = x, y s, d, z = board[t_x][t_y] total = s if d == 0 or d == 1: s %= 2 * R - 2 while s: if (t_x == R - 1 and d == 1) or (t_x == 0 and d == 0): d ^..

기본적인 투포인터 문제. 합에 따라 크기를 증감시키며 슬라이딩 시켰습니다. import sys input = sys.stdin.readline N, M = map(int, input().split()) arr = list(map(int, input().split())) left, tmp, cnt = 0, 0, 0 for right in range(N): tmp += arr[right] while tmp > M: tmp -= arr[left] left += 1 if tmp == M: cnt += 1 print(cnt)

행렬의 곱셈을 연습하는 문제이다. 각 항을 어떻게 표현 할 것인가? 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)