TEAM EDA

회의실 준비 (Big) 엘리스씨는 보다 더 나은 서비스를 제공하기 위하여 정기적인 회의를 하는 것을 선호하는 편이다. 여기서 엘리스씨의 역할은 n개의 회의가 언제 시작하는지, 그리고 언제 끝나는지를 모두 모으고, 그 이후 각 회의가 어느 장소에서 이루어져야 하는지를 정한다. 각 회의가 시작하는 시간, 그리고 끝나는 시간은 초단위로 주어진다고 하자. 예를 들어, 하나의 회의는 10초에 시작하여 99초에 끝날 수 있다. 당연하게도, 두 개의 회의가 시간이 겹칠 경우에는 같은 회의실을 사용할 수 없다. 또한, 만약 정확히 10초에 끝나는 회의가 있고, 또 다른 회의가 정확히 10초에 시작한다면, 이 두 회의는 같은 회의실을 사용할 수 있다. 회의실을 빌리는 데에는 돈이 들기 때문에, 엘리스씨는 가능한한 적은 ..

가장 가까운 두 점 찾기 (Big) 2차원 평면에 n개의 점이 있다. 이 점들 중에서 그 거리가 가장 가까운 두 점 사이의 거리의 제곱을 출력하는 프로그램을 작성하시오. 단, 두 점 (x1, y1)과 (x2, y2) 사이의 거리는 $\sqrt{(x1-x2)^2 + (y1-y2)^2}$ 로 정의된다. 예를 들어, 4개의 점이 각각 (0, 3), (1, 1), (2, 2), (7, 1) 에 위치해 있다고 하면, 가장 가까운 두 점은 (1, 1)과 (2, 2)이며, 그 거리의 제곱은 2이다. 입력 첫째 줄에 점의 개수 nn이 주어진다. (2≤n≤100,000) 두 번째 줄부터 각 점의 x좌표, y좌표가 주어진다. 각 좌표는 정수이다. 출력 가장 가까운 두 점 사이의 거리의 제곱을 출력한다. 입력 예시 4 0 ..

Inversion counting n개의 숫자의 리스트 A가 주어질 때, inversion은 다음과 같이 정의된다. 만약 i A[j]라면 A[i]와 A[j]는 inversion 관계이다. 예를 들어, A = [1, 4, 3, 2] 일 경우, 총 3개의 inversion이 존재하는데, 이는 그 값들을 나열해보면 (4, 3), (4, 2), (3, 2) 이다. n개의 숫자가 주어질 때, inversion 관계인 숫자 쌍의 개수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 n개의 숫자가 주어진다. (1≤n≤100,000) 출력 Inversion의 개수를 출력한다. 입력 예시 1 4 3 2 출력 예시 3 풀이 분할정복법을 이용한 계산 합병정렬을 이용해가지고 합병정렬시에 순서가 바..

히스토그램 가로의 길이가 1, 세로의 길이가 각각 다른 nn개의 판자들이 주어진다. 이 판자들은 아래 그림과 같이 모두 붙어있다. 직사각형 모양의 판자가 필요해 진 엘리스씨는, 이 붙어있는 판자들을 적당히 잘라내어 넓이가 가장 큰 직사각형을 얻고싶어 한다. 예를 들어, 위의 그림에서 얻을 수 있는 최대 넓이의 직사각형은 아래 그림과 같다. n개 판자에 대한 정보가 주어질 때, 이를 적당히 잘라 얻을 수 있는 직사각형의 최대 넓이를 출력하는 프로그램을 작성하세요. 입력 첫째 줄에 n개의 판자의 높이가 차례대로 주어진다. (1≤n≤100,000) 첫 번째 숫자는 첫 번째 판자의 높이, 두 번째 숫자는 두 번째 판자의 높이, …, n번째 숫자는 n번째 판자의 높이를 나타낸다. 출력 주어진 판자를 적당히 잘라 ..

색종이 만들기 아래 과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 전체 종이의 크기가 N×N(N=2^k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다. 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑..

절댓값 순 정렬 문제 : n개의 숫자가 주어질 때, 이를 절댓값을 기준으로 오름차순 정렬하는 프로그램을 작성하세요. 만약 두 수의 절댓값이 같다면, 더 작은 숫자가 앞에 위치하게 됩니다. 이 실습 문제는 Quick sort로 구현해주세요. 입력 : 첫 번째 줄에 n개의 숫자가 주어집니다. 출력 : 절댓값을 기준으로 오름차순 정렬한 결과를 출력합니다. 입력 예시 -2 1 3 9 -5 6 7 -3 출력 예시 1 -2 -3 3 -5 6 7 9 풀이 Quick Sort 절댓값 순 정렬 기저조건 : array가 1개 이하이면 자기자신 출력 임의로 pivot 출력 (중앙에 있는 값) pivot이 크면 왼쪽(left), pivot이 작으면 오른쪽(right), pivot이랑 같은데 음수이면 왼쪽 양수이면 오른쪽(eq..