문제는 너무 쉬웠다. 바로 풀었는데 (내가 알고리즘 천재인줄 앎)
Given a non-negative integer num, return the number of steps to reduce it to zero. If the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it.
갑자기 Recursive 의 Big O 가 궁금하다는 생각이 들었다.(갑자기)
검색하다 보니 stack overflow 에 좋은 글을 찾았다.
int recursiveFun1(int n) {
if (n <= 0)
return 1;
else
return 1 + recursiveFun1(n-1);
}
Java
복사
이건 base case ( n ≤ 0n≤0 ) 까지 도착하는데 n 번 recursive 된다.
int recursiveFun2(int n) {
if (n <= 0)
return 1;
else
return 1 + recursiveFun2(n-5);
}
Java
복사
base case 에 오는데 n−5 번 걸리지만 결국 같은 O(n) 이 된다.
int recursiveFun3(int n) {
if (n <= 0)
return 1;
else
return 1 + recursiveFun3(n/5);
}
Java
복사
이 함수는 log(n)log(n) 이 된다. 왜냐하면 매번 함수를 호출 하기 전에 divide by 5 가 되기 때문이다.
그런데 매번 5씩 나누는거랑 log 랑 무슨 상관이 있는거지..?
T(n) = a *log_5(n) + T(0) = a* log5(n) + b = O(log n)T(n)=a∗log5(n)+T(0)=a∗log5(n)+b=O(logn)
일단 수식이 이러하다고 함. (a, b 는 상수)
1.
n = 0 이면 1번 호출
2.
1 ≤ n < 5 이면 2번 호출
3.
5 ≤ n < 25 이면 3번 호출
4.
25 ≤ n <125 이면 4번 호출
이러한 이유로 밑이 5인 log 가 완성된다.
최대 1 + log_5n1+log5n
void recursiveFun4(int n, int m, int o) {
if (n <= 0) {
printf("%d, %d\n",m, o);
} else {
recursiveFun4(n-1, m+1, o);
recursiveFun4(n-1, m, o+1);
}
}
Java
복사
이건 이거나 exponential 이라고 한다. 왜냐하면 함수가 recursive n을 각각 두번 호출하기 때문이다. 사실 이게 이 될 거라고 생각 못했다. 그리고 대부분의 recursive 가 다 이런 높은 OO 를 가지고 있는줄 알았어서 최대한 recursive 를 피하는 방향으로만 생각했다.
int recursiveFun5(int n) {
for (i = 0; i < n; i += 2) {
// do something
}
if (n <= 0)
return 1;
else
return 1 + recursiveFun5(n-5);
}
Java
복사
첫 번째 for 문 에서 n/2n/2 호출이 된다, for 문이 2 씩 증가 한다.
그리고 n-5 번 호출하는 recursive 가 있다.
따라서 수식은 (n / 2) *(n -5) = (2n -10)* n = 2n^2 - 10n(n/2)∗(n−5)=(2n−10)∗n=2n2−10n
즉 O(n^2)O(n2) 가 된다.
recursive 라고 무조건 피하는 게 아니라 잘 따져볼 필요가 있다.
이제 문제를 보면
class Solution {
public int numberOfSteps (int num) {
int result = 0;
while(num > 0) {
if (num % 2 == 0) {
num /= 2;
} else {
num -= 1;
}
result ++;
}
return result;
}
}
Java
복사
최초에 내가 푼 풀이다. 사실 DP 로도 접근을 해봤다. 왠지 DP로 하면 잘 맞아떨어질거 같다는 생각이 들었기 때문이다.
•
9: 8의 결과 +1; (9, 8, 4, 2, 1)
•
10: 10, 5, 4, 2, 1, 0
•
11: 10의 결과 + 1; (11, 10, 5, 4, 2, 1, 0)
•
12: 6의 결과 + 1;
•
13: 12의 결과 + 1; (13, 12, 6, 3, 2, 1, 0)
•
14: 7의 결과 + 1; (14, 7, 6, 3, 2, 1, 0)
그런데 DP 로 한다면 캐싱이 필수이기 때문에 공간을 두어서 오히려 속도가 엄청 느려진다
DP로 푼것 하나만 343ms 로 나온다
class Solution {
public int numberOfSteps (int num) {
if (num <= 1) return 1;
if (num % 2 == 0) {
return 1 + numberOfSteps(num/2);
} else {
return 1 + numberOfSteps(num-1);
}
}
}
Java
복사
이 풀이는 recursive 로 푼 경우인데
worst case 가 n-1, n/2 가 번갈아 나오는 경우이다.
그렇다면 무조건 -1 이 되는 n 보다 빠르고, log_2log2 보다는 느리게 된다.
즉, Big O notation 로는 log_nlogn 이라 볼 수 있다.(while 을 사용한 경우도 맞찬가지)
알고리즘으로 고생하고 계신분들이 있다면, 많은 도움 되시길 :)
