아롱이의 PS하는 블로그

"파이썬으로 구현하는"시리즈 1분리 집합(Disjoint Set)오늘은 파이썬으로 구현하는 분리 집합의 표현 방법에 대해서 알아볼 것이다. 다른 말로 유니온-파인드 자료 구조(Union-Find Structure)라고도 하는 이 자료구조는, 집합의 묶음을 관리하는 구조이다. 여기에서 집합은 서로소 집합으로, 한 원소가 둘 이상의 집합에 속하는 경우가 없다. 아이디어는 다음과 같다. 집합 하나당 원소 하나가 대표값이 된다.그래서, 같은 집합에 속해있으면 같은 대표값을 가지게 되는 것이다! 예를 들어, 집합이 {3, 1, 4}, {5} {6, 7, 8, 9}인 경우 다음과 같이 나타낼 수 있을 것이다.  예를 들어서 나는 이 상태에서 {3, 1, 4}와 {6, 7, 8, 9} 집합을 합하고 싶다. 그러면 어..

https://www.acmicpc.net/problem/1419문제첫 항이 x이고 공차가 d인 등차수열의 첫 k개의 항은 x, x+d, x+2d, ..., x+(k-1)d이다. x와 d가 자연수인 등차수열의 첫 k개의 항의 합으로 나타낼 수 있는 수 중에서, l 이상이고 r 이하인 수가 몇 개인지 구하는 프로그램을 작성하시오.입력자연수 l, r, k가 순서대로 한 줄에 하나씩 주어진다. (1 ≤ l ≤ r ≤ 1,000,000,000, 2 ≤ k ≤ 5)출력첫째 줄에 조건을 만족하는 수의 개수를 출력한다.  풀이등차수열의 합 공식은 무엇인가?첫 항이 x이고 공차가 d라면, 등차수열의 k개의 합은  $$\frac{k(2x+(k-1)d)}{2}$$  로 나타낼 수 있다.여기서 $l$ 이상이고 $r$..

https://www.acmicpc.net/problem/3679 문제평면 위의 점의 집합이 주어졌을 때, 다각형을 만드는 프로그램을 작성하시오. 집합의 모든 점은 다각형의 꼭짓점이어야 하고, 집합에 없는 점을 다각형의 꼭짓점으로 가질 수 없다. 다각형의 두 선분은 연속하는 두 선분의 교점을 제외하고는 교차할 수 없다.예를 들어, 왼쪽 그림의 점으로 만든 다각형은 오른쪽과 같다.항상 문제의 조건을 만족하는 다각형만 입력으로 주어지며, 가능한 다각형이 여러 가지인 경우에는 아무거나 출력해도 된다. 두 점이 같은 위치에 있는 경우는 없으며, 모든 점이 한 직선위에 있는 경우는 없다.입력첫째 줄에 테스트 케이스의 개수 c (1 ≤ c ≤ 200)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 테스트..

https://www.acmicpc.net/problem/30645문제탁자 위에 인형을 전시하려고 한다. 탁자는 위에서 보았을 때 R개의 행과 C개의 열을 가진 R × C개의 칸을 가진 2차원 배열이며, 각 칸에 하나의 인형을 전시할 수 있다. 현재 전시할 수 있는 인형은 N개이며, 탁자 위에 N개의 인형을 모두 전시할 필요는 없다.탁자를 정면으로 보면 1행에 놓은 인형들이 맨 앞쪽에 있는 방향으로 보게 되는데, 같은 열에 있는 인형들에 대해 앞쪽 행에 인형을 놓은 경우 앞쪽 인형보다 뒤쪽 행에 있고 높이가 앞쪽 인형의 높이 이하인 인형은 앞쪽 인형에 가려져 보이지 않게 된다.이때, 탁자에 인형들을 적당히 배치했을 때 탁자의 정면 방향에서 보이는 인형의 개수의 최댓값을 구하는 프로그램을 작성하시오.입력첫..

https://www.acmicpc.net/problem/14247문제영선이는 나무꾼으로 나무를 구하러 오전에 산에 오른다. 산에는 n개의 나무가 있는데, 영선이는 하루에 한 나무씩 n$n$일 산에 오르며 나무를 잘라갈 것이다. 하지만 이 산은 영험한 기운이 있어 나무들이 밤만 되면 매우 빠른 속도로 자라는데, 그 자라는 길이는 나무마다 다르다.따라서, 어느 나무를 먼저 잘라가느냐에 따라서 총 구할 수 있는 나무의 양이 다른데,나무의 처음 길이와 하루에 자라는 양이 주어졌을 때, 영선이가 얻을 수 있는 최대 나무양을 구하시오.참고로, 자른 이후에도 나무는 0부터 다시 자라기 때문에 같은 나무를 여러 번 자를 수는 있다.입력첫째 줄에는 나무의 개수 n개가 있다. 나무는 1번부터 n번까지 있다.다음 줄에는 ..

https://www.acmicpc.net/problem/4008문제1부터 n까지 번호가 붙여진 n명의 병사들로 이루어진 군대의 지휘관이 있다. 이 지휘관은 앞으로의 전투를 위하여 n명의 병사들을 여러 개의 특공대로 나누고자 한다. 결속력과 사기를 높이기 위하여 각 특공대는 {i, i+1, ..., i+k}형태의 번호가 연속하는 병사들로 구성된다.각 병사 i의 전투력은 xi이다. 병사들 {i, i+1, ..., i+k}로 구성된 특공대의 전투력 x는 원래는 각 병사의 전투력의 합으로 계산되었다. 달리 말하면 x = xi + xi+1 + ... + xk이었다.그러나 여러 해의 영광스러운 승리를 통하여 특공대의 전투력을 다음과 같이 조정해야 하는 것으로 결론을 내렸다: 특공대의 조정된 전투력 x′는 등식 x..

https://www.acmicpc.net/problem/14751문제There are two distinct horizontal lines hupper and hlower in the xy-coordinate plane and n line segments connecting them. One endpoint of each segment lies on hupper and the other on hlower. All endpoints of the segments are distinct. All segments are numbered from 1 to n. Consider a horizontal line hi located between hupper and hlower, which will be given ..

https://www.acmicpc.net/problem/13263문제높이가 a1, a2, ..., an인 나무 n개를 전기톱을 이용해서 자르려고 한다.i번 나무에 전기톱을 사용할 때 마다 그 나무의 높이는 1만큼 감소한다. 전기톱은 사용할 때 마다 충전해야 한다. 전기톱을 충전하는 비용은 완전히 자른 나무의 번호에 영향을 받는다. 즉, 높이가 0이 되어버린 나무의 번호에 영향을 받는다. 완전히 잘려진 나무의 번호 중 최댓값이 i이면, 전기톱을 충전하는 비용은 bi이다. 완전히 잘려진 나무가 없다면 전기톱은 충전할 수가 없다. 가장 처음에 전기톱은 충전되어져 있다.나무의 높이 ai와 각각의 나무에 대한 충전 비용 bi가 주어졌을 때, 모든 나무를 완전히 자르는데 (높이를 0으로 만드는데) 필요한 충전 비..

https://www.acmicpc.net/problem/9892문제(직접 핵심만 번역해보겠음)2차원 평면 상에 점들이 여러개 주어진다. width w는 이 점들을 모두 감싸는 두 평행한 직선 사이의 최소 거리이다.예를 들면 다음 그림과 같다.당신은 주어진 점들에 대해서 w^2를 계산한 다음 이 수의 정수 부분만 출력하면 된다. 이 문제를 쉽게 풀게 하기 위해 공식을 하나 제공하겠다. 삼각형 ABC가 있어서 A(xa, ya), B(xb, yb), C(xc, yc)라고 할 때 이 삼각형의 높이 h는과 같이 계산될 수 있다. 여기서 문자 시그마의 값은 ABC가 반시계방향이면 1이고 시계방향이면 -1이다. Figure 2를 참고하라.모든 점들이 일직선에 놓여있다면, width는 0이 된다. 입력첫 번째 줄에는..

https://www.acmicpc.net/problem/10254문제n개의 도시를 가진 나라가 있다. 이 나라에서는 도시들 중 가장 먼 두 도시 사이에 직행 고속도로를 놓으려 한다.고속도로는 시작점과 끝점이 아닌 다른 나라를 통과해도 된다. 즉, n개의 도시 중 유클리드 거리가 가장 먼 두 도시를 찾으려 한다. 모든 도시는 한 평면 위에 있다.위의 예제에서는 (12,0)의 도시와 (-6,3)의 도시가 가장 먼 유클리드 거리를 갖는다.도시 n개의 좌표가 주어지면 모든 두 도시 쌍의 거리 중 가장 먼 두 도시를 찾아라.입력첫째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 줄엔 도시의 개수 n이 주어진다. (2 ≤ n ≤ 200,000) 그 후 n줄에 걸쳐 각 도시의 x좌표와 y좌표가 주..