NEMOSTAR5

재귀적으로 푼다는 것은, 문제를 쪼개서 더욱 더 작은 문제로 푸는 것이라고 생각한다. 재귀 = 반복문, 이런식으로 접근하는 것이 가능하다. 하지만 재귀에는 치명적인 문제가 있는데, 함수를 재귀적으로 너무 많이 호출하게 되면 call stack이 너무 많이 쌓이게 되어 stackOverflow 에러가 발생하게 된다. 재귀 함수에는 기본적으로 recursive case 와 base case가 있다. Recursive case : 현 문제가 너무 커서, 같은 형태의 더 작은 부분 문제를 재귀적으로 푸는 경우 Base case : 이미 문제가 충분히 작아서, 더 작은 부분 문제로 나누지 않고 답을 알 수 있는 경우 재귀적으로 다가가 본 피보나치 수열 def fib(n): # base case if n < 3: ..

저번 시간복잡도에 이어 이번에는 공간 복잡도에 대해 소개드리려고 합니다. 공간복잡도란? 공간 복잡도(Space Complexity)는 인풋 크기에 비례해서 알고리즘이 사용하는 메모리 공간을 나타냅니다. 공간복잡도는 예제를 통해 보겠습니다. O(1) def product(a, b, c): result = a * b * c return result 파라미터 a, b, c가 차지하는 공간을 제외하면, result 라는 변수에는 a * b * c 라는 값은 인풋값과 무관하기 때문에 공간복잡도는 O(1)이라고 볼 수 있습니다. O(n) def get_every_other(my_list): every_other = my_list[::2] return every_other 인풋 my_list 의 길이가 n이라고 생각..

codeit 강의를 통해 배운, 알고리즘 성능에 대한 분석법을 소개하겠습니다. 알고리즘 성능 분석에는 1. 시간 복잡도 - Time complexity 2. 공간 복잡도 - Space complexity 지금 할 것은 시간 복잡도(Time complexity)란? 기본적으로, Big-O Notation 이라는 표기법을 사용합니다. Big-O 시간 복잡도에 가장 큰 영향을 미치는 차항으로 시간복잡도를 나타내는 것을 Big-O 표기법 (Big-O Notation) 시간 복잡도의 표현 법 중 가장 많이 쓰이는 표현 법으로 알고리즘 실행 시간의 상한을 나타낸 표기법입니다. (최악의 효율) T(n)=n^2+2n+9 # O(n^2) T(n)=n^4+n^3+n^2+1 # O(n^4) T(n)=5n^3+3n^2+2n+..