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..
12979번: 종이 접기 종이의 크기 W,H인 종이가 주어질때 종이를 적절히 접어서 넓이가 A가 되도록 만들고 싶다. 종이를 접더라도 직사각형이 되도록 접어야하고 접고 나서도 W,H는 항상 정수가 되어야한다. 여기서 W,H가 10^9까지인데 A가 10^5까지라는 점에 주목하자. W,H로 뭔가 해보는건 어려울것 같지만 적어도 A는 1~10^5까지 다 돌아볼만하다. X*Y = A가 될려면 당연히 X,Y는 A이하여야한다. 그래서 A를 기준으로 1~A까지 돌아서 그 값을 X라고 둔다면, Y는? A가 X로 나누어 떨어질때, Y = A//X가 된다. 이러한 X,Y를 찾았다면 주어진 W,H에서 찾은 X,Y로 몇번만에 이동할 수 있는지 체크하면 된다. W에서 X로 갈려면 가장 빠르게 갈려면 몇번만에 갈수 있을까? ..
28867번: Портальная пушка 최대 100000개의 원소를 가지는 배열 A,B에 대하여 $\sum_{i,j}^{}(i-j)|a_{i} - b_{j}|$를 구하는 문제 당연히 $O(N^{2})$은 안될거고 O(N)에는 풀어야하는데 $a_{i} >= b_{j}$이고 $a_{i} 따라서 $(i-j)|a_{i}-b_{j}| = i(a_{i}-b_{j})-j(a_{i}-b_{j})+i(b_{j}-a_{i})-j(b_{j}-a_{i})$ 그래서 ai>=bj인 경우 i(ai-bj)와 j(ai-bj), ai 여기서 핵심은 앞에 붙은 i,j인데 얘를 고정시킨다면 투포인터를 활용해서 O(N)에 계산할 수 있다. 예를 들어 i = 0인 경우 j = 0,1,2,...증가시켜서 ai >= bj인 경우의 j를 ..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
