알고리즘 스터디 정리(복습용)2 [Python] 에라토스테네스의 체 (소수 구하기) 에라토스테네스의 체 (Sieve of Eratosthenes)📌 개요에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 고안한 소수를 빠르고 효율적으로 찾는 알고리즘입니다!특정 범위 내의 모든 소수를 한 번에 구할 수 있어 수학 및 알고리즘 문제 해결에서 널리 사용됩니다.🎯 원리에라토스테네스의 체는 다음과 같은 절차로 동작합니다:1️⃣ 초기화 → 2부터 원하는 범위까지 모든 정수를 나열2️⃣ 첫 소수 선택 → 가장 작은 소수 2부터 시작3️⃣ 배수 제거 → 2의 배수를 제거 (자기 자신 제외)4️⃣ 다음 소수 선택 → 남아있는 수 중 다음 소수 선택 & 배수 제거5️⃣ 반복 → 위 과정을 모든 수에 대해 반복!💡 이 과정을 거치면 남아있는 수들이 소수!🔎 예시예를 들어, 1부터 25까지의 소.. 2025. 3. 7. [Python] 세그먼트 트리 segment tree [세그먼트 트리] 세그먼트 트리 알고리즘 정리📌 세그먼트 트리란?세그먼트 트리는 배열의 구간 정보를 저장하여 구간 쿼리와 업데이트를 효율적으로 처리하는 자료구조입니다. 주로 구간 합, 최소값, 최대값 등을 O(log n) 시간 안에 계산할 수 있도록 도와줍니다.🚨 세그먼트 트리의 구조완전 이진 트리: 배열을 기반으로 한 완전 이진 트리 구조로 구현됩니다.노드 역할:리프 노드: 배열의 개별 원소를 저장합니다.내부 노드: 자식 노드의 값을 이용해 해당 구간의 정보를(예, 최소값 또는 합) 계산해 저장합니다.💡 주요 연산구간 쿼리: 특정 구간(예, [L, R])의 합 또는 최소/최대값을 O(log n) 시간 내에 계산할 수 있습니다.업데이트: 배열의 한 원소가 변경되었을 때, O(log n) 시간 안에 .. 2025. 3. 6. 이전 1 다음