hail2y.log

책 [Do it! 알고리즘 코딩 테스트 - 자바 편;김종관 지음]을 참고하여 작성하였습니다.  오일러 피 함수 P[N]코딩 테스트에 자주 나오지는 않으나 알고 있어야 보임1부터 N까지 범위에서 N과 서로소인 자연수의 개수원리는 에라토스테네스('배수를 제거한다'는 원리)와 비슷다른 점은 현재 배열의 값이 소수일 때, 그 배수를 제거하기 위해 배열의 끝까지 P[i] = P[i] - (P[i] / K) 연산을 수행한다는 것(K는 현재 선택된 수, i는 K의 배수)이 과정은 N에서 해당 소인수 K의 배수를 제거하고 남은 수의 개수를 반영한다실제 구현할 때는 N까지를 배열로 구현하지 않아도 되는데, 1부터 N까지의 서로소 개수를 result 변수로 생각하는 것이다. 그래서 처음에 N을 넣고 K를 2부터 시작해 N..

모판을 만들어서 푸는 문제가 많이 나온다.구간합을 미리 다 구해놓은 합 배열을 만든다. https://www.acmicpc.net/problem/1292  import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class BOJ1292_ans { public static void main(String[] args) throws IOException { int[] t = new int[1001]; // 0, 1, 2, 2, 3, 3, 3 ... int idx = 1; for (..

(유클리드) 호제법(Euclidean Algorithm)두 정수의 최대공약수(gcd; Greatest Common Divisor)를 쉽게 알아내는 방법gcd(0, A) = A모든 수는 0을 나눌 수 있다. 따라서, 0의 모든 약수는 임의의 정수 A를 포함한다. 따라서, 둘의 gcd는 A가 된다. gcd(a,b) = gcd(b, a%b) (단, a > b) -- b > a이면 값을 바꾼다  cf. 귀류법어떤 명제가 참임을 직접 증명하는 대신, 그 부정 명제가 참이라고 가정하여 그것의 불합리성을 증명함으로써 원래의 명제가 참인 것을 보여 주는 간접 증명법. [네이버사전]import java.io.BufferedReader;import java.io.IOException;import java.io.InputS..