본문 바로가기

알고리즘

SCPC 2019 본선 5번 풀이. 정육면체 재구성 문제 설명(요약) 3차원 공간에 \(N\)개의 점 \(P_1(x_1,y_1,z_1)\), \(\cdots\), \(P_N(x_N,y_N,z_N)\)이 주어져 있다. (정수좌표) 다음 조건을 만족하는 두 정육면체 \(Q\), \(Q'\)을 생각하자. \(Q\)와 \(Q'\)의 중심은 서로 일치한다. 주어진 \(N\)개의 점은 \(Q\)의 내부 또는 경계에 있으며, 동시에 \(Q'\)의 외부 또는 경계에 있다. 즉, \(Q\)는 바깥쪽 정육면체이고 \(Q'\)은 안쪽 정육면체이다. \(Q\)와 \(Q'\)의 한 변 길이의 차이의 최솟값을 구하시오. 제약 조건: \(N \le 15,000\), \(-10^9 \le x_i, y_i, z_i \le 10^9\) 실행 조건: 테스트 케이스 50개에 대한 실행시간 .. 더보기
SCPC 2018 본선 2번 풀이. 외계메시지 문제 설명(요약)N개의 정수가 순서대로 주어진다. 이 수열에서 X번 이상 반복되는 패턴 중 가장 긴 패턴의 길이를 구하여라. 단, 패턴은 부분적으로 서로 겹칠 수 있다.제약 조건: N 더보기
SCPC 2017 본선 4번 풀이. 방 바꾸기 문제 설명www.codeground.org 참조 풀이, Part 1 (부분문제 2)원래 그래프를 G라고 하자. G에서 임의의 간선은 최대 하나의 사이클에만 속하므로, 사이클을 이루는 정점들을 하나로 묶은 그래프 T를 생각하자. 사이클을 이루지 않는 정점은 그대로 홀로 둔다. T는 트리가 된다. 왜냐면, T의 정점들이 사이클을 이룬다면 애초에 하나로 묶였을 것이기 때문이다. * 원래 그래프의 정점과 구분하기 위해 T의 정점과 간선은 슈퍼정점과 슈퍼간선으로 표현할 것이다.* INF = 무한대 (Infinity)의 약자로 쓸 것이다. T의 슈퍼정점들 중, 빈 방의 처음 위치를 포함하는 슈퍼정점이 딱 하나 있을 것이다. 이 슈퍼정점을 트리 T의 루트 R(T)로 하자. 빈 방은 R(T)의 자식슈퍼정점 중 일부를 .. 더보기
SCPC 2017 본선 3번 풀이. Colony 문제 설명www.codeground.org 참조 부분문제 1 풀이만약 어떤 연도 Y에 캡슐이 도달 가능하다면, 캡슐은 Galaxy1이 어떤 연도 i에 건설한 Colony1[i]에서 출발하여 Galaxy2이 어떤 연도 j에 건설한 Colony2[j]에 도달했을 것이다. Colony1[i]에서 출발한 캡슐이 방문 가능한 지점은 택시거리가 Y-i 이하인 모든 지점이다. 따라서 Colony1[i]와 Colony2[j]의 택시거리가 Y-i 이하인지 확인하면 된다. 전체 시간복잡도는 O(N3)으로 N 더보기
SCPC 2017 본선 2번 풀이. Bridge 문제 설명(요약)평면 위에 볼록다각형 모양의 두 섬 A와 B가 있다. A와 B는 서로 교차하지 않는다. A와 B 사이에 다리를 놓으려고 하는데, 다리 건설 비용을 최소화하기 위해 다리의 길이를 최소화하려고 한다.다리의 A쪽 끝점 P와 B쪽 끝점 Q에 대해, P는 A의 내부나 경계에, Q는 B나 내부의 경계에 위치해야 한다.다리(선분 PQ)의 길이를 최소화하는 점 P와 Q에 대해, 그 길이를 구하여라.제약 조건: A, B의 꼭짓점 수 N, M은 각각 200,000 이하* 부분문제 1 (82점): N, M 더보기
SCPC 2016 본선 4번 풀이. 반물질 문제 설명www.codeground.org 참조 제약 조건: 1 더보기
SCPC 2016 본선 3번 풀이. 폭격 문제 설명2차원 격자칸 형태의 적국에 폭격을 하려고 한다.격자칸의 가로 크기는 N, 세로 크기는 M 이다.좌표는 가장 왼쪽 위 칸을 (1 , 1)로, 가장 오른쪽 아래 칸을 (M,N)으로 표현한다.각 격자칸에 최대 하나의 목표물이 있으며, 전체 목표물의 개수는 P 로 주어진다.각 폭격기는 3X3크기의 영역에 있는 목표물을 모두 파괴할 수 있으며, 그 영역에 두 개 이상의 목표물이 있어야 출격이 가능하다고 한다.적국의 목표물 위치가 주어졌을 때 모든 목표물을 파괴할 수 있는 최소의 폭격기 수를 계산하라.두 개 이상의 폭격기가 하나의 목표를 파괴하는 것도 가능하다.아래 그림에서 왼쪽의 경우는 어떤 경우에도 한 폭격기는 하나의 목표만 파괴할 수 있어서 폭격이 불가능하다.오른쪽의 경우는 두 대의 폭격기가 출동하.. 더보기
SCPC 2016 2차예선 5번 풀이. 난민촌 문제 설명(요약)평면 위에 N개의 점 (xi, yi)가 있고, N개의 자연수 ai가 주어져 있다. 가상의 평균점 C(xc, yc)와 ai들의 순열 ap(1), ..., ap(N)을 잘 정해 다음 식을 최소화하면 그 최솟값은 얼마인가? 제약 조건: N 더보기

티스토리툴바