목록[Study]/코딩테스트 연습 (23)
기록
int func(int n) { if (n == 1) return 1; else if (n % 2 == 1) return n + func(n - 1); else return func(n / 2) * 2 + (n*n) / 4; } 1 + 2 + ... + n -> (1 + 2 + ... n/2) + ((n/2 + 1) + (n/2 + 2) + ... + (n/2 + n/2)) -> (1 + 2 + n/2) * 2 + (n/2 * n/2) // n/2가 n/2개 있음으로 뒤로 뺀다 따라서 n이 짝수일 때 f(n) = f(n/2)*2 + (n*n)/4 n이 홀수일 땐 f(n) = n + f(n-1) n이 1이면 1을 반환
이전에 나온 높이가 다음 높이를 볼 수 있다면 적재시키고 count 증가시키는데, 여기서 n번 전에 나온 높이는 그 다음에 나온 높이보다 높음으로 그 다음 높이를 당연히 볼 수 있으니 누적하여 count+=S.size()-1 한다. 다음에 나올 높이를 이전 높이가 못본다면, 볼 수 있는 높이가 나올 때까지 pop한다. (count에 들어가지 않기 위해) 관련 개념 : Monotone Stack
재귀적 방식 def fibonacci(i): if i==0: return 0 elif i==1: return 1 else: return fibonacci(i-1)+fibonacci(i-2) for i in range(6): print(fibonacci(i)) DP fibo = [0 for i in range(100)] fibo[0] = 0 fibo[1] = 1 for i in range(0,10): if i==0: print('0') elif i==1: print('1') else: fibo[i] = fibo[i-1] + fibo[i-2] print(fibo[i])