Algorithm (4) 썸네일형 리스트형 Lagest Rectangle In Histogram [Java] 아래 문제를 풀때 사용한 알고리즘 이다. https://www.codetree.ai/ko/trails/complete/curated-cards/test-max-area-of-positive-rectangle/description 양수 직사각형의 최대 크기 설명 | 코드트리양수 직사각형의 최대 크기를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 해당 이차원 배열에서 양수로만 이루어진 직사각형을 찾아야 할때 각 행을 읽어오면서 누적된 양수를 기록해 준다.for i 0) height++ else height = 0 i = 0 일때 height = [1, 0, 1, 0, 1]i = 1 일때 height = [2, 1,.. Manhattan Distance 맨해튼 거리는 흔히 사용하는 유클리드 거리와 다르게 좌표축에 평행하게 이동하여 길이를 구한다.과 q=(q1,q2,…,qn)를 공간벡터라 할 때,d1(p,q)=‖p−q‖1=∑i=1n|pi−qi|이다. 코딩에서는 마름모형태를 구할때 사용한다.for(int x = 0; x 이차원 배열에서 (x, y)를 기준으로 k만큼 떨어져 있는 마름모를 구하는 코드이다. 각 값들의 범위를 잘 조정해 주면 배열의 크기보다 큰 마름모 까지 확인을 하며 결국 정사각형 형태를 볼 수도 있다. 에라토스테네스의 체 (Sieve of Eratosthenes) 많은수의 소수 판변을 할때 유용한 방법 가장 작은 소수를 찾기해당 수의 배수를 모두 지우기 boolean[] isNotPrime = new boolean[N + 1]; isNotPrime[0] = true; isNotPrime[1] = true; for(int i = 2; i * i 유클리드 호제법 두 양의 정수 a, b(a > b)에 대하여 a = bq+r (0 ≤ r a, b의 최대공약수는 b, r의 최대공약수와 같다. //최대공약수(Greatest Common Divisor)public static long gcd(long a, long b){ if (b==0) { return a; }else return gcd(b, a%b);}//최소공배수(Least Common Multiplepublic static long lcm(long a, long b){ return a*b / gcd(a, b);} 시간복잡도 O(N log M) 이전 1 다음