Naor-Reingold 의사 난수 함수(Pseudo Random Function)는 난수를 생성하는 또 다른 방법 중 하나입니다.모니 나오르(Moni Naor)와 오메르 라인골드(Omer Reingold)는 1997년에 개인키 암호화 및 공개키 암호화 분야의 다양한 암호학적 기본 요소(primitive)에 대한 효율적인 구성 방법을 발표했습니다.p와 l이 l | p−1 조건을 만족하는 소수라고 가정해 보겠습니다. 이때 곱셈 차수(multiplicative order)가 l인 원소 g ∈ Fp*를 선택합니다. 그런 다음 각 n차원

곱하기-캐리(Multiply-with-Carry) 방법이란?곱하기-캐리(MWC) 방법은 Marsaglia와 Zaman이 1991년에 발표한 더하기-캐리(Add-with-Carry) 생성기의 변형입니다. 이 방법의 가장 큰 장점은 단순한 컴퓨터 정수 연산만으로 구현할 수 있다는 점과, 약 260에서 22000000에 이르는 엄청나게 긴 주기를 가진 난수 수열을 매우 빠른 속도로 생성할 수 있다는 점입니다.MWC에서는 밑(base) b를 컴퓨터 워드(word) 크기와 같게 설정하며, 승수(multiplier) a와 지연(lag) r이

이 글에서는 N개의 주사위 굴리기를 에뮬레이트하는 C++ 코드를 소개합니다. 핵심 원리는 간단합니다. 1부터 6 사이의 난수를 생성하면 그것이 곧 주사위를 한 번 굴린 결과가 되는 것입니다.동작 원리C++ 표준 라이브러리의 rand() 함수는 임의의 정수를 반환합니다. 여기에 나머지 연산자(%)를 활용하여 rand() % 6 + 1을 계산하면, 결과값은 항상 1~6 범위 안에 있게 됩니다. 이 값이 바로 하나의 주사위 눈이 됩니다. 사용자가 입력한 개수(N)만큼 반복하면 N개의 주사위를 동시에 굴린 것과 같은 효과를 얻을 수 있습니

휠 체(Wheel Sieve)는 주어진 범위 사이의 소수를 찾는 데 사용되는 방법입니다. 휠 인수분해(wheel factorization)는 에라토스테네스의 체(Sieve of Eratosthenes)를 본격적으로 수행하기 전에 소수와 합성수를 미리 걸러내는 과정을 시각적으로 수행하는 그래픽 기법입니다.이 방법에서는 가장 안쪽 원에 배치된 소수들의 배수가 바깥쪽 원들에서도 자신과 같은 상대적 위치에 나타납니다. 그 결과 소수와 그 배수들이 마치 바퀴살(spoke)처럼 뻗어 나가는 형태를 이루게 되며, 안쪽 원의 소수들에 대한 배수들

이 글에서는 C++로 에라토스테네스의 체(Sieve of Eratosthenes)를 구현하여 주어진 범위 안의 모든 소수를 생성하는 방법을 다룹니다.에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 고안한 가장 고전적이면서도 효율적인 소수 판별 알고리즘입니다. 이 방법의 핵심 아이디어는 다음과 같습니다.크기가 n인 정수 배열을 선언하고 모든 요소를 0으로 초기화합니다.중첩 루프를 돌면서 각 수의 배수에 해당하는 인덱스(합성수)를 1로 표시합니다.최종적으로 배열 값이 0으로 남아 있는 인덱스가 바로 소수입니다.알고리즘Begin

C++에서 파일을 읽을 때 루프 조건으로 iostream::eof()를 사용하는 방식은 잘못된 관행으로 간주됩니다. 그 이유는 간단합니다. eof()를 호출하는 시점에는 아직 파일 끝(EOF)에 도달하지 않았을 수 있으며, 따라서 EOF에 도달하지 않았다는 사실이 곧 다음 읽기가 반드시 성공한다는 의미가 되지 않기 때문입니다. eof()는 미래를 예측하는 함수가 아니라, 이전 입출력 연산에서 파일 끝에 도달했는지를 알려주는 상태 플래그일 뿐입니다. 그럼에도 while(!stream.eof()) 형태의 루프가 자주 사용되는데, 이는

리눅스 플랫폼에는 C++ 프로그램의 성능을 분석할 수 있는 강력한 프로파일링 도구가 다양하게 존재합니다. 그중 가장 널리 사용되는 대표적인 도구가 바로 Valgrind와 gprof입니다. 이 글에서는 두 도구를 활용해 C++ 코드를 프로파일링하는 기본적인 방법을 소개합니다.Valgrind를 이용한 프로파일링Valgrind는 메모리 디버깅, 메모리 누수 탐지, 성능 프로파일링까지 지원하는 만능 프로그래밍 도구입니다. 특히 callgrind 도구를 함께 사용하면 함수별 실행 시간과 호출 관계를 상세히 분석할 수 있습니다.먼저 프로파일링

복사 생략(Copy Elision)은 복사 생략(Copy Omission)이라고도 불리며, 컴파일러가 불필요한 객체 복사를 제거하는 대표적인 최적화 기법입니다. 현재 사용되는 거의 모든 C++ 컴파일러는 이 기술을 기본적으로 지원하고 있으며, 특히 객체를 반환하거나 초기화할 때 성능 향상에 큰 도움을 줍니다.그렇다면 복사 생략은 실제로 어떻게 동작할까요? 아래 예제 코드를 통해 살펴보겠습니다.예제 코드#include <iostream> using namespace std; class MyClass { public:

Atkin의 체(Sieve of Atkin)는 지정된 정수까지의 모든 소수를 찾는 현대적인 알고리즘입니다. 고전적인 에라토스테네스의 체와 달리, Atkin의 체는 이차 형식(quadratic form)의 해의 개수를 활용해 소수 후보를 수학적으로 판별하므로 이론적으로 더 높은 효율을 기대할 수 있습니다. 이 글에서는 주어진 범위 내의 소수를 생성하기 위해 Atkin의 체를 C++로 구현하는 방법을 단계별로 살펴봅니다.알고리즘Atkin의 체의 전체 동작 과정은 다음과 같습니다.시작    결과 리스트

이 글에서는 세그먼트 체(Segmented Sieve) 알고리즘을 활용해 주어진 범위 사이의 소수를 생성하는 C++ 프로그램을 소개합니다. 세그먼트 체는 먼저 단순 체(Simple Sieve of Eratosthenes)를 이용해 √(n) 이하의 소수를 모두 구한 뒤, 전체 범위 [0 ... n-1]을 여러 개의 구간(segment)으로 나누고 각 구간별로 소수를 순차적으로 계산하는 방식입니다.이러한 분할 처리 방식 덕분에 매우 큰 수 범위에서도 메모리 사용량을 크게 줄일 수 있어, 일반적인 에라토스테네스의 체보다 효율적으로 동작합

GCC 링크 오류, 왜 라이브러리 순서가 문제가 될까?이러한 종류의 오류는 기본적으로 컴파일 과정의 링커(linker)에서 비롯됩니다. 링커의 기본 동작 방식은 현재 프로그램이 필요로 하는 시점에 아카이브 라이브러리(정적 라이브러리)에서 해당 코드를 가져오는 것입니다.링커의 기본 동작 원리링커는 명령줄에 나열된 파일을 왼쪽에서 오른쪽으로 처리하면서, 그 시점까지 아직 해결되지 않은(undefined) 심볼만 라이브러리에서 찾아 연결합니다. 따라서 어떤 라이브러리가 다른 라이브러리에 정의된 함수를 참조한다면, 참조하는 쪽(호출자)이

C++에는 C 스타일 캐스트를 대체하는 네 가지 명시적 캐스트 연산자가 있습니다. static_cast, dynamic_cast, const_cast, reinterpret_cast가 그것인데, 각각의 목적이 분명하게 구분되어 있으므로 상황에 맞게 올바르게 선택하는 것이 중요합니다. 1. const_cast — const 속성의 추가 및 제거 const_cast는 변수에서 const 속성을 제거하거나 추가할 때 사용합니다. const로 선언된 변수의 const 속성을 조작해야 하는 경우에 유용합니다. 예를 들어, const 포인터

란 무엇인가?는 C++의 모든 표준 라이브러리를 한 번에 포함시켜 주는 헤더 파일입니다. 알고리즘 문제 풀이나 코딩 대회에서 여러 헤더 파일을 일일이 작성할 시간을 아끼고 싶을 때 유용하게 사용됩니다. 예를 들어 , , , 등을 개별적으로 선언하지 않아도 되기 때문에 코드 작성 속도가 빨라집니다.그러나 실제 소프트웨어 개발 환경에서는 필요한 헤더만 최소한으로 포함하는 것이 원칙입니다. 이 헤더 파일을 사용하면 프로그램에 실제로 필요하지 않은 수많은 파일까지 함께 불러오게 되어, 컴파일 시간 증가와 실행 파일 크기 확대 등의 문제가

C/C++에서 #include 지시자를 사용할 때 꺾쇠 괄호(<>)와 큰따옴표() 중 어떤 것을 쓰느냐에 따라 전처리기가 헤더 파일을 찾는 경로가 달라집니다. #include <파일명> 컴파일러가 미리 지정한 시스템 포함 디렉터리(표준 라이브러리 경로 등)에서 파일을 검색합니다. 주로 표준 라이브러리 헤더나 시스템 헤더를 포함할 때 사용합니다. #include 파일명 현재 소스 파일이 위치한 디렉터리(또는 지시자가 있는 파일 기준)에서 먼저 파일을 찾습니다. 만약 그곳에서 찾지 못하면 #include <파

라빈-밀러 소수 판별 테스트란?라빈-밀러(Rabin-Miller) 소수 판별 테스트는 주어진 수가 소수(prime number)인지 아닌지를 판별하는 대표적인 확률적 알고리즘입니다. 페르마 소수 판별법이나 솔로베이-스트라센(Solovay-Strassen) 테스트와 유사한 방식으로 동작하며, 이 테스트의 기반이 되는 개념은 처음에 러시아 수학자 M. M. 아르튜호프(M. M. Artjuhov)에 의해 발견되었습니다.이 테스트는 페르마의 소정리에 기반을 두고 있습니다. 홀수 n이 소수일 때, n−1 = 2s·d(d는 홀수) 형태로 분해

이 글에서는 C++를 이용해 숫자들의 최대공약수(GCD)와 최소공배수(LCM)를 구하는 방법을 알아봅니다.최대공약수(Greatest Common Divisor, GCD)란 0이 아닌 두 개 이상의 정수를 모두 나누어 떨어지게 하는 가장 큰 양의 정수를 의미합니다. 흔히 최대 공통 인수(Greatest Common Factor)라고도 부릅니다.최소공배수(Least Common Multiple, LCM)는 두 수의 공통 배수 중에서 0이 아닌 가장 작은 수를 말합니다.알고리즘 number2) ? number1 : number2

이 글에서는 순다람의 체(Sieve of Sundaram)를 이용하여 주어진 범위 사이의 소수를 생성하는 C++ 프로그램을 소개합니다. 순다람의 체는 1934년 인도의 수학자 순다람(Sundaram)이 발견한 알고리즘으로, 에라토스테네스의 체와 마찬가지로 합성수를 걸러내는 방식이지만 홀수만을 대상으로 처리하기 때문에 필요한 메모리가 절반으로 줄어드는 것이 특징입니다.알고리즘n보다 작은 소수를 모두 찾는 것이 목표입니다. 먼저 n-2를 절반으로 나눈 값을 New라 하고, i + j + 2ij(단, 1 ≤ i ≤ j) 형태의 수를 걸러

페르마 소수성 테스트(Fermat Primality Test)는 주어진 수가 소수인지 아닌지를 판별하는 확률적 알고리즘입니다. 이 테스트는 페르마의 소정리에 기반하며, 다음과 같습니다.p가 소수이고 a가 p의 배수가 아니라면, 항상 ap-1 ≡ 1 (mod p)가 성립합니다.즉, 무작위로 선택한 밑(base) a에 대해 am-1 mod m의 값이 1이 아니라면 m은 합성수임이 확실하고, 1이라면 m이 소수일 가능성이 높다고 판단하는 방식입니다. 아래에서 알고리즘의 동작 원리와 C++ 전체 코드를 살펴보겠습니다.알고리즘핵심 함수는 두

부스 곱셈 알고리즘(Booths Multiplication Algorithm)은 2의 보수(2s complement) 표기법으로 표현된 두 개의 부호 있는 이진수를 곱하기 위한 효율적인 알고리즘입니다. 앤드류 도널드 부스(Andrew Donald Booth)는 덧셈보다 시프트 연산이 더 빨랐던 탁상용 계산기의 특성을 활용하여 연산 속도를 향상시키고자 이 알고리즘을 고안했습니다. 알고리즘 핵심 원리 부스 알고리즘은 곱셈기(Multiplier)의 비트 쌍(Qn, Qn+1)을 검사하여 연산을 결정합니다. 피승수(Multiplicand)

Schönhage-Strassen(숀하게-스트라센) 알고리즘은 두 개의 수를 곱하는 데 사용되는 알고리즘으로, 특히 아주 큰 정수에 대해 점근적으로 빠른 성능을 보이는 곱셈 방식입니다. 실제 환경에서 이 알고리즘은 2215 ~ 2217(십진수 약 10,000 ~ 40,000자리) 범위를 넘는 숫자에 대해 카라추바(Karatsuba), 툼-쿡(Toom-Cook)과 같은 기존 방법보다 우수한 성능을 발휘하기 시작합니다. 알고리즘 아래 의사 코드는 각 수의 자릿수를 구하고, 선형 컨볼루션(linear convolution)을 계산한 후,