영최의 개발켈로그

[위상정렬] (백준_2252) 줄세우기 - 파이썬 (다시 풀 문제는 아님)

✅ 위상정렬 기본 문제from collections import dequeN,M = map(int,input().split())G = [[] for _ in range(N+1)]indegree = [0]*(N+1)for _ in range(M): a,b = map(int,input().split()) G[a].append(b) indegree[b]+=1q = deque()for i in range(1,N+1): if indegree[i]==0: q.append(i)while q: v = q.popleft() print(v, end=" ") for nv in G[v]: indegree[nv]-=1 if indegree[nv]==0:..

[다익스트라/플로이드워셜] (백준_2660) 회장뽑기 - 파이썬

✅ 이문제 처음 접근할 때 친구-친구(2점) -> G[a][b]==G[b][c] ; O(n^3)...친구-친구-친구-친구-친구-친구(5점) -> G[a][b]==G[b][c]==G[c][d]==G[d][e]==G[e][f] ; O(n^6)이렇게 생각해서 뭐야 플로이드워셜로 풀면 시간 오류 뜨겠는데 생각해서 1) 다익스트라를 N번 돌려서 풀었는데 ,2) 플로이드워셜을 DP랑 같이 사용해서 풀 수도 있는 문제였다. ✅ 처음 다익스트라로 풀때 실수했던 부분:처음 시작점을 지나고 나서 distance[start][nv] = nddistance[nv][start] = nd -> 이부분까지 갱신을 해줬는데 그러면 안된다.왜냐면 Dijkstra의 알고리즘에서 거리는 특정 시작 노드에서 다른 노드까지 한 방향으로만 계..

✅ 두 사람이 친구이거나, A와 친구이고, B와 친구인 C가 존재해야 된다. => 바로 플로이드 워셜 점화식 떠올림✅ 플로이드 워셜에서 주의할 점 a!=b여야함 명심 N = int(input())G = [list(input()) for _ in range(N)]V = [[0]*N for _ in range(N)]for k in range(N): for a in range(N): for b in range(N): if a == b: continue if G[a][b]=="Y" or (G[a][k]=="Y" and G[k][b]=="Y"): V[a][b]=1answer = 0for row in V:..

✅ X,Y,Z마다 정렬하는게(3번) 힙을 각각 X,Y,Z마다 만들고 빼는것보다 빠름 정렬 사용) 총 시간 복잡도: O(N) + O(N log N) + O(N) = O(N log N)힙 사용) 총 시간 복잡도: O(N log N) + O(N log N) + O(N) = O(N log N)아무래도 힙을 넣는데서 더 오래걸리는 것 같음  ✅ 통과 코드 (정렬 사용)from heapq import heappop,heappushN = int(input())hangsungs = [list(map(int,input().split()))+[i] for i in range(N)]q = []visited = [0]*(N)G = [[] for _ in range(N)]for i in range(3): hangsungs..

링크: https://school.programmers.co.kr/learn/courses/30/lessons/42583✅ bridge의 길이를 유지하기 위해 0으로 채우고 시간이 지날때마다 우선 popleft✅ sum 대신 total을 써야 시간 초과안남from collections import dequedef solution(bridge_length, weight, truck_weights): bridge = deque([ 0 for _ in range(bridge_length)]) trucks = deque([ truck for truck in truck_weights]) answer = 0 total = 0 while trucks: cur_truck ..

링크: https://school.programmers.co.kr/learn/courses/30/lessons/42587✅ 순서가 첫번째부터임 리스트 0번으로 return하면 당연히 틀림 ✅ 최대 힙임 (최소힙으로 습관적으로 쓰지 말것)✅ 가장 우선 순위가 높은 프로세스를 찾을 때 max() 나 any()를 쓰는 거 보단 힙을 사용하는게 더 빠름  최신 풀이: 큐+힙 사용(더 빠름)이전 풀이: 큐+any사용시간 ✅ 최신 풀이: 큐+힙 사용from collections import dequefrom heapq import heappush,heappopdef solution(priorities, location): q = deque() hq = [] for i,p in enumerate(pr..

✅ 스택 사용from math import ceildef solution(progresses, speeds): stack = [] answer = [] cnt = 0 for p,s in zip(progresses,speeds): cost = ceil((100-p)/s) if stack: if stack[-1]>=cost: answer[cnt]+=1 else: stack.pop() cnt+=1 answer.append(1) stack.append(cost) else: ..

✅ 해시 풀이- dict.fromkeys([arr],value)- 하나씩 더해가면서 자기자신아니면서 dict에 있는지 비교def solution(phone_book): d = dict.fromkeys(phone_book,1) for num in phone_book: temp = "" for n in num: temp+=n if temp in d and temp!=num: return False return True ✅ 정렬 풀이 - 일단 정렬- 파이썬 문자열의 y.startswith(x)사용하여 판단 (+endswith()도 있음)def solution(phone_book): phone_boo..