✅ 시간 복잡도 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다. 알고리즘의 시간복잡도는 주로 Big-O notation을 사용하여 나타내며, 이 Big-O notation은 계수와 낮은 차수의 항을 제외시키는 방법이다. 이런 방식으로 표현할 때, 시간복잡도를 점근적으로 묘사한다고 말한다. ✅ Big-O notation ➰ O(1) O(1)는 constant complexity라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다. 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있다는 의미이다. 코드 예시는 다음과 같다. def print_first(arr): print(arr[0]) ➰ O(n) O(n)은 linear complexity라고 부르며, 입력..
✅ 선형 탐색(Linear Search) 리스트의 맨 처음 원소부터 차례대로 하나씩 검사하여 그 값이 원하는 원소인지 확인하는 알고리즘이다. 원하는 원소를 찾으면 해당 인덱스를 리턴하고 끝까지 검사했는데도 못 찾으면 -1을 리턴한다. def seqsearch(nbrs, tgt): for i in range(0, len(nbrs)): if (tgt == nbrs[i]): return i return -1 알고리즘을 실행하는데 걸리는 시간은 원소 수에 비례하고 최악의 경우는 찾는 원소가 없는 경우이다. 보통 시간 복잡도를 O(n)으로 표시한다. ✅ 이진탐색(Binary Search) 탐색 범위의 중간 위치의 값을 원하는 원소 값과 비교한다. 중간 위치의 값이 원하는 원소 값보다 더 작으면 중간 위치 오른쪽..
✅ 재귀 알고리즘(Recursive Algorithm) 한 알고리즘의 내부에서 자기 자신을 다시 부르는 알고리즘을 의미한다. 반복 패턴과 종료 조건이 존재한다. 스택으로부터 메모리 할당 및 해제를 반복하는 반복 함수 호출로 속도는 느리다. ➰ 1부터 n까지의 합 구하기 def RecursiveSum(n): return 1 if n == 1 else RecursiveSum(n - 1) + n print("Recursive Sum of 1 to", upper, "=", RecursiveSum(upper)) ➰ 배열의 숫자의 합 구하기 (Recursive Sum) data = input("Enter list of numbers: ") numbers = data.split() numbers = [int(i) f..
