hail2y.log

책 [Do it! 알고리즘 코딩 테스트 - 자바 편;김종관 지음]을 참고하여 작성하였습니다.  이 글은 증명보다는 방정식의 해를 구할 때 어떻게 접근해야 하는지 설명한다.유클리드 호제법이 두 수의 최대공약수를 구하기 위한 것이라고 보면, 확장 유클리드 호제법은 방정식의 해를 구하는 것이라고 볼 수 있다. 이름에서 알 수 있듯이 확장 유클리드 호제법은 기본 호제법을 알고 있어야 진행된다ax + by = c주어진 a, b, c, x, y는 모두 정수라고 생각한다. 이때 x, y의 해는 c % gcd(a,b) = 0 조건이 성립되어야 정수해를 구할 수 있다. 그렇기 때문에 문제에 접근할 때 먼저 c의 값이 gcd(a,b)의 배수가 맞는지 확인부터 해야 한다. 배수가 맞다면 일차 조건은 만족한 것이다. c가 g..

모듈러 연산을 활용해 분배 법칙을 하면 우리가 흔히 분배 법칙으로 기대하는 결과와는 차이가 있다. (A + B) % C = (A % C + B % C) % C(A - B) % C = (A % C - B % C + C) % C (A * B) % C = ((A % C) * (B % C)) % C(A / B) % C = (A * B^(-1)) % C = ((A % C) * (B^(-1) % C)) % C뺄셈의 경우 추가적으로 +C를 해주었는데 이러면 나머지 결과가 0 이상임을 보장할 수 있다. 코딩할 때 사실 결과로서 위 법칙만을 기억해도 괜찮을 것 같아서 증명 과정이 필요할까 싶지만... 과정을 알면 나중에 더 쉽게 기억할 수 있을 것 같아 첨부한다. 증명은 더하기만 확인해 보기로 한다. 어려워 보일 수 있..

책 [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..