문제 설명정수 K와 M × N 크기의 행렬이 주어졌을 때, 행렬의 모든 원소를 동일한 값으로 만들기 위해 필요한 최소 연산 횟수를 구하는 것이 목표입니다. 여기서 한 번의 연산이란 행렬의 임의의 원소에 K를 더하거나 빼는 작업을 의미합니다.예시입력 행렬과 K 값이 다음과 같다고 가정해 보겠습니다.행렬:{    {2, 4},    {20, 40}}K = 2모든 원소를 20으로 맞추려면 총 27번의 연산이 필요합니다.Matrix[0][0]: 2 + (K × 9) =

스타인 알고리즘(Steins Algorithm), 흔히 이진 GCD 알고리즘이라고도 불리는 이 방법은 두 개의 음이 아닌 정수에 대한 최대공약수(GCD, Greatest Common Divisor)를 구하는 데 사용되는 효율적인 알고리즘입니다.이 알고리즘의 가장 큰 특징은 전통적인 유클리드 호제법처럼 나눗셈을 사용하지 않고, 비트 시프트(bitwise shift), 비교, 뺄셈 연산만으로 최대공약수를 계산한다는 점입니다. 컴퓨터에서 비트 연산은 나눗셈보다 훨씬 빠르게 처리되기 때문에 성능 면에서 큰 이점을 얻을 수 있습니다.기본 규

문제 설명n개의 양의 정수로 이루어진 배열이 주어집니다. 우리의 목표는 배열의 모든 요소를 동일한 값으로 만들기 위해 필요한 최소 연산 횟수를 구하는 것입니다. 이때 배열의 각 요소에 대해 덧셈, 뺄셈, 곱셈, 나눗셈 연산을 자유롭게 수행할 수 있습니다.예시입력 배열이 {1, 2, 3, 4}라고 가정해 보겠습니다. 모든 요소를 4로 통일하려면 1, 2, 3에 각각 한 번씩 덧셈을 수행하면 되므로, 총 3번의 연산이 필요합니다.접근 방식 및 알고리즘이 문제의 핵심은 다음과 같은 직관에서 출발합니다. 이미 값이 같은 요소가 많을수록,

문제 개요 정수 N이 주어졌을 때, N을 K개의 정수의 합으로 표현하고, 이 정수들 중 일부 또는 전체를 더하여 1부터 N까지 범위의 모든 수를 만들어야 합니다. 이때 구해야 하는 것은 가능한 한 작은 K값입니다. 핵심 아이디어 K개의 정수가 있을 때 각각을 더한다 / 더하지 않는다 두 가지로 선택할 수 있으므로, 만들어 낼 수 있는 서로 다른 합은 공집합을 제외하고 최대 2K − 1개입니다. 따라서 다음 조건을 만족하는 최소 K를 찾으면 됩니다. 2K − 1 ≥ N 흥미롭게도 이 최소 K값은 N을 이진수로 표현했을 때의 비트 개수

문제 설명 1부터 N까지의 숫자와 하나의 정수 S가 주어집니다. 이때 주어진 숫자들을 더하여 합이 정확히 S가 되도록 만들 때, 필요한 숫자 개수의 최솟값을 구하는 것이 문제입니다. 예시 예를 들어 n = 7, s = 10이라면 단 두 개의 숫자만으로 10을 만들 수 있습니다. (7, 3) (6, 4) (5, 5) 사용하는 숫자의 개수를 최소화하려면 가능한 한 큰 값을 우선적으로 선택해야 합니다. 즉, 가장 큰 숫자인 N을 먼저 더하고, 남은 합은 다시 N 이하의 숫자로 채워 나가면 됩니다. 알고리즘 정답은 아래 공식으로 간단하게

C++ STL(표준 템플릿 라이브러리)의 stable_sort() 함수는 지정된 범위의 요소들을 키(key)를 기준으로 오름차순으로 정렬하는 알고리즘입니다. 일반적인 sort() 함수와 달리, stable_sort()는 안정성(stability)을 보장한다는 점이 핵심 특징입니다. 즉, 값이 동일한 요소들이 원본 데이터에서 가졌던 상대적인 순서가 정렬 후에도 그대로 유지됩니다.예를 들어, 학생 데이터를 이름순으로 먼저 정렬한 뒤 점수순으로 다시 정렬할 때, 이름순 정렬 결과가 보존됩니다. 이러한 특성 덕분에 복합 조건 정렬이 필요한

문제 설명 행운의 숫자(Lucky Number)란 십진수 표현에서 오직 행운의 자릿수인 4와 7로만 이루어진 양의 정수를 의미합니다. 이 문제의 목표는 자릿수의 합이 정확히 n이 되는 최소의 행운의 숫자를 찾는 것입니다. 예시 예를 들어 합계(sum)가 22라면 정답은 4477입니다. 4 + 4 + 7 + 7 = 22이므로 자릿수의 합 조건을 만족하며, 가능한 조합 중에서 가장 작은 수입니다. 알고리즘 접근 방식 1. 합계가 4의 배수이면, 결과는 모두 4로 구성됩니다. 2. 합계가 7의 배수이면, 결과는 모두 7로 구성됩니다.

C++ 프로그래밍에서는 std::sort()와 같은 표준 라이브러리 함수뿐만 아니라 다양한 방법으로 문자열을 오름차순 또는 내림차순으로 정렬할 수 있습니다. 이 글에서는 strcmp()(두 문자열 비교)와 strcpy()(첫 번째 단어를 임시 변수에 복사) 함수를 활용한 버블 정렬 방식을 통해 문자열 배열을 내림차순으로 정렬하는 원리를 살펴보겠습니다.정렬 원리바깥쪽 반복문과 안쪽 반복문을 중첩하여 인접한 두 문자열을 strcmp()로 비교합니다. 앞의 문자열이 뒤의 문자열보다 사전순으로 앞선다면(strcmp 결과가 0보다 클 때),

선택 정렬(Selection Sort)이란? 선택 정렬은 정렬되지 않은 영역에서 최소 요소를 반복적으로 찾아 맨 앞으로 이동시키는 방식으로 배열을 정렬하는 알고리즘입니다. 매 반복마다 정렬되지 않은 하위 배열에서 가장 작은 요소를 선택하여 정렬된 하위 배열의 끝으로 옮기는 과정을 거칩니다. 문자열 배열을 정렬할 때는 숫자 비교 대신 strcmp() 함수로 문자열을 사전순으로 비교하고, strcpy() 함수로 문자열을 복사·교환한다는 점이 일반적인 선택 정렬과의 차이점입니다. C++ 구현 예제 #include <iostream&

이 글에서는 x, y, z 성분을 가진 두 벡터 A와 B가 주어졌을 때, 두 벡터의 내적(dot product)과 외적(cross product)을 구하는 C++ 프로그램을 다룹니다.벡터란 무엇인가?수학에서 크기(magnitude)와 방향(direction)을 모두 가지는 양을 벡터(vector)라고 하며, 반대로 크기만 가지고 방향이 없는 양은 스칼라(scalar)라고 합니다. 벡터가 시작되는 점을 시점(initial point), 끝나는 점을 종점(terminal point)이라 하며, 시점과 종점 사이의 거리가 곧 벡터의 크기

문제 개요 부호 없는 정수(unsigned number)가 하나 주어졌을 때, 이 숫자가 가진 세트 비트(set bit, 1로 설정된 비트)의 개수를 그대로 활용해 만들 수 있는 최솟값을 구하는 것이 이번 문제의 목표입니다. 최소 숫자를 만들려면 주어진 세트 비트들을 모두 가장 낮은 자릿수 쪽에 몰아 배치하면 됩니다. 상위 자릿수에 비트가 남아 있을수록 값이 커지기 때문입니다. 예시 입력이 10이라면 정답은 3입니다. 10의 이진 표현: 1010 세트 비트의 개수: 2개 2개의 세트 비트로 만들 수 있는 최소 숫자: 0011

C++에서는 포인터를 이용하면 별도의 추가 배열 없이도 문자열을 간단히 거꾸로 출력할 수 있습니다. 핵심 원리는 다음과 같습니다.먼저 strlen() 함수를 사용해 포인터가 가리키는 문자열의 길이를 계산합니다. 그다음 인덱스를 문자열의 끝에서부터 시작점까지 감소시키는 for 반복문을 실행하면서 각 문자를 순서대로 출력하면, 자연스럽게 역순의 문자열을 얻을 수 있습니다.예제 코드#include <string.h> #include <iostream> using namespace std; int main(){

이 글에서는 C++를 이용해 배열을 역순으로 뒤집는 방법을 소개합니다. 핵심 아이디어는 낮은 인덱스(low)와 높은 인덱스(high)를 두고, 두 위치의 요소를 서로 교환(swap)하면서 두 인덱스가 중앙에서 만날 때까지 배열을 순회하는 것입니다.동작 원리배열의 첫 번째 요소와 마지막 요소를 먼저 교환하고, 그다음 두 번째 요소와 뒤에서 두 번째 요소를 교환하는 방식으로 진행됩니다. low 인덱스는 앞에서 뒤로, high 인덱스는 뒤에서 앞으로 한 칸씩 이동하며, low가 high보다 작은 동안만 반복문이 실행됩니다.예제 코드#in

문제 개요서로 다른 N개의 원소로 구성된 배열이 주어졌을 때, 이 배열을 오름차순으로 정렬하기 위해 필요한 최소 스왑(교환) 횟수를 구하는 것이 이 글의 목표입니다.예시배열이 {4, 2, 1, 3}이라면 단 2번의 스왑만으로 정렬을 완료할 수 있습니다.arr[0]과 arr[2]를 교환 → {1, 2, 4, 3}arr[2]과 arr[3]을 교환 → {1, 2, 3, 4}즉, 무작정 인접한 두 원소를 반복해서 바꾸는 것보다, 각 원소가 최종적으로 위치해야 할 자리를 파악한 뒤 한 번에 올바른 위치로 옮기는 전략이 훨씬 효율적입니다.알고

n개의 프로세스와 각기 다른 크기의 m개 메모리 블록이 주어졌을 때, First Fit(최초 적합) 메모리 관리 알고리즘을 이용해 각 프로세스에 적합한 메모리 블록을 찾아 할당하는 것이 이 프로그램의 목표입니다.First Fit 메모리 관리 알고리즘이란?운영체제는 프로세스에 메모리 블록을 할당할 때 여러 가지 메모리 분할 알고리즘을 사용합니다.First Fit Algorithm (최초 적합)Next Fit Algorithm (다음 적합)Best Fit Algorithm (최적 적합)Worst Fit Algorithm (최악 적합)Q

문제 정의2차원 평면상에 여러 개의 지점이 있으며, 이 지점들은 특정한 순서대로 방문해야 합니다. 한 지점에서 다른 지점으로 이동할 때는 항상 최단 경로를 선택하며, 경로의 각 구간은 격자선(grid line)에 평행하게 이루어집니다.우리에게는 지점들을 방문하기 위해 선택된 경로가 문자열 형태로 주어집니다. 이때, 주어진 경로 전체를 생성하기 위해 반드시 필요한 최소 지점(정류장)의 개수를 구하는 것이 이 문제의 목표입니다.알고리즘지점을 방문할 때의 이동 패턴을 관찰하면 문제를 해결할 수 있습니다.한 지점에서 다른 지점까지 최단 경

C++에서는 스택(stack), 제자리(in-place) 방식, 반복문(iteration) 등 다양한 방법으로 문자열을 뒤집을 수 있습니다. 이 글에서는 가장 기본적인 반복문 방식으로 문자열을 뒤집는 알고리즘과 예제 코드를 소개합니다.알고리즘START Step-1: 문자열을 입력받는다 Step-2: length() 메서드로 문자열의 길이를 구한다 Step-3: for 루프를 사용해 마지막 문자와 첫 번째 문자를 서로 교환한다 Step-4: 결과를 출력한다 END위 알고리즘의 핵심 아이디어는 다음과 같습니

문제 정의문자열 S가 주어졌을 때, 문자열 S의 어떤 순열이라도 회문(palindrome)이 될 수 있도록 제거해야 하는 문자의 최소 개수를 구하는 것이 목표입니다.예시예를 들어 str = abcdba인 경우, 문자 1개만 제거하면 됩니다. 즉 c 또는 d 중 하나를 없애면 나머지 문자들로 회문을 만들 수 있습니다.접근 방법 및 알고리즘회문의 성질을 이용하면 간단하게 해결할 수 있습니다.회문은 길이에 따라 두 가지 유형으로 나뉩니다. 짝수 길이 회문과 홀수 길이 회문입니다.짝수 길이 회문은 모든 문자가 반드시 짝수 번 등장해야 합니

C++ 프로그래밍 코드를 사용하여 피라미드 형태의 구조를 출력하는 방법을 소개합니다. 피라미드의 높이와 공백 배치는 이중 for 루프 구조를 순회하면서 결정됩니다.예제 코드#include <iostream> using namespace std; int main() { int space, rows=6; for(int i = 1, k = 0; i <= rows; ++i, k = 0){ for(space = 1; space <= rows-i; ++space){ cou

문제 개요N개의 정수와 값 K가 주어졌을 때, 남은 원소들의 최댓값과 최솟값의 차이가 Amax - Amin ≤ K 조건을 만족하도록 하기 위해 제거해야 하는 원소의 최소 개수를 구하는 문제입니다. 원소를 제거한 후에는 남아 있는 원소들 사이에서 Amax(최댓값)와 Amin(최솟값)이 다시 계산됩니다.예시배열 arr[] = {1, 3, 4, 9, 10, 11, 12, 17, 20}이고 k = 4라고 가정해 보겠습니다. 이 경우 정답은 5입니다.배열 앞부분에서 1, 3, 4를 제거합니다.배열 뒷부분에서 17과 20을 제거합니다.최종 배