Algorithm/BOJ133 [백준] 5427번 - 불 (파이썬) # 불 from collections import deque import sys input = sys.stdin.readline dx = [0, 1, 0, -1] dy = [1, 0, -1, 0] def burn(): for _ in range(len(fire)): x, y = fire.popleft() for k in range(4): nx = x + dx[k] ny = y + dy[k] if 0 2022. 2. 2. [백준] 11657번 - 타임머신 (파이썬) # 타임머신 import sys input = sys.stdin.readline MAX = sys.maxsize N, M = map(int, input().split()) bus = [] for _ in range(M): a, b, time = map(int, input().split()) bus.append((a, b, time)) dist = [MAX] * (N+1) def bf(start): dist[start] = 0 for k in range(N): for i in range(M): city, ncity, time = bus[i] if dist[city] != MAX and dist[ncity] > dist[city] + time: dist[ncity] = dist[city] + time if .. 2022. 2. 1. [백준] 2437번 - 저울 (파이썬) # 저울 import sys input = sys.stdin.readline N = int(input()) arr = list(map(int, input().split())) arr.sort() result = 0 sum = 0 for i in range(N): if sum+1 >= arr[i]: sum += arr[i] else: result = sum+1 break if result == 0: result = sum+1 print(result) 그리디 1. 저울의 무게를 담은 리스트를 정렬해준다 2. 현재까지의 무게의 합 + 1보다 다음에 리스트에 넣어줄 값이 더 크면 중간에 공백이 나오는 것을 이용 - (sum+1) >= (다음무게) 이면, (현재까지의 무게의합) += (다음무게) - 더 크면 공백.. 2022. 1. 31. [백준] 1300번 - K번째 수 (파이썬) # K번째 수 N = int(input()) k = int(input()) start, end = 1, k result = 0 while start = k: result = mid end = mid - 1 else: start = mid + 1 print(result) 이진탐색 B리스트는 정렬된 상태라고 문제에 적혀져있다. 이분탐색을 사용 B[k]는 항상 k보다 작거나 같기 때문에 end를 k로 지정해준다. 1. start가 end보다 작거나 같을 동안 이진 탐색 수행 - count : mid보다 작은 수들의 개수 - 해당 열에서 X보다 작은 수의 개수는 X를 해당 열의개수(1~N)으로 나눈값 (단, N보다 커질 수 없음) 2. count == k 이면 result를 출력 아 좀 많이 해맸다... 이진탐.. 2022. 1. 31. [백준] 9466번 - 텀 프로젝트 (파이썬) # 텀 프로젝트 import sys input = sys.stdin.readline sys.setrecursionlimit(100001) def dfs(x): global result visited[x] = True cycle.append(x) if visited[student[x]]: if student[x] in cycle: result += cycle[cycle.index(student[x]):] return else: dfs(student[x]) T = int(input()) for _ in range(T): N = int(input()) student = list(map(int, input().split())) student.insert(0, 0) visited = [False] * (N+1) .. 2022. 1. 31. [백준] 1202번 - 보석 도둑 (파이썬) # 보석 도둑 import sys import heapq input = sys.stdin.readline N, K = map(int, input().split()) gem = [] for _ in range(N): weight, cost = map(int, input().split()) heapq.heappush(gem, (weight, cost)) bags = [] for _ in range(K): w = int(input()) bags.append(w) bags.sort() result = 0 temp = [] for bag_weight in bags: while gem: if bag_weight >= gem[0][0]: weight, cost = heapq.heappop(gem) heapq.heap.. 2022. 1. 30. [백준] 17135번 - 캐슬 디펜스 (파이썬) # 캐슬 디펜스 import copy import sys input = sys.stdin.readline MAX = sys.maxsize N, M, D = map(int, input().split()) arr = [] enemy = [] for i in range(N): arr.append(list(map(int, input().split()))) for j in range(M): if arr[i][j] == 1: enemy.append([i, j]) enemy.sort(key=lambda x: x[1] arch = [] target = [] result = 0 def archPositon(count, k): if count == 3: temp = copy.deepcopy(arr) tenemy = cop.. 2022. 1. 30. 이전 1 ··· 11 12 13 14 15 16 17 ··· 19 다음
