개발블로그by페페

10 : Combination 01 - 조합 알아보기 076 : 이항계수 구하기 1 077 : 이항계수 구하기 2 078 : 부녀회장이 될 테야 079 : 다리 놓기 080 : 조약돌 꺼내기 081 : 순열의 순서 구하기 082 : 사전 찾기 083 : 선물 전달하기

09 : TREE 01 - 트리 알아보기 067 : 트리의 부모 찾기 DFS + DFS 시행시 부모 노드 저장 068 : 리프 노드의 갯수 구하기 02 - 트라이 069 : 문자열 찾기 03 - 이진 트리 070 : 트리 순회하기 04 - 세그먼트 트리 최하단 리프 (N/2 ~) 에 값을 입력시킨 뒤, 한 위상씩 올라가면서 최솟값, 합 등 계산 071 : 구간 합 구하기 3 072 : 최솟값 찾기 2 073 : 구간 곱 구하기 05 - 최소 공통 조상 074 : 최소 공통 조상 구하기 1 075 : 최소 공통 조상 구하기 2

08 : Graph 01 - 그래프의 표현 Edge list : A[2][N] Adjacency matrix : A[N][N] Adjacency List : ArrayList[N] 046 : 특정 거리의 도시 찾기 047 : 효율적으로 해킹하기 048 : 이분 그래프 판별하기 049 : 물의 양 구하기 02 - 유니온 파인드 union : (find값인) label이 다르다면, 하나의 label로 묶는 선언 find : label 출력, 똑같으면 value, 다르면 value = find(label(a)); checkSame : label이 같으면 true, 다르면 false 출력 050 : 집합 표현하기 051 : 여행 계획 짜기 052 : 거짓말쟁이가 되긴 싫어 03 - 위상 정렬 사이클이 없는 방향..

07 : Number Theory 01 - Prime 037 : 소수 구하기 - 에라스토테네스의 체 038 : 소수 구하기 2 - 에라스토테네스의 체 039 : 소수 & 팰린드롬 수 중 최솟값 - 에라스토테네스의 체 - 팰린드롬 040 : 제곱이 아닌 수 찾기 - 에라스토테네스의 체의 unit을 배수가 아닌 제곱으로 사용 02 - Euler Phi 041 : Euler phi 구현 - Euler phi 작동방식 외우기 03 - Euclidean Algorithm 042 : LCM - GCD*LCM = A*B 043 : GCD - GCD - 수의 길이를 나타내는 두 수의 최대 공약수는 두 수의 최대 공약수 - BufferedWriter 044 : Cocktail 04 - Extended Euclidean ..

s

2회 반복하면 나머지는 동일하다

// Operating GCD(1/2) long GCD = GCD(Math.max(A, B), Math.min(A, B)); // External Module(1/2) private static long GCD(long B, long S) { long r = B % S; while (r != 0) { r = B%S; B = S; S = r; } return Math.abs(B); }

절댓값 반환

Ax + By = C 방정식의 해를 구하는 것 - C % GCD(A, B) = 0인 경우에만 정수해를 가진다 (나누어 떨어질 때) - C의 최솟값은 1임을 적용하여 중간에서 MOD 연산 시작 예제 : 5x + 9y = 2 > 5x + 9y = 1 에서 시작 - 나머지가 0이 될때까지 연산 시행 MOD Remainder Quotient 5 % 9 = 5 5 0 9 % 5 = 4 4 1 5 % 4 = 1 1 1 4 % 1 = 0 0 4 - 최하단에서 역순으로 올라가며 x와 y 쌍 계산 x = 이전y y = 이전x - 이전y*Quotient * 최하단은 이전 값이 없으므로 이전값을 (1, 0)으로 지정 - 이렇게 재귀 형식으로 구해진 최종 (x, y)는 Ax + By = GCD(A, B)를 만족 - 또한 앞에..

- 두 수의 Greatest Common Divisor를 구하는 것 - MOD 연산 10 MOD 4 = 2 10 % 4 = 2 큰 수를 작은 수로 나누는 것 - 앞 단계의 작은 수와 remainder로 MOD 연산 재귀적으로 반복 - remainder == 0일 때 그 연산의 작은 수 = GCD