본문 바로가기

전체 글263

[백준] 15961번 - 회전 초밥 # 회전 초밥 from collections import defaultdict N, d, k, c = map(int, input().split()) arr = [int(input()) for _ in range(N)] arr += arr[:k-1] left, right = 0, k result = 0 dict = defaultdict(int) dict[c] += 1 for x in arr[left:right]: dict[x] += 1 while right < len(arr): result = max(result, len(dict)) dict[arr[left]] -= 1 dict[arr[right]] += 1 if dict[arr[left]] == 0: dict.pop(arr[left]) left += 1.. 2022. 5. 3.
[백준] 1507번 - 궁금한 민호 (파이썬) # 궁금한 민호 N = int(input()) arr = [] for _ in range(N): arr.append(list(map(int, input().split()))) road = [[True]*N for _ in range(N)] # 플로이드 와샬 역으로 result = 0 for k in range(N): for i in range(N): if i != k: for j in range(N): if i != j and k != j: if arr[i][j] == arr[i][k]+arr[k][j]: road[i][j] = False elif arr[i][j] > arr[i][k]+arr[k][j]: result = -1 if not result: for i in range(N): for j in .. 2022. 5. 2.
[백준] 3584번 - 가장 가까운 공통 조상 (파이썬) # 가장 가까운 공통 조상 def find_parent(parent, x): result = [x] while parent[x]: result.append(parent[x]) x = parent[x] return result T = int(input()) for _ in range(T): N = int(input()) parent = [0 for _ in range(N+1)] for _ in range(N-1): a, b = map(int, input().split()) parent[b] = a x, y = map(int, input().split()) # 각 부모 리스트 정의 x_parent = find_parent(parent, x) y_parent = find_parent(parent, y) # 깊.. 2022. 5. 1.
[백준] 16197번 - 두 동전 (파이썬) # 두 동전 import copy from collections import deque N, M = map(int, input().split()) arr = [] money = deque() for i in range(N): arr.append(list(input().strip())) for j in range(M): if arr[i][j] == 'o': money.append((i, j)) arr[i][j] = '.' visited = set() visited.add(''.join(map(str, money))) dx = [0, 1, 0, -1] dy = [1, 0, -1, 0] def bfs(): q = deque() q.append((0, money)) while q: cnt, now = q.pop.. 2022. 4. 20.
[백준] 16916번 - 부분 문자열 (파이썬) # 부분 문자열 P, S = input().strip(), input().strip() def get_table(x): arr = [0 for _ in range(len(x))] j = 0 for i in range(1, len(x)): while j > 0 and x[i] != x[j]: j = arr[j-1] if x[i] == x[j]: j += 1 arr[i] = j return arr def kmp(word, find): result = 0 j = 0 for i in range(len(word)): while j > 0 and word[i] != find[j]: j = table[j-1] if word[i] == find[j]: if j == len(find)-1: result += 1 j = .. 2022. 4. 18.
[백준] 2234번 - 성곽 (파이썬) # 성곽 import sys from collections import deque from collections import defaultdict input = sys.stdin.readline M, N = map(int, input().split()) arr = [] for _ in range(N): arr.append(list(map(int, input().split()))) # 방향은 8,4,2,1 순서로 남,동,북,서 dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] def bfs(a, b, arr, visited, room_num): q = deque() q.append((a, b)) visited[a][b] = room_num room_size = 1 while q: x, y.. 2022. 4. 17.
[백준] 24042번 - 횡단보도 (파이썬) # 횡단보도 import heapq import sys input = sys.stdin.readline N, M = map(int, input().split()) arr = [[] for _ in range(N+1)] for i in range(M): a, b = map(int, input().split()) arr[a].append((i, b)) arr[b].append((i, a)) def dijkstra(): q = [] heapq.heappush(q, (0, 1)) visited = [sys.maxsize for _ in range(N+1)] visited[1] = 0 while q: time, node = heapq.heappop(q) if node == N: return time if visi.. 2022. 4. 16.

티스토리툴바