본문 바로가기

분류 전체보기

(402)
[백준 4225번] 쓰레기 슈트 (Python3) 처음에는 너무 쉬운 문제라고 생각했다. 고등학교 1학년때 배우는 점과 직선사이의 거리 공식을 이용하면 되는거 아닌가? 하고 10분만에 풀었다. (사실 제출조건이 까다로워서 좀 더 걸리기는 했다) 코드는 다음과 같다. import sys,math input = sys.stdin.readline def lineeq(x1,y1,x2,y2): return y2-y1,x1-x2,(x2-x1)*y1-(y2-y1)*x1 test = 1 while 1: N = int(input()) if not N: break point = [] for _ in range(N): point.append([*map(int,input().split())]) result = 1e9 line = [] for n in range(N): a,b..
[백준 1708번] 볼록 껍질 (Python3) import sys,math input = sys.stdin.readline N = int(input()) point = [] for _ in range(N): x,y = map(int,input().split()) point.append((y,x)) point.sort() cospoint = [] sy,sx = point[0] for i in range(1,N): y,x = point[i] cospoint.append(((sx-x)/math.sqrt((x-sx)**2+(y-sy)**2),x,y)) cospoint.sort() convex = [(sx,sy)] for i in range(N-1): cos,x,y = cospoint[i] while len(convex)>1: x1,y1,x2,y2 = *co..
[백준 3015번] 오아시스 재결합 (Python3) import sys input = sys.stdin.readline N,result,stack = int(input()),0,[] for _ in range(N): h = int(input()) while stack and stack[-1][0]1: result += 1 else: result += 1 stack.append([h,1]) else: stack.append([h,1]) print(result) 간단한 문제라고 생각했는데 약간 고려할 요소가 있었다. 기본적인 풀이는 히스토그램 문제 [백준 6549번] 히스토그램에서 가장 큰 직사각형 (Python3) (tistory.com) 와 유사하게 스택을 이용해서 풀어주었다. 알고리즘을 요약하면, 1. stack에는 키와 해당 키의 사람 명수의 리스트를..
[백준 6549번] 히스토그램에서 가장 큰 직사각형 (Python3) import sys input = sys.stdin.readline while True: data = [*map(int,input().split())] N = len(data)-1 if N==0: break result = 0 histogram = [] for i in range(N): h = data[i+1] i1 = i while histogram and histogram[-1][0]>=h: h1,i1 = histogram.pop() result = max(result,h1*(i-i1)) histogram.append((h,i1)) while histogram: h,i = histogram.pop() result = max(result,h*(N-i)) print(result) 히스토그램 [백준 172..
[백준 13977번] 이항계수와 쿼리 (Python3) import sys input = sys.stdin.readline mod = 1000000007 def cal(x,n): if n == 1: return x cal2 = cal(x,n//2) if n%2: return cal2*cal2*x %mod else: return cal2*cal2 %mod factorial = [1] for i in range(1,4000001): factorial.append(factorial[i-1]*i%mod) M = int(input()) for _ in range(M): N,K = map(int,input().split()) print(factorial[N]*cal((factorial[K]*factorial[N-K])%mod,mod-2)%mod) 이항계수 3 [백준 1..
[백준 1761번] 정점들의 거리 (Python3) import sys input = sys.stdin.readline from collections import deque from math import log2 def findparent(x,d): global result for i in range(logd+1): if d&(1
[백준 14427번] 수열과 쿼리 15 (Python3) import sys input = sys.stdin.readline import heapq N = int(input()) data = [0]+[*map(int,input().split())] hq = [] for i in range(1,N+1): heapq.heappush(hq,(data[i],i)) for _ in range(int(input())): Q = [*map(int,input().split())] if Q[0] == 1: q,i,v = Q data[i] = v heapq.heappush(hq,(v,i)) else: while data[hq[0][1]] != hq[0][0]: heapq.heappop(hq) print(hq[0][1]) 간단한 우선순위 큐 문제. 1. 모든 데이터를 인덱스와 함..
[백준 2008번] 사다리 게임 (Python3) import sys input = sys.stdin.readline from heapq import heappush,heappop N,M = map(int,input().split()) #가로 n 세로 m a,b,erase,draw = map(int,input().split()) graph = {(n,m):[((n,m+1),0)] for n in range(1,N+1) for m in range(M+1)} for m in range(M): n = int(input()) graph[(n,m)] = [((n+1,m+1),0),((n,m+1),erase)] graph[(n+1,m)] = [((n,m+1),0),((n+1,m+1),erase)] for n in range(1,N+1): for m in range..