개발일지

www.acmicpc.net/problem/3830 3830번: 교수님은 기다리지 않는다 교수님의 질문 (? a b)이 입력으로 들어올 때 마다, 지금까지 측정한 결과를 바탕으로 a와 b의 무게 차이를 계산할 수 있다면, b가 a보다 얼마나 무거운지를 출력한다. 무게의 차이의 절댓값이 1,000, www.acmicpc.net 접근 처음에 Disjoint-Set과 LCA를 고민했다. Disjoint-Set을 고민한 이유는 간선을 추가할(샘플을 측정) 때 Disjoint-Set의 Union연산을 통해 하나의 Set으로 만들고, Find연산으로 쉽게 UNKNOWN인지 알 수 있기 때문이다. LCA를 고민한 이유는 무게차이를 구할 때 공통 조상 노드를 찾아서 거리를 구하면 logN만에 쉽게 거리를 찾을 수 있기..

개념 서로 같은 집합에 속해있는지 확인하고 같은 집합으로 합치거나 집합의 포함된 원소의 수를 알아내는 알고리즘이다. union => 두 원소 a, b가 있을 때 a가 속한 집합과 b가 속한 집합을 합치는 연산 find => 원소 a가 있을 때 a가 속한 집합을 찾는 연산 작동원리 초기화 1. 배열을 -1로 초기화한다. (음수의 절대값이 해당 집합에 속안 원소의 갯수가 된다.) find 1. 재귀호출을 통해 배열에 저장된 값이 음수일 때 까지 찾는다 (배열에 저장된 값이 양수면 해당 원소의 부모 원소이고, 음수면 해당 집합의 최고 위치에 있는 인덱스이다.) 2. 배열에 저장된 값이 음수이면 해당 인덱스를 반환한다. union 1. 두 원소의 속한 집합을 find연산으로 찾는다. 2. 두 원소가 속한 집합이..