알고리즘

쿼드트리 [백준 1992] - python

import sys input = sys.stdin.readline def BOJ1992() : global graph def check(x, y, step) : flag = True pivot = graph[x][y] for i in range(x, x + step) : for j in range(y, y + step) : if graph[i][j] != pivot : flag = False break if flag == False : print("(", end='') step //= 2 check(x, y, step) check(x, y+step, step) check(x+step, y, step) check(x+step, y+step, step) print(")", end='') elif pivot..

카잉 달력 [백준 6064] - python

import sys input = sys.stdin.readline def BOJ6064() : def getYear(M, N, x, y) : MAX_NUM = M * N while x

플로이드 [백준 11404] - python

import sys input = sys.stdin.readline def BOJ11404() : n = int(input()) m = int(input()) dist = [[1e9 for _ in range(n)] for _ in range(n)] for _ in range(m) : a, b, c = list(map(int, input().split())) dist[a - 1][b - 1] = min(dist[a-1][b-1], c) for k in range(n) : for i in range(n) : for j in range(n) : if dist[i][k] != 0 and dist[k][j] != 0 : dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j..

촌수계산[백준 2644] - python

from collections import deque import sys input = sys.stdin.readline def BOJ2644() : global graph global visited global answer def bfs(start) : queue = deque() queue.append([start, 0]) while queue : node, relation = queue.popleft() for i in range(len(graph[node])) : if visited[i] == False and graph[node][i] == 1 : visited[i] = True answer[i] = relation + 1 queue.append([i, relation + 1]) n = int(..

파일 합치기[백준 11066] - python

import sys input = sys.stdin.readline INF = 1e9 def BOJ11066() : global files global presum global cache def dp(start, end) : if start == end : return files[start] if cache[start][end] != 0 : return cache[start][end] result = INF sum = presum[end+1] - presum[start] for i in range(start, end) : result = min(result, dp(start, i) + dp(i+1, end) + sum) cache[start][end] = result return result T = in..

스티커[백준 9465] - python

import sys input = sys.stdin.readline def BOJ9465() : T = int(input()) for _ in range(T) : n = int(input()) sticker = [] for _ in range(2) : sticker.append(list(map(int, input().split()))) dp = [[0 for _ in range(n)] for _ in range(2)] dp[0][0], dp[1][0] = sticker[0][0], sticker[1][0] for i in range(1, n) : dp[0][i] = max(dp[1][i-1] + sticker[0][i], dp[0][i-1]) dp[1][i] = max(dp[0][i-1] + sticke..

DFS와 BFS [백준 1260] - python

from collections import deque import sys input = sys.stdin.readline def BOJ1260(): def dfs(start, visited, graph): stack = [] stack.append(start) print(start, end=" ") while stack: node = stack.pop() visited[node] = True for next in range(1, len(graph[node])): if visited[next] == False and graph[node][next] == 1: visited[next] = True dfs(next, visited, graph) def bfs(start, visited, graph): queu..

편의점 2 [백준 14400] - python

import sys input = sys.stdin.readline def BOJ14400(): n = int(input()) l = [] a = [] b = [] for _ in range(n) : x, y = list(map(int, input().split())) a.append(x) b.append(y) l.append([x,y]) a.sort() b.sort() x_median = a[len(a)//2] y_median = b[len(b)//2] result = 0 for x, y in l : result += abs(x-x_median) + abs(y-y_median) print(result) BOJ14400() 접근 방법 : 1. 두 위치의 거리는 맨하탄 거리로 구한다. 거리합을 최소로 하는..

행렬 곱셈 순서 [백준 11049] -python

import sys input = sys.stdin.readline INF = 2**31 def BOJ11049() : N = int(input()) l = [] for _ in range(N) : l.append(list(map(int, input().split()))) dp = [[0 for _ in range(N+1)] for _ in range(N+1)] # dp[i][j] = 행렬 i 부터 j까지의 곱의 최솟값 for i in range(1, len(l)+1) : # 0 1 2 3 for j in range(N-i) : # 4 (0, 1, 2, 3), 3 (0, 1, 2), 2 (0, 1), 1 (0) if i == 1 : dp[j][j+1] = l[j][0] * l[j][1] * l[j+1][..

Dance Dance Revolution [백준 2342] - python

import sys input = sys.stdin.readline INF = 1e8 def BOJ2342() : def get_distance(curr, target) : if curr == target : return 1 elif curr == 0 : return 2 elif abs(curr - target) % 2 == 0 : return 4 else : return 3 l = list(map(int, input().split())) # dp[n 번째 움직임][왼발위치][오른발위치] dp = [[[INF for _ in range(5)] for _ in range(5)] for _ in range(len(l)+1)] dp[0][0][0] = 0 for i in range(1, len(l)) : mo..