전체 글23 Fermat's Little Theorem & Miller-Rabin Primality Test 이 글을 읽기 전 알아야 할 내용 (하단 더보기 클릭) 더보기 본 내용을 시작하기에 앞서 학습되어 있어야 할 내용은 정수론에서 합동식의 개념과 성질에 관한 것과 Big-O 표기법에 대한 내용입니다. Big-O 표기법에 대한 내용은 아래 링크를 통해 보실 수 있고, 합동식에 관한 내용은 추후에 업로드 예정이나, 일정을 잡지 못하여 업로드 하는대로 Big-O 표기법과 같이 링크를 달아두로록 하겠습니다. (그 전까지는 다른 것을 보고 학습한 후 이 글을 읽는 것을 추천합니다.) 또한 라그랑주 정리와 관련해서는 추후에 업로드 하도록 하겠습니다. 2023.04.07 - [Algorithm] - 시간 복잡도(Big-O) 밀러-라빈 소수 판별법은 주어진 수가 소수인지 아닌지 판별하는 알고리즘으로, 확률적 알고리즘이다.. 2023. 4. 8. 시간 복잡도(Big-O) 문제를 해결하기 위한 알고리즘을 코드로 구현할 때 연산 횟수에 따른 걸리는 시간을 계산한 것이 시간 복잡도이다. 즉, 쉽게 설명하면 작성한 코드를 돌렸을 때 컴퓨터가 이를 수행하는 데에 걸리는 시간을 시간 복잡도라고 한다. 이러한 시간 복잡도를 정보과학에서는 특정 기호로 표기하고, 그 중 가장 많이 사용하는 표기법이 Big-O 표기법이다. 빅-오 표기법은 알고리즘이 해당 차수이거나 그보다 낮은 차수의 시간 복잡도를 가진다는 의미로, 알고리즘의 최악의 실행 시간을 표기한다. 특징 상수항 및 계수를 무시한다. 어떤 알고리즘이 O(2N+9)의 시간복잡도를 가진다면 이는 O(N)으로 표기 최고차항만 표기한다. 어떤 알고리즘에 대한 시간 복잡도가 O(3N^2+8N+118)이라면 이는 O(N^2)으로 표기한다. 중.. 2023. 4. 7. 탐구활동 3 입력된 어떤 양의 정수의 가장 큰 소인수를 출력하는 프로그램을 for 반복 구조를 사용하여 작성해 보자. (예를 들어 13195의 가장 큰 소인수는 29이다.) 해설 더보기 수학적으로 생각해보면 소인수의 정의는 주어진 자연수를 나누어떨어뜨리는 소수인 약수를 말한다. 따라서 주어진 수를 나누어떨어뜨리면서 소수인 수 중 최댓값을 파악하면 된다. 1부터 큰 값으로 가면서 체크하면 굳이 최댓값을 판별하기 위해 노력할 필요없이 그냥 계속 값을 업데이트 해주면 된다. 따라서 1부터 큰 값으로 이동하면서 주어진 자연수를 나누어뜨리면서 소수인 수를 찾는데 반복횟수를 줄여주기 위해서 만약 소인수를 찾았다면 값을 업데이트해줌과 동시에 처음에 주어줬던 자연수를 해당 소인수로 나누어 처음 주어진 수의 크기를 계속 줄여나간다... 2023. 4. 7. 탐구활동 2 입력된 두 양의 정수의 공약수를 모두 출력하는 프로그램을 작성해 보자. (예를 들어 8 24와 같이, 두 개의 양의 정수가 입력되었을 때에는 1 2 4 8이 출력되어야 한다.) 해설 더보기 두 정수를 받을 때 각 변수를 a, b라 하자. 이때 일반성을 잃지 않고 a≤b라고 가정하면 반복문을 1부터 a까지 돌리면서(이때 해당하는 값을 i라 하자.) 0 ≡ i (mod a), 0 ≡ i (mod b)를 만족하는 i를 모두 출력하면 된다. (∵ a보다 큰 값에 대해서는 a의 약수에 해당하는 수가 존재하지 않기 때문에 반복문을 1부터 a까지만 돌려줘도 된다.) 하지만 ab이면 a와 b의 값을 swap 해주는 코드도 작성한다. 코드 더보기 #include using namespace std; int f_swap(.. 2023. 4. 7. 이전 1 2 3 4 5 6 다음
