알고리즘 심층 분석: 소수 판별, 중복 원소 찾기, 최대 물 컨테이너 문제 해결
이 문서는 세 가지 핵심 알고리즘 문제에 대한 다양한 해결 전략과 최적화 기법을 다룹니다. 소수 판별부터 배열 내 중복 원소 탐색, 그리고 '최대 물을 담을 수 있는 컨테이너' 문제까지, 각 문제에 대한 기본 접근 방식과 개선된 솔루션을 C++ 코드를 통해 설명합니다.
1. 소수 판별 알고리즘
소수(Prime Number)는 1과 자기 자신만으로 나누어떨어지는 1보다 큰 자연수 ...
7월 9일 02:42에 게시됨
수론의 고급 알고리즘
BSGS
이산 로그 문제를 해결하기 위한 알고리즘으로, 주어진 a, b, p에 대해 a^n ≡ b (mod p)를 만족하는 최소의 양의 정수 n을 찾는 데 사용됩니다.
알고리즘 절차
이 문제는 두 가지 경우로 나눌 수 있습니다:
일반 BSGS
a와 p가 서로소(a⊥p)인 경우입니다.
이 경우 a는 역원을 가지며, BSGS는 이 성질을 이용해 제곱근 시간 알고리즘을 설계합니다.
a^n의 주기 길이는 φ ...
6월 22일 23:02에 게시됨