from collections import defaultdict import heapq hour=defaultdict(int) order=defaultdict(list) cnt=defaultdict(int) n=int(input()) for i in range(1,n+1): m=list(map(int,input().split())) hour[i]=m[0] if m[1]==-1: continue for j in m[1:-1]: order[j].append(i) # i이전에 j가 성행한다 cnt[i]+=1 q=[] ans=[0]*(n+1) for i in range(1,n+1): if cnt[i]==0: q.append(i) ans[i]=hour[i] while q: x=q.pop() for y in ord..
height: 현재 번호 작업을 하기 위한 우선순위 작업들을 담고 있다 cost: 현재 작업의 비용(시간) 모든 작업을 돌면서 현재 번호를 작업하기 위해 먼저 해야할 작업들의 비용의 최대값(여러 작업을 동시에 할 수 있다는 조건이 있다)에 현재 작업의 시간을 더한 것이 현재 번호를 작업하는 걸리는 시간이다 from collections import defaultdict import heapq height=defaultdict(list) cost=defaultdict(int) n=int(input()) for i in range(1,n+1): c=list(map(int,input().split())) cost[i]=c[0] if c[1]==0: continue for j in c[2:]: height[i]..
위상정렬 + 우선순위큐 문제번호가 작은 것 부터 풀어야된다 from collections import defaultdict import heapq height=defaultdict(list) cnt=defaultdict(int) q=[] n,m=map(int,input().split()) for i in range(m): a,b=map(int,input().split()) height[a].append(b) cnt[b]+=1 # b이전에 a가 선행된다 for i in range(1,n+1): if cnt[i]==0: q.append(i) result=[] while q: x=heapq.heappop(q) result.append(x) for j in height[x]: cnt[j]-=1 if cnt[j]..
from collections import defaultdict from collections import deque height=defaultdict(list) cnt=defaultdict(int) dq=deque() n,m=map(int,input().split()) for i in range(m): a,b=map(int,input().split()) height[a].append(b) cnt[b]+=1 # b이전에 a가 선행된다 for i in range(1,n+1): if cnt[i]==0: dq.append(i) result=[] while dq: x=dq.popleft() result.append(x) for j in height[x]: cnt[j]-=1 if cnt[j]==0: dq.appe..
www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 �� www.acmicpc.net 다익스트라 유형 import sys import collections import heapq t=int(sys.stdin.readline()) for kk in range(t): n,d,c=map(int,sys.stdin.readline().split()) graph=collections.defaultdict(list) for i in range(d): a,b,s=map(int,sys.stdin.readlin..
import sys import collections import heapq V,E=map(int,sys.stdin.readline().split()) K=int(sys.stdin.readline()) graph=collections.defaultdict(list) for i in range(E): u,v,w=map(int,sys.stdin.readline().split()) graph[u].append((v,w)) dist=collections.defaultdict(int) q=[(0,K)] while q: time,node=heapq.heappop(q) if node not in dist: dist[node]=time for v,w in graph[node]: alt=time+w heapq.heapp..
1. python import collections import sys sys.setrecursionlimit(2000) def dfs(x): visited[x]=True print(x,end=' ') for y in sorted(dict[x]): if not visited[y]: dfs(y) def bfs(x): visited[x]=True dq=collections.deque() dq.append(x) while dq: cur=dq.popleft() print(cur,end=' ') for y in sorted(dict[cur]): if not visited[y]: visited[y]=True dq.append(y) n,m,v=map(int,sys.stdin.readline().split()) dic..
2개씩 짝을 지어 최소값들의 합의 최대값을 구하는 것은 정렬된 배열을 2개씩 묶어서 구하면 된다. 정렬된 수이므로 각 짝의 최대값은 인덱스가 짝수인 수들이며 sorted(nums)[::2]를 통해 짝수번째 수들만 구할 수 있다. class Solution: def arrayPairSum(self, nums: List[int]) -> int: print(sorted(nums)[::2]) return sum(sorted(nums)[::2]) # nums.sort() # result=0 # pair=[] # for i in range(1,len(nums),2): # pair=[nums[i],nums[i-1]] # result+=min(pair) # pair=[] # return result
* 알게 된 것 check.values()의 리턴이 배열 형태가 아닌 줄 알고 또 따로 배열을 만들어서 처리해줬었는데 배열로 리턴이 되는 것 같다. sorted는 리스트 형태로 반환한다. sorted(문자열)은 문자열의 각 단어를 정렬한 리스트를 반환해준다. from collections import defaultdict class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: check=defaultdict(list) for item in strs: # print(''.join(sorted(item))) sortedWord=''.join(sorted(item)) check[sortedWord].append(item) ret..
문제 어떤 수열을 읽고, 홀수번째 수를 읽을 때 마다, 지금까지 입력받은 값의 중앙값을 출력하는 프로그램을 작성하시오. 예를 들어, 수열이 1,5,4,3,2 이면, 홀수번째 수는 1번째 수, 3번째 수, 5번째 수이고, 1번째 수를 읽었을 때 중앙값은 1, 3번째 수를 읽었을 때는 4, 5번째 수를 읽었을 때는 3이다. 입력 첫째 줄에 테스트 케이스의 개수 T(1