5884번: 감시 카메라 n개의 점이 있는데 수직선이나 수평선으로 3개만 그어서 모든 점을 덮을 수 있는지 체크하는 문제 점의 좌표 범위가 10^9이다 보니 하나하나 다 그어보면 당연히 시간초과 날것이고 X좌표를 기준으로 그룹을 묶고, Y좌표를 기준으로 그룹을 묶는다 그러면 어떤 X = x좌표를 기준으로 수직선을 그어보면, 해당하는 y좌표들을 알 수 있다 그러면 그러한 y좌표가 여러개 있다면? Y = y로 수평선을 또 그어야할 것이다 근데 해당하는 Y = y2가 하나만 존재한다면 Y = y2로 수평선을 그을 필요가 없다 그러므로 모든 X = x에 대해 순회해봐서 x에 대응하는 y들을 다시 하나씩 순회해본 다음 해당하는 y좌표값들 개수가 2개 이상인 경우가 존재하면 그 쪽으로 수평선을 그어야하므로..
9015번: 정사각형 점이 n개 그냥 한다면 O(N^4)이겠지만 당연히 안될거고 O(N^3)인 방법도 있긴한데 N 정사각형 성질을 이용하면.. 임의의 두 점 A(x1,y1), B(x2,y2)을 먼저 잡고 벡터 AB를 구한다 벡터 AB = OB - OA = (x2-x1, y2-y1)으로 구할 수 있다 다음 벡터 AB를 시계방향으로 90도 회전하면 벡터 AD를 구할 수 있다 90도 회전하는 방법은? (x,y) >> (-y,x)로 되므로 벡터 AD = (-y2+y1, x2-x1)이 된다 https://deepdata.tistory.com/1388 벡터 (x,y)를 90도 회전하는 방법1. 회전 행렬 벡터 (x,y)는 극좌표계를 이용하면 $(rcos \theta , rsin \theta)$ 이 상황에..
2187번: 점 고르기 평면 위 n개의 점이 있는데, 세로로 A, 가로로 B인 직사각형을 쳐서 이 안에 있는 점의 크기의 최댓값과 최솟값의 차이가 가장 크게 직사각형을 만들고 싶다 보면 N 그러다보니 직사각형의 크기를 1부터 2*10^6까지 돌리고 직사각형 위치를 2*10^6*2*10^6... 해보면.. 당연히 시간초과 그런데 구하고자 하는 것이 직사각형 크기 이런건 아니고 아무 직사각형이나 쳐서 그 안에 점 크기의 최댓값 - 최솟값의 차이를 최대로 만드는거 어떤 점들이 들어오느냐 이게 중요 그래서 점 i를 기준으로 잡아서 점 j를 순회해서 크기가 A*B인 직사각형을 만들 수 있는지 고려해보고 가능하다면 두 점 i,j는 직사각형 내부에 있기 때문에 두 점 i,j의 크기를 최댓값, 최솟값으로 갱신해서..
7868번: 해밍 수열 3개의 소인수 p1,p2,p3이 주어질 때 p1,p2,p3만으로 소인수를 가지는 자연수의 오름차순 배열에서 i번째 수를 찾는 문제 H(2,3,5)는 2,3,4,5,6,8,9,10,12,... p1,p2,p3,i가 10^18보다 작다고 하니까 단순하게 다 돌려보는건 어려울것 같고 p1,p2,p3만을 소인수로 가지니까 H(p1,p2,p3)는 $p1^{n1} * p2^{n2} * p3^{n3}$ 여기서 출력하는 수가 10^18보다 작다고 하니까 결국 $p1^{n1} * p2^{n2} * p3^{n3}$도 10^18보다 작아야함 따라서 n1,n2,n3 따라서 p1,p2,p3가 주어질때 0~59 * 0~59 * 0~59로 3중 for문 돌아보면서 p1**n1 * p2 ** n2 * p..
5588번: 별자리 찾기 좌표 집합 A와 B가 주어질때 A를 얼마나 평행이동 시켜야 B의 부분집합이 될 수 있는가? 아래의 경우 2,-3 이동시키면 B의 빨간 부분과 일치시킬 수 있다 A의 별 개수 m이 최대 200개이고 B의 별 개수 n이 최대 1000개 x,y값은 최대 10^6까지... 그러면 200개 * 1000개 돌아보면서... 평행이동 시킬 수 있는 양 10^6까지 하나하나 돌아봐야하나?? 그런데 A의 모든 점은 서로 동일하게 (dx,dy)만큼 이동한다는 점 + B의 점들 집합의 일부가 되어야하므로, A의 한 점이 B의 모든 점 각각에 대하여 얼마만큼 이동해야 가능한지 (dx,dy)를 모두 구해놓는다면? 가능한 (dx,dy) 후보는 최대 1000개이고 각각에 대해서 A의 모든 점에..
3129번: 상범이의 은밀한 메세지 암호화된 메시지랑 원본 메시지의 일부가 주어질떄, 원본 메시지를 찾는 문제 각 메시지에서 알파벳을 0~25로 치환하고 원래 메시지 + 키 = 암호화된 메시지 이기 때문에 암호화된 메시지 - 원래 메시지 = 키임을 알 수 있다. 여기서 원래 메시지의 일부분만 보여지기 때문에 암호화된 메시지랑 원래 메시지를 비교해서 가능한 모든 키를 구해야한다. 예를 들어 암호화된 psinottfn과 원래 메시지 most가 주어지는데 원래 메시지 most는 어디 부분인지 모르니까 0번부터 5번까지 most를 비교해보면서 키를 찾는다 psinottfnmost psinottfn most ... for i in range(len(a)-len(b)+1): K = [] for..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
