문제(영어)문제(번역)정수 n이 주어질때, n!에서 오른쪽 끝에 있는 0의 개수를 구해라.n! = n * (n-1) * ... * 2 * 1 인 것을 기억해라. 접근 방법 팩토리얼 결과의 맨 뒤에 0은 언제언제 붙을까? 0은 10이 곱해질때마다 생길 것이다. 그럼 10은 2와 5의 곱으로 생긴다.우리는 여기에서 5에 집중을 해야 한다.2는 생각보다 자주 나오지만, 5는 자주 나오지 않는다.즉 뒤에 붙는 0의 수는 5가 나오는 수와 동일하다고 간주하면 된다!그럼 답이 정말로 간단해진다. 소스코드int trailingZeroes(int n) { int c = 0; while(n > 0) { c += ( n/=5 ); } return c;} 공간복잡도도 O(1)이고, 해당 ..

문제(영어) 문제(번역)너는 계단을 오르고 있다. 꼭대기에 다다르려면 n 걸음이 걸린다.한번에 1칸 또는 2칸 오를 수 있다. 정상에 다다르려면 몇가지 구별되는 방법이 있나요? 접근 방법문제를 보자마자 DP가 생각났다.정상이 1인 경우, 갈 수 있는 경우의 수는 1칸만 이동하는 1개 밖에 없다.정상이 2인 경우, 1칸 이동하고 1칸을 이동하거나 바로 2칸을 이동하는 경우가 존재한다.정상이 3인 경우, 1번째 칸에서 올라오거나 2번째 칸에서 올라올 수 밖에 없다. 즉, 정상 t에 오르기 위해서는 t-1에 오는 방법의 수와 t-2에 오는 방법의 수를 더하면 된다! 코드int climbStairs(int n) { int array[46] = {0}; array[0] = 0; array[1] =..

문제(영어)문제 번역못생긴 숫자는 2,3,5 외에는 소인수가 없는 양의 정수이다. 정수 n이 주어졌을때 만약 못생긴 숫자면 true를 반환해라. 접근 방법먼저 제약 조건을 보니 n은 4 byte integer 범위의 수인 것을 알 수 있다.못생긴 숫자는 양수만 다루니 1보다 작은 모든 수는 false인 것을 알 수 있다. 그 다음 소인수 분해를 해야하는데, 2,3,5 숫자 3개로만 소인수 분해를 하면 된다.만약 소인수 분해를 했는데 이 이외의 수를 소인수로 갖고 있다면 false를 반환 하고 아니면 true를 반환하면 된다. 먼저 입력받은 수 n을 2로 나눈 나머지가 0인동안(즉, 2로 나눠지는 동안) 2로 계속해서 나눈다.그 다음 3으로 나눈 나머지가 0인동안(즉, 3으로 나눠지는 동안) 3으로 계속..