Computer Science/Algorithm11 [백준] 7578번 : 공장 (Python) 문제https://www.acmicpc.net/problem/7578문제 요약 A 열에 위치한 기계, B 열에 위치한 기계의 식별번호가 주어진다.각 기계는 유일한 식별번호를 가지며, A 열의 특정 식별번호를 가진 기계는 B 열에 반드시 존재한다. (짝을 이룬다)A열, B열의 기계들에 대해, 식별번호가 같은 기계끼리 모두 연결했을 때 발생하는 교차하는 선 쌍의 개수를 찾는 문제이다.(중요) 교차점 을 구하는 문제가 아니다! (선 N개가 한 점에서 교차하는 경우를 생각하지 않아도 된다.)문제에서 체크할 것들입력값의 특성 기계의 개수 $N$ : $1 \leq N \leq 500,000$→ $O(NlogN)$ 알고리즘으로 해결해야 하구나! ($O( N^{2} )$ 알고리즘으로는 불가)기계의 식별번호 $K$ .. 2026. 1. 17. [구름톤 챌린지] Day19 : 대체 경로 입력 및 출력 소스 코드 n, m, start, end = map(int, input().split()) graph = [[] for _ in range(n+1)] for _ in range(m): a, b = map(int, input().split()) graph[a].append(b) graph[b].append(a) for i in range(1, n+1): if i == start or i == end: print(-1) continue visited = [False for _ in range(n+1)] q = [start] visited[start] = True depth = 1 ended = False while len(q) != 0 and not ended: nextq = [] for no.. 2023. 9. 9. [구름톤 챌린지] Day16 : 연합 소스 코드 from collections import deque n, k = map(int, input().split()) #undirected graph graph = [[] for _ in range(n+1)] #is undirect connected? sc = [[False for _ in range(n+1)] for _ in range(n+1)] for _ in range(k): a, b = map(int, input().split()) if not sc[b][a]: sc[a][b] = True else: #undirected connected graph graph[a].append(b) graph[b].append(a) visited = [False for _ in range(n+1)] unio.. 2023. 9. 9. [구름톤 챌린지] Day15 : 과일 구매 입력 및 출력 소스 코드 n, k = map(int, input().split()) fruits = [list(map(int, input().split())) for _ in range(n)] onepiece = [] for num, cost in fruits: pc = cost // num onepiece.append([pc, num]) onepiece.sort(reverse = True) ans = 0 i = 0 while k > 0 and i = onepiece[i][1]: ans += onepiece[i][0] * onepiece[i][1] k -= onepiece[i][1] i += 1 else: ans += k * onepiece[i][0] onepie.. 2023. 9. 1. 이전 1 2 3 다음
