분류 전체보기 (5) 썸네일형 리스트형 [코드트리] 완전탐색 약점 극복 후기 코드트리의 청약통장 챌린지가 돌아왔다. 최근 대학생 부트캠프의 코딩테스트에서 떨어져서 코테에 대한 부담감과 걱정이 많이 있는 상태인데 이번 기회에 다시 기초부터 다잡아 볼까 한다. 청약통장의 첫 시작은 갭체크를 보는 것이다. 백준 골드였고 그래도 나름 기본을 알고있다고 생각했는데 갭체크에서 또 한번 미끄러진 것 같다. 알고리즘 문제를 풀 때 시간을 넉넉하게 잡고 푸는 편이었는데 10분만에 문제를 풀려고 하니 생각보다 많이 힘들었다. 5번 문제 같은 경우에는 문제 해석 자체를 잘 못해서 아예 풀지도 못했고 다이나믹 프로그래밍인 7번 문제는 10분을 다 써도 문제 해석을 못할 것 같아 건너뛰기를 눌러버렸다. (갭체크가 다 끝나면 문제 해설이 있을 줄 알고;;)갭체크 결과 내가 완전탐색의 개념이 없다는 판정.. 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 다음
