Computer Science/알고리즘과 자료구조2 시간 복잡도(Time Complexity)와 Big-O 표기법(Big-O Notation) 효율적인 알고리즘 알고리즘에서 문제를 푸는 것 만큼이나 중요한 문제는 공간과 시간의 활용을 어떻게 효율적으로 할 것인지에 대한 문제이다. 이에, 공간 복잡도와 시간 복잡도는 다양한 알고리즘의 평가 도구로 사용된다. 공간 복잡도: 얼마나 메모리를 적게 쓰는가? 시간 복잡도: 얼마나 빠른가(CPU에 얼마나 부담을 주는가)? 최신의 머신에서는 공간 복잡도에 대해 과거에 비해 고민이 많이 줄었으나(그러나 알고리즘 평가시 보조적인 역할을 한다), 시간 복잡도는 문제를 효율적으로 해결하기 위해 필수적으로 고민해야 하는 이슈이다. 공간 복잡도 Space Complexity 프로그램이 실행되고 완료되기까지 사용하는 총 저장 공간량을 의미한다. 고정 공간: 알고리즘과 상관 없는 공간으로 코드와 단순 변수, 상수가 해당된.. 2023. 9. 27. 1456. 거의 소수: 에라토스테네스의 체(Seive of Eratosthenes) 1456. 거의 소수 문제 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. 제한 1 ≤ A ≤ B ≤ 1014 에라토스테네스의 체 정수론: 소수 에라토스테네스의 체는 범위 내에 있는 소수를 구하는 알고리즘으로, O(N)의 시간복잡도를 가진, 소수를 구하는 방법 중 가장 빠른 알고리즘이다. 당신이 이걸 고안해내지 않는 바에야 모르면 못 푼다. 못할 건 없겠지만 시간 낭비다. 어떤 한 수가 소수인지 아닌지 판단하는 소수 판별법과는 다르므로 하나의 수가 소수인지 판단하는 것은 나중에 살펴보자. 설명 소수도, 합성수도 아닌 유일한 자연수 1을 제외한다. 2를 제외한 2의 배수를.. 2023. 8. 16. 이전 1 다음
