지식을 나누는 공간

문제 https://www.acmicpc.net/problem/16202 16202번: MST 게임 첫 턴에 찾을 수 있는 MST는 총 5개의 간선 {(1, 3), (1, 2), (2, 4), (4, 6), (4, 5)}로 이루어져 있고, 비용은 16이다. 두 번째 턴에는 첫 턴에서 구한 MST에서 간선의 비용이 최소인 (2, 4)를 제거한 후 남아있 www.acmicpc.net 코드 n,m,k=map(int, input().split()) graph=[] parent=[] for i in range(n+1): parent.append(i) for i in range(1,m+1): a,b=map(int, input().split()) graph.append([a,b,i]) def find(x): if p..

문제 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 코드 import sys from collections import deque input=sys.stdin.readline t=int(input()) for _ in range(t): n,k=map(int, input().split()) graph=[[] for _ in range(n+1)] time=[0]+list(map(int, input().split())) indegree=[0]..

문제 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 코드 from collections import deque import sys input=sys.stdin.readline def bfs(start): visited=[-1]*(v+1) queue=deque() queue.append(start) visited[start]=0 max_a=[0,0] #dis, node while queue: t=queue.popleft() fo..

문제 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 코드 from sys import stdin input = stdin.readline def find(x): if parent[x] != x: parent[x] = find(parent[x]) return parent[x] def union(a, b): a = find(a) b = find(b) if a != b: parent[b] = a number[a] += number[b] ..

문제 https://programmers.co.kr/learn/courses/30/lessons/49190?language=python3 코딩테스트 연습 - 방의 개수 [6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0] 3 programmers.co.kr 코드 from collections import defaultdict def solution(arrows): dx=[-1,-1,0,1,1,1,0,-1] dy=[0,1,1,1,0,-1,-1,-1] array=defaultdict(list) answer=0 row,col=0,0 for i in arrows: for _ in range(2): nx=row+dx[i] ny=col+dy[i] if (nx, ny..

문제 https://programmers.co.kr/learn/courses/30/lessons/49191?language=python3 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 코드 def solution(n, results): answer = 0 array=[[None]*(n+1) for _ in range(n+1)] for i,j in results: array[i][j]=True array[j][i]=False for i in range(1,n+1): for j in range(1,n+1): for k in range(1,n+1): if array[j][i]==None: continue if array..

문제 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 코드 import sys from collections import deque input=sys.stdin.readline def sort(): queue=deque() for i in range(1,n+1): if parent[i]==0: queue.append(i) while queue: x=queue.popleft() result.append(..

문제 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 코드 import sys input=sys.stdin.readline def find(x): if parent[x]!=x: parent[x]=find(parent[x]) return parent[x] def union(a,b): a=find(a) b=find(b) if a

문제 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 코드 import sys sys.setrecursionlimit(1000000) input=sys.stdin.readline def find(x): if parent[x]!=x: parent[x]=find(parent[x]) return parent[x] def union(b,c): b=find(b) c=find(c) if b

서로소 집합 자료구조 _ Union-Find 서로소 집합이란 공통원소가 없는 두 집합을 의미한다. 서로소 부분집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 서로소 집합 자료구조(=합치기 찾기 자료구조)는 두종류의 연산을 지원한다. 합집합(Union) : 두개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 찾기(find) : 특정 원소가 속한 집합이 어떤 집합인지 알려주는 연산 - Union의 인자값으로 각 노드가 들어감 - 초기에는 각각이 하나의 집합으로 여겨지며 자기자신이 곧 부모가 된다. - 합치기 연산에서, 일반적으로 두 노드중 값이 더 큰 노드의 부모값을 더 작은노드의 부모로 갱신한다. 단, 여기서 부모노드는 루트노드가 아니라는것을 주의해야함 (3번과 4번은 부모노드는 다르지만 ..