여러 개의 행렬을 연속해서 곱할 때는 곱하는 순서(괄호 배치)에 따라 필요한 스칼라 곱셈 횟수가 크게 달라집니다. 이 글에서는 동적 계획법(Dynamic Programming)을 활용해 곱셈 횟수를 최소화하는 최적의 괄호 배치, 즉 최적 괄호화(Optimal Parenthesization)를 구하는 C++ 프로그램을 알고리즘 설명부터 소스 코드, 실행 결과까지 자세히 다룹니다. 행렬 체인 곱셈 문제란? 먼저 왜 곱셈 순서가 중요한지 간단한 예로 살펴보겠습니다. 차원이 10×30, 30×5, 5×60인 세 행렬 A, B, C가 있다

선형대수학에서 기저(basis)는 벡터 공간 전체를 선형 결합으로 표현할 수 있으면서 서로 선형 독립인 벡터들의 집합을 의미하며, 차원(dimension)은 그 기저를 이루는 벡터의 개수를 뜻합니다. 정방행렬의 행렬식(determinant)이 0이 아니면, 해당 행렬의 열벡터들은 Rn 공간의 기저를 형성합니다.아래는 이 원리를 이용해 주어진 행렬의 기저 여부를 판별하는 C++ 프로그램입니다. 프로그램은 재귀적으로 행렬식을 계산하고, 그 값이 0인지 아닌지에 따라 결과를 출력합니다.알고리즘시작 함수 determinant() :

C++를 사용하여 대수식의 최솟값을 찾는 프로그램을 소개합니다. (x1 + x2 + x3 + … + xa) × (y1 + y2 + … + yb) 형태의 대수식과 (a + b)개의 정수가 주어졌을 때, a개의 숫자와 나머지 b개의 숫자로 만들 수 있는 모든 조합을 고려해 값을 계산한 뒤, 그중 가장 작은 값을 도출하는 것이 목표입니다. 알고리즘 Begin function MinValue() : Arguments: a[] = 요소들을 저장하는 배열 x, y = 정수 Body of the

이 글에서는 임의의 대수식에서 최댓값을 찾는 C++ 프로그램을 소개합니다.(x1 + x2 + x3 + … + xa) * (y1 + y2 + … + yb) 형태의 대수식과 총 (a + b)개의 정수가 주어졌을 때, 앞의 a개 숫자와 나머지 b개 숫자로 만들 수 있는 모든 조합을 고려하여 각 경우의 곱셈 값을 계산한 뒤, 그중 가장 큰 값을 도출하는 것이 목표입니다.알고리즘시작 함수 MaxValue() : 매개변수: a[] = 요소들을 저장하는 배열 x, y = 정수 함수 본문: 1) 배열 요

모듈러 지수 연산(Modular Exponentiation)은 (base^exp) % mod 형태의 거듭제곱 나머지 값을 효율적으로 계산하는 알고리즘입니다. 이 연산은 RSA와 같은 공개키 암호 시스템의 핵심으로 활용되며, 매 단계마다 모듈러 연산을 적용해 중간값이 커지지 않도록 함으로써 오버플로우 없이 빠른 계산을 가능하게 합니다.알고리즘이 알고리즘은 지수를 비트 시프트로 반복해서 2로 나누고, 그때마다 밑을 제곱하는 거듭 제곱 기법을 사용합니다. 단순히 밑을 지수만큼 반복 곱하는 방식(O(n))과 달리 O(log n)의 시간 복

C++를 이용하면 사용자가 지정한 길이(M)의 암호를 여러 개(N개) 손쉽게 생성할 수 있습니다. 이 프로그램은 먼저 rand() 함수로 0~9 사이의 난수를 만든 뒤, 순열(permutation) 알고리즘과 백트래킹 기법을 적용해 해당 숫자들의 다양한 조합을 암호로 출력합니다. 알고리즘 프로그램의 핵심 동작 흐름은 아래 의사코드(pseudo-code)와 같습니다. Begin 암호의 길이를 입력받는다. permutation() 함수가 무작위 암호를 생성한다. /* 매개변수 설명 a : 정수 배열의

이 프로그램은 무작위로 선택된 정점과 간선을 이용해 랜덤 그래프를 생성합니다. 프로그램의 시간 복잡도는 O(v×e)이며, 여기서 v는 정점(vertex)의 개수, e는 간선(edge)의 개수를 의미합니다. 알고리즘 시작 간선의 개수 e와 정점의 개수 v를 매개변수로 받는 GenRandomGraphs() 함수를 작성한다. rand() 함수를 사용해 그래프의 정점 수와 간선 수에 임의의 값을 할당한다. 방향에 관계없이 각 정점의 연결 정보를 출력한다. 차수가 0인 정점(고립된 정점)에는 &

해밀턴 순환이란?해밀턴 순환(Hamiltonian Cycle)은 그래프 이론에서 매우 중요한 개념입니다. 무방향 그래프에서 모든 정점을 정확히 한 번씩만 방문하는 경로를 해밀턴 경로(Hamiltonian Path)라고 하며, 이 경로의 마지막 정점에서 시작 정점으로 돌아가는 간선이 존재할 때 이를 해밀턴 순환이라고 부릅니다.즉, 해밀턴 순환은 그래프의 모든 정점을 딱 한 번씩 거쳐 다시 출발점으로 되돌아오는 닫힌 경로입니다. 이 문제는 NP-완전(NP-Complete) 문제에 속하기 때문에, 일반적으로 백트래킹(backtrackin

개요이 프로그램은 그래프의 간선 연결성(Edge Connectivity), 즉 브리지(Bridge, 다리 간선)를 찾는 방법을 다룹니다. 브리지란 해당 간선을 제거했을 때 그래프가 연결 해제(disconnect)되는 간선을 의미합니다. 무방향 그래프에서 브리지를 하나 제거하면 연결 요소(connected component)의 개수가 증가하게 됩니다.즉, 그래프 전체의 연결을 끊기 위해 잘라내야 하는 최소 간선을 찾는 문제이며, 이는 깊이 우선 탐색(DFS)과 low 값 계산을 통해 효율적으로 해결할 수 있습니다.connections

이 글에서는 그래프 이론의 중요한 개념 중 하나인 피드백 아크 집합(Feedback Arc Set)을 찾는 C++ 프로그램을 다룹니다. 피드백 아크 집합이란, 그래프에서 특정 간선들을 제거했을 때 그래프가 방향 비순환 그래프(DAG, Directed Acyclic Graph), 즉 순환이 없는 방향 그래프가 되도록 만들어 주는 간선들의 집합을 의미합니다.알고리즘시작 함수 checkCG(int n): n: 정점의 개수 arr: 그래프 구조체 변수 cnt = 0, size = (n-1)로 초기화 i = 0부

해밀턴 순환(Hamiltonian Cycle)이란 해밀턴 경로(Hamiltonian Path)의 마지막 정점에서 첫 번째 정점으로 다시 연결되는 간선이 존재하는 경로를 말합니다. 즉, 무방향 그래프에서 그래프의 모든 정점을 정확히 한 번씩만 방문하고 시작점으로 되돌아오는 순환 경로입니다. 알고리즘 구성 및 역할 이 프로그램은 백트래킹(Backtracking) 기법을 사용하여 해밀턴 순환 문제를 해결하며, 주요 함수는 다음과 같습니다. 시작 1. isSafe() 함수: 현재 추가하려는 정점이 이전에 추가된 정점과

개요주어진 방향 그래프(directed graph)가 약하게 연결(weakly connected)된 그래프인지, 아니면 강하게 연결(strongly connected)된 그래프인지는 깊이 우선 탐색(DFS)을 활용하여 판별할 수 있습니다. 이 글에서는 그 대표적인 방법인 코사라주(Kosaraju) 알고리즘을 이용해 그래프의 강결합 요소(Strongly Connected Component, SCC)를 찾는 C++ 프로그램을 소개합니다.강결합 요소란 그래프 내 임의의 두 정점 u, v에 대해 u에서 v로 가는 경로와 v에서 u로 가는

DFS(깊이 우선 탐색)를 활용하면 주어진 무방향 그래프가 약연결(weakly connected) 상태인지 강연결(strongly connected) 상태인지 판별할 수 있습니다. 이 글에서는 그래프의 강연결 요소(SCC)를 찾아 연결 상태를 확인하는 C++ 프로그램을 소개합니다. 핵심 개념 정리 강연결은 그래프의 모든 정점 쌍이 서로 도달 가능한 경우를 말하며, 약연결은 간선의 방향을 무시했을 때만 전체가 하나로 이어지는 경우를 말합니다. 이 프로그램은 코사라주(Kosaraju) 알고리즘을 응용하여 강연결 요소의 개수를 센 뒤,

이 글에서는 C++를 사용해 그래프의 최대 컷(maximum cut)을 찾는 방법을 다룹니다. 핵심은 그래프의 에지 연결성(edge connectivity)을 구하는 것으로, 이는 곧 브리지(bridge, 단절선)를 찾는 문제와 같습니다. 브리지란 그래프에서 해당 간선 하나만 제거해도 그래프가 둘 이상의 연결 요소로 분리되어 버리는 간선을 의미합니다. 즉, 무향 그래프에서 브리지를 제거하면 연결 요소(connected component)의 개수가 늘어나게 됩니다. 핵심 개념: 브리지(단절선)란? 무향 그래프에서 간선 (w, x)를

그래프의 정점 연결성(Vertex Connectivity)을 구하려면 먼저 해당 그래프의 단절점(Articulation Points)을 찾아야 합니다. 그래프에서 단절점(또는 컷 버텍스, Cut Vertex)이란 그 정점과 연결된 간선들을 함께 제거했을 때 그래프 전체가 분리되어 버리는 정점을 의미합니다. 또한 비연결(disconnected) 무방향 그래프에서는, 특정 정점을 제거했을 때 연결 요소(connected component)의 개수가 증가한다면 그 정점이 단절점이라고 할 수 있습니다.알고리즘단절점을 찾기 위해 DFS(깊이

rand() 함수란?C++에서 난수를 생성할 때 가장 기본적으로 사용되는 것이 바로 rand() 함수입니다. 이 함수는 C++에 미리 정의된 표준 라이브러리 함수로, <stdlib.h>(C++에서는 <cstdlib>) 헤더 파일에 선언되어 있습니다.rand()는 호출될 때마다 임의의 정수를 반환하며, 나머지 연산자(%)와 함께 사용하면 원하는 범위 안의 난수를 손쉽게 만들 수 있습니다. 여기서 min_n은 생성할 난수의 최솟값, max_n은 최댓값을 의미합니다.난수 생성에 사용되는 핵심 공식은 다음과 같습니다.

C++를 사용해 랜덤 16진수(Hexadecimal) 값을 생성하는 프로그램을 만들어 보겠습니다. 이번 글에서는 rand() 함수와 itoa() 함수를 활용하는데, 각 함수가 어떤 역할을 하는지 하나씩 자세히 살펴본 뒤 전체 코드를 구현해 보겠습니다. rand() 함수란? rand()는 C++에 미리 정의되어 있는 표준 함수로, <stdlib.h> 헤더 파일에 선언되어 있습니다. 이 함수는 지정한 범위 내에서 난수(random number)를 생성하는 용도로 사용됩니다. 여기서 min_n은 난수 범위의 최솟값, max_

솔로베이-스트라센(Solovay-Strassen) 소수성 테스트는 오일러 준거(Euler Criterion)에 기반한 확률적 알고리즘으로, 주어진 수가 합성수인지 아니면 소수일 가능성이 높은지를 판별하는 데 사용됩니다. 이 테스트는 여러 번의 반복을 거치며 합성수를 소수로 오판할 확률을 지수적으로 낮추기 때문에, 큰 수의 소수 여부를 빠르게 검사해야 하는 상황에서 유용하게 활용됩니다. 알고리즘 전체 알고리즘은 세 가지 핵심 함수로 구성됩니다. 1. 모듈러 거듭제곱 함수 (modulo) 시작 이진 계산을 수행하기 위한 modu

Baillie-PSW 소수성 테스트는 Robert Baillie, Carl Pomerance, John Selfridge, Samuel Wagstaff 네 사람의 이름을 딴 소수 판별 알고리즘입니다. 이 테스트는 주어진 수가 합성수(composite number)인지, 아니면 소수일 가능성이 있는 수인지를 판별합니다. 완전한 Baillie-PSW 테스트는 강한 유사소수 검사(밀러-라빈 테스트)와 뤼카(Lucas) 테스트를 결합한 형태이며, 흥미롭게도 아직까지 이 테스트를 통과하면서 실제로는 합성수인 반례는 단 하나도 발견되지 않았습

C++에서는 클래스 내부에 정적(static) 멤버(함수 또는 변수)를 선언할 수 있습니다. 이번 글에서는 특히 private 정적 멤버 변수를 초기화하는 방법을 알아보겠습니다.정적 멤버 변수는 클래스의 모든 객체가 공유하는 단 하나의 복사본만 존재하기 때문에, 일반 멤버 변수처럼 생성자에서 초기화할 수 없습니다. 대신 클래스를 정의한 후, 클래스 외부에서 별도로 초기화해야 합니다.초기화 문법은 다음과 같습니다. 먼저 클래스 이름을 쓰고, 범위 지정 연산자(::)를 붙인 뒤 변수 이름을 적고 값을 할당하면 됩니다.클래스이름::변수이