러시아 농민 곱셈(Russian Peasant Multiplication)은 두 개의 큰 수를 빠르게 곱할 수 있는 고전적인 알고리즘입니다. 이 방법은 나눗셈과 곱셈 대신 비트 시프트 연산만을 사용하기 때문에 매우 효율적이며, 컴퓨터의 이진수 연산 특성과 잘 맞아떨어집니다. 알고리즘의 원리 이 알고리즘의 핵심 아이디어는 다음과 같습니다. 한쪽 숫자(n)를 계속 2배(왼쪽 시프트)하고, 다른 쪽 숫자(m)를 계속 절반으로 나누고(오른쪽 시프트), m이 홀수일 때마다 현재의 n 값을 결과에 더합니다. m이 0이 되면 지금까지 누적된

이 글에서는 오일러 정리(Eulers Theorem)를 활용하여 모듈러 곱셈 역원(modular multiplicative inverse)을 구하는 C++ 프로그램을 소개합니다.모듈러 곱셈 역원이 존재하려면 대상 숫자와 모듈러 값이 반드시 서로소(coprime) 관계여야 합니다. 즉, 두 수의 최대공약수가 1이어야 한다는 조건입니다.알고리즘역원 배열을 계산하는 절차는 다음과 같습니다.시작 모듈러 곱셈 역원을 구할 숫자를 입력받는다 모듈러 값을 입력받는다 inverseArray 함수를 수행한다: modInverse

확장 유클리드 호제법(Extended Euclidean Algorithm)은 두 수의 최대공약수(GCD)를 구하는 또 다른 방법입니다. 일반적인 유클리드 호제법과 달리, ax + by = gcd(a, b)라는 베주 항등식(Bézouts identity)을 만족하는 정수 계수 x와 y까지 함께 계산하는 추가 변수를 사용합니다. 이러한 특성 덕분에 모듈로 역원을 구하거나 암호학 알고리즘을 구현할 때 특히 유용하며, 재귀적 구조로 작성하면 컴퓨터 프로그램에서도 효율적으로 동작합니다.알고리즘Begin 변수 a, b, x, y 선언

페르마의 소정리(小定理)는 초등 정수론의 기본 결과 중 하나로, 페르마 소수 판별법(Fermat primality test)의 이론적 기반이 됩니다. 이 정리는 1640년에 이를 언급한 피에르 드 페르마(Pierre de Fermat)의 이름을 따서 명명되었습니다.정리의 내용은 다음과 같습니다. p가 소수라면, 임의의 정수 a에 대해 ap − a는 p의 배수가 됩니다. 특히 a와 m이 서로소이고 m이 소수일 때, a의 모듈러 역원(modular inverse)은 a^(m−2) mod m으로 계산할 수 있습니다.알고리즘시작 p

0-1 배낭 문제(0-1 Knapsack Problem)는 각각 고유한 무게와 가치를 가진 물건들이 주어졌을 때, 전체 무게가 주어진 한도를 초과하지 않으면서 전체 가치가 최대가 되도록 배낭에 담을 물건을 선택하는 대표적인 최적화 문제입니다. 문제 이름 그대로 각 물건은 배낭에 넣는다(1) 또는 넣지 않는다(0)의 두 가지 선택지만 가능하며, 물건을 잘라 부분적으로 담을 수 없다는 점이 특징입니다.입력Value = [10, 20, 30, 40, 60, 70] Weight = [1, 2, 3, 6, 7, 4] int W = 7출력kn

분수 배낭 문제(Fractional Knapsack Problem)는 각각 무게와 가치를 가진 여러 아이템이 주어졌을 때, 배낭의 용량 한도 내에서 총가치를 최대화하는 문제입니다. 이 문제의 핵심은 아이템을 잘라서(부분적으로) 담을 수 있다는 점이며, 이러한 특성 덕분에 탐욕(Greedy) 알고리즘으로 최적해를 구할 수 있습니다. 문제 개념 0/1 배낭 문제와 달리, 분수 배낭 문제에서는 아이템 전체를 담지 못할 경우 일부만 잘라서 넣을 수 있습니다. 예를 들어 금가루나 쌀처럼 나눌 수 있는 물건을 생각하면 이해하기 쉽습니다. 탐욕

이 글에서는 주어진 정수의 모든 고유한 분할(partition)을 구하는 C++ 프로그램을 소개합니다. 분할이란 하나의 정수를 여러 개의 양의 정수 합으로 표현하는 방법을 의미하며, 각 분할을 구성하는 수들을 모두 더하면 원래의 정수가 됩니다. 즉, 양의 정수 n이 주어졌을 때 n을 양의 정수들의 합으로 나타낼 수 있는 서로 다른 모든 방식을 생성하는 것이 이 프로그램의 목표입니다.예를 들어 정수 4의 분할은 4, 3+1, 2+2, 2+1+1, 1+1+1+1처럼 순서만 다른 조합은 하나로 취급하여 중복 없이 모두 출력됩니다.알고리즘

빈 패킹(Bin Packing) 문제는 절단 재고(Cutting Stock) 문제의 특수한 형태입니다. 이 문제는 서로 다른 부피를 가진 물체들을 각각 용량 V를 가진 유한 개의 컨테이너(빈)에 담을 때, 사용되는 빈의 개수를 최소화하는 방법을 찾는 것이 목표입니다. 계산 복잡도 이론에서 빈 패킹은 조합론적 NP-난해(NP-hard) 문제로 분류됩니다.흥미로운 관련 문제로, 빈의 개수가 1개로 제한되고 각 물건이 부피와 가치를 모두 가질 때, 빈에 담을 수 있는 물건들의 가치 합을 최대화하는 문제를 배낭(Knapsack) 문제라고

DFT(이산 푸리에 변환)란?이산 푸리에 변환(Discrete Fourier Transform, DFT)은 함수를 균일한 간격으로 샘플링한 유한한 데이터 목록을, 동일한 샘플 값을 갖는 복소 사인파(complex sinusoid)들의 유한 조합에 대한 계수 목록으로 변환하는 수학적 기법입니다. 변환된 계수들은 주파수 순서대로 정렬되며, 이를 통해 샘플링된 함수를 원래의 도메인(주로 시간 또는 선상에서의 위치)에서 주파수 도메인으로 옮길 수 있습니다.DFT 계수는 다음과 같은 공식으로 표현됩니다.X(k) = Σ x(n) · e^(−j

이산 푸리에 변환(Discrete Fourier Transform, DFT)은 함수의 등간격 샘플들로 이루어진 유한한 목록을, 주파수순으로 정렬된 복소 정현파(complex sinusoid)의 유한 선형 조합 계수 목록으로 변환하는 수학적 기법입니다. 이를 통해 샘플링된 함수를 원래의 도메인(주로 시간 또는 직선상의 위치)에서 주파수 도메인으로 옮길 수 있습니다.이 글에서는 최적화 없이 정의 그대로 계산하는 순진한 접근 방식(naive approach)을 사용해 DFT를 구현하는 C++ 프로그램을 살펴봅니다.DFT의 기본 원리길이가

고속 푸리에 변환(Fast Fourier Transform, FFT)은 이산 푸리에 변환(DFT)과 그 역변환을 빠르게 계산하는 알고리즘입니다. 푸리에 분석은 본질적으로 시간(또는 공간) 영역의 신호를 주파수 영역으로 변환하거나, 그 반대로 변환하는 기법입니다. FFT가 빠른 이유는 DFT 행렬을 대부분 0으로 이루어진 희소(sparse) 인수들의 곱으로 분해하기 때문입니다. 덕분에 순진한 DFT 계산의 O(N²) 복잡도를 O(N log N) 수준으로 크게 줄일 수 있으며, 이미지 처리·신호 분석 등 2D 데이터에 적용되는 2D F

피보나치 수란 무엇일까요? 피보나치 수(Fibonacci numbers)는 보통 Fn으로 표기하며, 0과 1에서 시작해 각 항이 바로 앞의 두 항의 합이 되는 수열, 즉 피보나치 수열을 이룹니다. 수식으로 나타내면 다음과 같습니다. F0 = 0, F1 = 1Fn = Fn-1 + Fn-2  (n > 1) 단순 반복문으로 피보나치 수를 구하면 O(n)의 시간이 필요하지만, 행렬 거듭제곱(Matrix Exponentiation) 기법을 활용하면 분할 정복 방식으로 거듭제곱을 빠르게 계산하여 시간 복잡도를 O(log

퀵 정렬(Quicksort)은 리스트를 두 부분으로 나누는 방식으로 동작하는 정렬 기법입니다. 먼저 분할(partition) 알고리즘을 통해 피벗(pivot) 요소를 하나 선택합니다. 피벗을 기준으로 왼쪽 부분에는 피벗보다 작은 값들이, 오른쪽 부분에는 피벗보다 큰 값들이 배치됩니다. 분할이 완료되면 나누어진 각 리스트에 대해 동일한 절차를 재귀적으로 반복 적용합니다.이 글에서 다루는 구현의 특징은 피벗 요소를 무작위(랜덤)로 선택한다는 점입니다. 피벗을 무작위로 고르면 이미 정렬된 배열이나 역순 배열처럼 고정 피벗 방식에서 최악의

100개 미만의 작은 숫자들을 선형 시간, 즉 O(n) 복잡도로 정렬해야 한다면 카운팅 정렬(Counting Sort) 기법을 사용할 수 있습니다. 카운팅 정렬은 안정 정렬(stable sort) 방식의 알고리즘으로, 키 값이 작은 범위의 정수일 때 매우 효과적입니다. 이 기법은 같은 키 값을 가지는 원소의 개수를 세어(counting) 그 정보를 바탕으로 정렬된 배열을 만듭니다. 다만 키 값들 사이의 차이가 클 경우 카운트 배열의 크기가 커져 공간 복잡도가 증가할 수 있으므로, 값의 범위가 좁고 데이터 수가 많을 때 가장 유리합

퀵 정렬(Quicksort)은 리스트를 두 부분으로 분할하는 방식으로 동작하는 정렬 알고리즘입니다. 먼저 분할(Partition) 과정을 통해 피벗(Pivot) 요소를 하나 선택하고, 피벗보다 작은 값들은 왼쪽 부분에, 큰 값들은 오른쪽 부분에 배치합니다. 이후 분할된 각각의 리스트에 대해 동일한 절차를 재귀적으로 반복하여 전체를 정렬합니다.이번 글에서는 약 100개의 요소를 가진 큰 배열을 정렬하는 예제를 다룹니다. 숫자들을 무작위 순서로 섞어(unshuffle) 정렬되지 않은 상태를 만든 뒤, 퀵 정렬 기법을 적용해 정렬하는 과

병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 기법에 기반한 대표적인 정렬 알고리즘입니다. 전체 데이터 집합을 더 작은 단위로 나눈 뒤, 각 부분을 정렬된 순서에 맞게 다시 합쳐 하나의 완전한 정렬 집합으로 만듭니다. 최악의 경우에도 낮은 시간 복잡도를 보장하기 때문에 어떤 입력 상황에서든 안정적인 성능을 발휘한다는 점이 큰 장점입니다.특히 연결 리스트는 병합 정렬을 통해 매우 효율적으로 정렬할 수 있습니다. 배열과 달리 연결 리스트에서 병합 작업은 새로운 메모리를 할당할 필요 없이 노드 간 링크(

인접 행렬(Adjacency Matrix)이란?그래프의 인접 행렬은 V × V 크기의 정방행렬(square matrix)입니다. 여기서 V는 그래프 G가 가진 정점(vertex)의 개수를 의미합니다.행렬의 행과 열에는 각각 V개의 정점이 배치되며, 만약 정점 i에서 정점 j로 이어지는 간선(edge)이 존재한다면 해당 위치, 즉 i번째 행과 j번째 열에 1을 기록합니다. 가중치 그래프(weighted graph)의 경우에는 1 대신 간선의 가중치와 같은 0이 아닌 값을 저장하고, 간선이 존재하지 않는 자리는 0으로 유지합니다.인접

인시던스 행렬(Incidence Matrix)이란?그래프를 메모리에 저장하는 방법 중 하나가 바로 인시던스 행렬입니다. 인접 행렬과 달리 인시던스 행렬은 정사각형 행렬이 아니며, 그 크기는 V × E입니다. 여기서 V는 그래프의 정점(vertex) 수, E는 간선(edge) 수를 의미합니다.행렬의 각 행(row)에는 정점이 배치되고, 각 열(column)에는 간선이 배치됩니다. 간선 e = {u, v}가 존재하는 경우, 해당 간선의 열에서 u번째 행과 v번째 행의 값이 1로 표시됩니다.공간 복잡도인시던스 행렬 표현은 O(V × E)

그래프의 인접 리스트(Adjacency List) 표현법은 연결 리스트(linked list) 기반의 그래프 표현 방식입니다. 이 방식에서는 리스트들의 배열을 사용하며, 배열의 크기는 V입니다. 여기서 V는 그래프에 존재하는 정점(vertex)의 개수를 의미합니다. 다시 말해, 서로 다른 V개의 리스트를 저장할 수 있는 배열을 하나 만드는 것입니다.만약 어떤 리스트의 헤더가 정점 u라면, 해당 리스트에는 u와 인접한 모든 정점들이 담기게 됩니다.인접 리스트 표현의 복잡도무방향 그래프의 경우 O(V+2E), 방향 그래프의 경우 O(V

그래프 표현 방식과 공간 복잡도그래프를 컴퓨터 메모리에 저장하는 방법은 여러 가지가 있습니다. 대표적으로 행렬(matrix) 기반 표현과 인접 리스트(adjacency list, 연결 리스트) 기반 표현이 있습니다.먼저 참고로, 그래프의 인시던스 행렬(incidence matrix)은 정점과 간선의 관계를 나타내는 또 다른 표현 방식입니다. 이 행렬은 정방행렬이 아니며 크기는 V × E입니다(여기서 V는 정점의 수, E는 간선의 수). 행에는 정점을, 열에는 간선을 배치하며, 간선 e = {u, v}가 존재하면 해당 열의 u와 v