#02. 에라토스테네스의 체(Sieve of Eratosthenes)

소수 판정법 중 하나 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 2는 소수이므로 오른쪽에 2를 쓴다. 자기 자신을 제외한 2의 배수를 모두 지운다. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. 자기 자신을 제외한 3의 배수를 모두 지운다. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. 자기 자신을 제외한 5의 배수를 모두 지운다. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. 자기 자신을 제외한 7의 배수를 모두 지운다. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다. #include int number = 100000; int a[1000001]; void primeNumberSieve() { // 1. 배열을 생성하여 초기화한다. for (in..

• format_list_bulleted Computer Science/Algorithm
• · 2021. 2. 4.
• textsms

#01. 이분탐색(Binary Search), 이진탐색

오름차순으로 정렬된 리스트에서 특정 값의 위치를 찾는 알고리즘 (이미 정렬되어 있어야 함) 모든 값을 순회해야 하는 일반적인 탐색보다 더 빠르다 중앙값을 찾는 값과 비교 left, mid, right 값으로 탐색 -> mid = (left+right)/2 (중앙값) > (찾는값) 중앙값 기준으로 왼쪽(작은 부분) 탐색 left -> mid+1 (중앙값) mid-1 반복문을 이용하는 방법 #include int main(void) { int N; int result = 0; int A[10] = { 2, 3, 5, 7, 8, 9, 11, 14, 16}; scanf("%d", &N); int left = 0, right = 9; while..

• format_list_bulleted Computer Science/Algorithm
• · 2021. 2. 4.
• textsms