알고리즘

가운데를 말해요

import heapq import sys def BOJ1655(): n = int(sys.stdin.readline()) leftheap = [] rightheap = [] for _ in range(n) : input_num = int(sys.stdin.readline()) if len(leftheap) == len(rightheap) : heapq.heappush(leftheap, (-input_num, input_num)) else : heapq.heappush(rightheap, (input_num, input_num)) if rightheap and leftheap[0][1] > rightheap[0][1] : leftmin = heapq.heappop(leftheap)[1] rightmin ..

아기 상어 [백준 16236] - python

import heapq def BOJ16236() : n = int(input()) graph = [] q = [] for i in range(n) : line = list(map(int, input().split())) graph.append(line) for j in range(len(line)) : if line[j] == 9 : heapq.heappush(q, (0, i, j)) graph[i][j] = 0 direction = [[0,1], [0,-1], [1,0], [-1,0]] result = 0 body, eat = 2, 0 visited =[[0] * n for _ in range(n)] while q : dist, curr_x, curr_y = heapq.heappop(q) if 0 <..

테트로미노 [백준 14500] - python

def BOJ14500() : global result n,m = map(int, input().split()) graph = [] for _ in range(n) : graph.append(list(map(int, input().split()))) visited = [[0] * m for _ in range(n)] direction = [[0,1], [0,-1], [1,0], [-1,0]] result = 0 middle_finger_tetromino = [[[0,1], [0,2], [1,1]], [ [0,1], [0,2], [-1,1]], [[1,0], [2,0], [1,1]], [[1,0], [2,0], [1,-1]]] def dfs(x, y, count, number, visited): globa..

미로 탐색 [백준 2178] - python

import sys input = sys.stdin.readline INF = 1e9 def BOJ2178() : global graph global result global N, M def dfs(x, y, count) : stack = [] directions = [[1, 0], [-1, 0], [0, 1], [0, -1]] result[x][y] = count stack.append([x, y, count]) while stack : curr_x, curr_y, curr_count = stack.pop() for dir_x, dir_y in directions : next_x = curr_x + dir_x next_y = curr_y + dir_y next_count = curr_count + 1 ..

Wifi Setup [백준 5864] - python

import sys input = sys.stdin.readline INF = 1e11 def BOJ5864(): N, A, B = map(int, input().split()) dp = [INF for _ in range(1000001)] cows = [] for _ in range(N): curr_cow = int(input()) cows.append(curr_cow) cows.sort() curr_wifi = cows[0] dp[curr_wifi] = A for i in range(1, len(cows)): dp[cows[i]] = min(dp[cows[i-1]] + B * (cows[i] - cows[i-1]) / 2, dp[cows[i-1]] + A) # B * (cows[i] - cows[i-..

로봇 청소기 [백준 14503] - python

from collections import deque import sys input = sys.stdin.readline def BOJ14503() : global N, M global directions global cleared global graph def bfs(r, c, d) : queue = deque() queue.append([r, c, d]) while queue : x, y, direction = queue.popleft() flag = True for dir_x, dir_y, dir in directions[direction] : n_x = x + dir_x n_y = y + dir_y n_dir = dir if 0

돌 게임 [백준 9655] - python

import sys from collections import deque input = sys.stdin.readline def BOJ9655() : N = int(input()) players = ["SK", "CY"] dp = [3 for _ in range(1001)] dp[0] = 1 for i in range(1001) : if dp[i] != 3 : player = dp[i] next_player = player ^ 1 if i + 1 < 1001 : dp[i+1] = next_player if i + 3 < 1001: dp[i+3] = next_player print(players[dp[N]]) BOJ9655() 접근 방법 : 1. 돌 개수를 배열로 선언하고 각 개수일때에 어느 플레이어가 가..

토마토 [백준 7576] - python

from collections import deque import sys input = sys.stdin.readline RIPE = 1 UN_RIPE = 0 def BOJ7576() : global M, N directions = [[1, 0], [-1, 0], [0, 1], [0, -1]] def bfs(graph) : queue = deque() temp = [[-1 for _ in range(M)] for _ in range(N)] visited = [[False for _ in range(M)] for _ in range(N)] for i in range(N) : for j in range(M) : if graph[i][j] == 0 : continue temp[i][j] = 0 if graph..

평균은 넘겠지[백준 - 4344] - python

import math import sys input = sys.stdin.readline def BOJ4344() : C = int(input()) for _ in range(C) : inputs = list(map(int, input().split())) total = inputs[0] scores = inputs[1:] standard = sum(scores) / total over_standard_scores = list(filter(lambda x: float(x) > standard, scores)) # result = math.floor(((len(over_standard_scores) / total * 100) + 0.0005) * 1000) / 1000 result = round((len(..

1,2,3 더하기 [백준 9095] - python

import sys input = sys.stdin.readline def BOJ9095() : T = int(input()) dp = [0] * 12 dp[1] = 1 dp[2] = 2 dp[3] = 4 for i in range(4, 12) : dp[i] = dp[i-3] + dp[i-2] + dp[i-1] for _ in range(T) : print(dp[int(input())]) BOJ9095() 접근 방법 : dp 문제이다. 4를 만드는 경우의 수부터 접근 해보자. 4는 1. 1을 만드는 경우의 수들에서 3하나를 추가해주면 된다 2. 2를 만드는 경우의 수들에서 2하나를 추가해주면 된다 3. 3을 만드는 경우의 수들에서 1하나를 추가해주면 된다 4를 만드는 경우의 수는 1을 만드는 경우의 수 ..