Waltwaez의 기록장 - 아카이브

1. 기본1. 2부터 구하고자 하는 수까지 모두 나열2. 2부터 숫자를 올리며 자신의 배수는 제거3. 과정 2를 반복하면 구간의 모든 소수가 남게 됨2번에서 올라가는 숫자는 구하고자 하는 수까지 가지 않아도 된다. 구하고자 하는 수의 제곱근까지만 가도 됨.2. 구현# 정수 n까지의 소수 리스트 얻기def sieve_of_eratosthenes(n): prime = [True] * (n + 1) prime[0] = False prime[1] = False for p in range(2, int(n**0.5) + 1): if prime[p]: for i in range(p * p, n + 1, p): prime[i] = Fals..

이진 탐색은 일반적으로 이렇게 짠다.def binary_search(arr, target): left = 0 right = len(arr) - 1 while left 1. 종료 조건- 종료 조건은 인덱스가 left > right일 때이다. (즉 반복 조건은left - left   2. 갱신 조건위처럼 left, right 를 갱신하는 게 일반적이지만.. 2.1. 중복 값중 가장 왼쪽/오른쪽 인덱스 찾기중복된 값 중 가장 왼쪽을 찾고 싶거나, 가장 오른쪽을 찾고 싶은 경우는 아래처럼 구현한다.공통적으로 left 가장 왼쪽 찾기 : right 갱신 조건에서 mid - 1 대신 mid  가장 오른족 찾기 : left 갱신 조건에서 mid + 1 대신 mid  가장 왼쪽 인덱스 값 찾기 w..