본문 바로가기

분류 전체보기

 (402)
[백준 16566번] 카드 게임 (Python3) import sys input = sys.stdin.readline from bisect import bisect_right def findparent(x): if check[parent[x]]==0: return parent[x] else: parent[x] = findparent(parent[x]) return parent[x] N,M,K = map(int,input().split()) minsu = [*sorted(map(int,input().split()))] cheolsu = [*map(int,input().split())] check = [0]*M parent = {i:i+1 for i in range(M)} for i in range(K): card = cheolsu[i] idx = bise..
[백준 12015번] 가장 긴 증가하는 부분 수열 2 (Python3) import sys input = sys.stdin.readline def binary(num): l = len(DP) start,end = 0,l-1 while True: if end-start len(DP)-1: DP.append(num) else: if DP[l] > num: DP[l] = num print(len(DP)-1) 가장 긴 증가하는 부분 수열 1과 같은 방식인 O(N^2)으로 제출하면 시간..
[백준 2162번] 선분 그룹 (Python3) import sys input = sys.stdin.readline def findparent(x): if parent[x] == x: return x parent[x] = findparent(parent[x]) return parent[x] def eq(x,y,i): return (x2[i]-x1[i])*(y-y1[i])-(y2[i]-y1[i])*(x-x1[i]) def check(i,j): if eq(x1[j],y1[j],i)*eq(x2[j],y2[j],i)=min(y1[i],y2[i]): return 1 elif (y2[j]-y1[j])*(x2[i]-x1[i]) == (y2[i]-y1[i])*(x2[j]-x1[j]): if y1[i]-(y2[i]-y1[i])/(x2[i]-x1[i])*x1[i] ==..
[백준 2887번] 행성 터널 (Python3) 처음에는 "뭐야 저번에 풀었던 별자리 만들기랑 똑같은 문제 아니야? 너무 쉬운데?" 라고 생각했다. 그래서 별자리 문제를 풀었던 방식대로 모든 노드 사이에 그래프를 생성하고 프림 알고리즘을 이용해서 풀어주려했다. 코드는 다음과 같다. import sys input = sys.stdin.readline from heapq import heappush, heappop N = int(input()) xlist,ylist,zlist = [0]*N,[0]*N,[0]*N for i in range(N): xlist[i],ylist[i],zlist[i] = map(int,input().split()) graph = [[0]*N for i in range(N)] for i in range(N): for j in ran..
[백준 1766번] 문제집 (Python3) import sys input = sys.stdin.readline from heapq import heappop,heappush N,M = map(int,input().split()) indegree = [0]*(N+1) graph = {i:[] for i in range(1,N+1)} for i in range(M): x,y = map(int,input().split()) indegree[y] += 1 graph[x].append(y) hq = [] seq = [] for i in range(1,N+1): if indegree[i] == 0: heappush(hq,i) while hq: now = heappop(hq) seq.append(now) for next in graph[now]: indegr..
[백준 9252번] LCS 2 (Python3) import sys input = sys.stdin.readline from collections import deque seq1 = input().strip() seq2 = input().strip() l = len(seq2) LCS = [0]*l #seq2 길이의 DP 생성 LCSseq = [""]*l for letter in seq1: MAX = 0 seq = "" for i in range(l): if LCS[i] > MAX: MAX = LCS[i] seq = LCSseq[i] else: if seq2[i] == letter: LCS[i] = MAX+1 LCSseq[i] = seq+letter result = [0,""] for i in range(l): if LCS[i]>result[0]: re..
[백준 1202번] 보석 도둑 (Python3) import sys input = sys.stdin.readline from heapq import heappush, heappop N,K = map(int,input().split()) jewel = [] for i in range(N): heappush(jewel,tuple(map(int,input().split()))) bag = [0]*K for i in range(K): bag[i] = int(input()) bag.sort() result = 0 jewel1 = [] for weight in bag: while jewel: if jewel[0][0]>weight: break w,v = heappop(jewel) heappush(jewel1,(-v,w)) if jewel1: v,w = heapp..
[백준 10775번] 공항 (Python3) import sys input = sys.stdin.readline from collections import deque sys.setrecursionlimit(10**6) def findparent(x): if parent[x] == 0: return False if gate[parent[x]] == 0: return parent[x] parent[x] = findparent(parent[x]) return parent[x] G = int(input()) P = int(input()) gate = [0]*(G+1) parent = {i:i-1 for i in range(1,G+1)} result = 0 fail = False for i in range(P): g = int(input()) if fail..

티스토리툴바