sezeme

1.Top-down 과 Bottom-upDP를 푸는 방식에는 두 가지가 있다.Top-Down : 큰 부분부터 작은 부분으로 쪼개지며 답을 찾는다(재귀 사용)Bottom-up : 작은 부분부터 큰 부분까지 모두 답을 찾는다. 즉  큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용한다. 2. Top-down 장점모든 부분을 다 구하지 않아도 될 때 시간복잡도 면에서 유리하다. Bottom-up 방식은 문제 해결에 필요하지 않은 부분까지 모두 구하기 때문에 메모리나 시간상 불리하다.그 예시로 백준 무한 수열이 있다. 3. Bottom-up 장점모든 부분을 다 구해야 할 때는 Bottom-up이 유리하다. Top-down은 재귀함수를 구현하기 때문에 stack이 쌓여 불필요한 메모리가 낭비될 수 있다.그..

1. 유클리드 호제법의 정의✅ a>b인 두 양의 정수 a,b에 대하여, a=qb+r(나머지 r은 0 이상 b 미만,q는 몫)이라 하면, gcd(a,b)=gcd(b,r) (a,b의 최대공약수=b,r의 최대공약수)이다.2. 알고리즘 표현 public int GCD(int num1, int num2) { if (num1 % num2 == 0) return num2; return GCD(num2, num1 % num2); } 3. 증명a > b인 두 양의 정수 a, b가 있다. 이 둘의 최대공약수를 G라고 하자.a = AG, b = BG 여기서 A와 B는 서로소이다. G가 두 수의 최대공약수이기 때문이다.( 최대공약수는 모든 공통 약수를 가져가야 하기 때문..