NEMOSTAR5

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

안녕하세요. 리스트를 k만큼 회전시키는 것에 대한 알고리즘은 무궁무진하게 많을 것라고 생각합니다. 저는 그냥 제가 학교에서 배운 내용에 대해 복습하고 생각해 볼 겸 게시글로 남겨봅니다. 전제 n만큼의 길이를 가진 리스트를 k칸만큼 회전시켜라. 방법 ① 0 < k < n일 경우 index_value의 자리를 index_value + k - n 이 식을 통해 해결 할 수 있습니다. def rotatelist(n: list, k: int): result = [None] * len(n) # 자리를 게산한 리스트를 넣을 빈리스트 생성 for i in range(len(n)): # n의 길이만큼 반복을 돌며 각 리스트의 값의 자리를 찾음 if i + k < len(n): # i + k가 n의 길이 보다 작을 경우를..

저번 시간복잡도에 이어 이번에는 공간 복잡도에 대해 소개드리려고 합니다. 공간복잡도란? 공간 복잡도(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+..