이진탐색 - Binary Search

정렬된 원소 리스트에서 시작한다. 리스트에 원하는 원소가 있으면 그 원소의 위치를 반환하고, 아니면 null 값을 반환한다. 매 번 남은 숫자 중의 가운데 숫자를 말하고, 대답에 따라 그 보다 큰 숫자 혹은 작은 숫자들을 한 번에 없앤다. n개의 원소를 가진 리스트에서 이진탐색을 이용하면 최대 $ log_2n$ 번 만에 대답을 찾을 수 있다. low = 0 high = len(list) -1 mid = (low + high) // 2 guess = list[mid] # 추측한 값이 작을 때 if guess item : high = mid - 1 알고리즘의 속도는 빅오 표기법에 의해서 O(연산횟수)로 표기할 수 있는데..

• format_list_bulleted 알고리즘과 자료구조/이론?
• · 2024. 1. 12.
• textsms

유클리드 호제법 - 최대공약수와 최소공배수

Python 에서 최대공약수와 최소공배수를 구할 수 있는 방법은 다양하게 존재한다. 그 중에서도 최소 시간을 이용할 수 있는 "유클리드 호제법" 에 대해 알아보고자 한다. 유클리드 호제법 (Euclidean Algorithm) 또는 유클리드 알고리즘이라고 불리는 이 방법은 2개의 자연수 또는 정수의 최대 공약수와 최소 공배수를 구할 수 있는 방법이다. 호제법 : 두 수가 서로 상대방 수를 나누어 원하는 수를 얻는 방법 예를 들어 a, b (단, a>b) 인 두 수가 존재할 때, a를 b로 나눈 나머지를 r 이라고 하면 a 와 b의 최대공약수는 b와 r의 최대공약수와 같다. 계속해서 나머지를 구해가면서 최종적으로 나머지로 나누어 떨어질때 까지 나누면 되는데 (최종적으로 나누어 떨어진 나머지가 최대공약수가 ..

• format_list_bulleted 알고리즘과 자료구조/이론?
• · 2024. 1. 11.
• textsms