이 글에서는 C++ STL(표준 템플릿 라이브러리)을 활용하여 사용자가 지정한 범위 안에 있는 모든 소수(prime number)를 찾아 출력하는 프로그램을 다룹니다.핵심 아이디어는 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘으로 0부터 각 경계값까지의 소수 목록을 두 개 만든 뒤, STL의 set_difference 함수로 두 목록의 차집합을 구하는 것입니다. 그러면 시작 값보다 크면서 끝 값 이하인 소수만 깔끔하게 남게 됩니다.알고리즘프로그램의 전체 흐름은 다음 세 단계로 구성됩니다.1단계 — 0부터 n

프뤼퍼(Prüfer) 코드는 레이블이 붙은 트리(tree)를 고유한 수열 하나로 표현하는 방법입니다. 사용자가 그래프 형태로 입력한 트리에서 노드에 1부터 p까지의 레이블이 붙어 있다면, 이 트리는 길이가 p − 2인 수열로 유일하게 식별됩니다. 즉, 정점이 n개인 트리는 항상 n−2개의 값으로 이루어진 프뤼퍼 코드를 가지며, 서로 다른 트리는 반드시 서로 다른 코드를 갖습니다. 프뤼퍼 코드를 만드는 기본 원리는 다음과 같습니다. ① 현재 남아 있는 리프(leaf, 차수가 1인 정점) 중에서 레이블이 가장 작은 정점을 찾습니다.②

이 글에서는 C++를 사용하여 이진 탐색 트리(Binary Search Tree, BST)에서 최솟값을 찾는 프로그램을 소개합니다.이진 탐색 트리의 핵심 성질 덕분에 최솟값을 찾는 것은 매우 간단합니다. BST에서는 모든 노드에 대해 왼쪽 자식은 부모보다 작거나 같고, 오른쪽 자식은 부모보다 크거나 같은 규칙이 유지됩니다. 따라서 루트 노드에서 시작해 왼쪽 자식 노드를 계속 따라 내려가면, 더 이상 왼쪽 자식이 없는 가장 왼쪽 끝 노드의 값이 곧 트리의 최솟값이 됩니다.알고리즘최솟값을 찾는 절차는 다음과 같습니다.시작 구조체

오늘날 프로그램은 우리 일상 깊숙이 들어와 있습니다. 사물인터넷(IoT)과 연결된 자동화 기술이 보편화되면서 소프트웨어는 현대 사회를 움직이는 핵심 동력이 되었습니다.그렇다면 개발자들에게 가장 사랑받는 프로그래밍 언어는 무엇일까요? 단연 C++, Java(자바), Python(파이썬)입니다. 이 세 가지 언어는 각각 고유한 특징과 장단점을 가지고 있으며, 용도에 따라 선택 기준이 크게 달라집니다.세 가지 언어의 기본 특성C++ — 빠르고 강력한 컴파일 언어C++은 컴파일 방식의 언어로, 뛰어난 실행 속도 덕분에 오랫동안 인기를 유지

이번 글에서는 흥미로운 부울 행렬(Boolean Matrix) 문제를 다뤄보겠습니다. 0과 1로만 구성된 부울 행렬이 주어졌을 때, 1이 표시된 위치를 찾아 해당 행과 열 전체를 모두 1로 변경하는 것이 목표입니다. 예를 들어 행렬의 mat[i][j] 위치에 1이 있다면, i번째 행의 모든 요소와 j번째 열의 모든 요소를 1로 만들어야 합니다. 문제 이해하기 다음과 같은 4x4 행렬이 주어졌다고 가정해 봅시다. 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 이 행렬에서 1은 (0,0), (0,3), (3,1) 세 곳에 있

이 글에서는 배열과 관련된 흥미로운 문제인 곱 배열(Product Array) 퍼즐을 다뤄보겠습니다. n개의 원소를 가진 배열이 주어졌을 때, 같은 크기의 새로운 배열을 만들어야 합니다. 이때 새 배열의 i번째 위치에는 원본 배열의 i번째 원소를 제외한 나머지 모든 원소들의 곱이 들어가야 합니다.여기에는 두 가지 까다로운 제약 조건이 있습니다. 첫째, 나눗셈 연산자를 사용할 수 없습니다. 둘째, O(1)의 추가 공간, 즉 별도의 보조 배열 없이 문제를 해결해야 합니다.나눗셈을 쓰면 얼마나 쉬워지나?만약 나눗셈을 사용할 수 있다면 문

문제 소개배열과 관련된 흥미로운 문제를 하나 살펴보겠습니다. n개의 원소를 가진 배열이 주어졌을 때, 같은 크기의 또 다른 배열을 만들어야 합니다. 이때 결과 배열의 i번째 위치에는 원본 배열에서 i번째 원소를 제외한 나머지 모든 원소들의 곱이 들어가야 합니다.여기서 중요한 제약 조건은 바로 나눗셈 연산자(/)를 사용할 수 없다는 점입니다.나눗셈을 쓸 수 있다면 얼마나 쉬울까?만약 나눗셈 사용이 허용된다면 문제는 매우 간단해집니다. 먼저 배열의 모든 원소를 곱해 전체 곱을 구한 뒤, i번째 원소로 나누어 그 값을 결과 배열의 i번째

이번 글에서는 배열과 관련된 흥미로운 코딩 퍼즐을 살펴보겠습니다. n개의 요소를 가진 배열이 주어졌을 때, 같은 크기의 새로운 배열을 만들어야 합니다. 이때 결과 배열의 i번째 위치에는 원본 배열에서 i번째 요소를 제외한 나머지 모든 요소들의 합이 들어가야 합니다.여기에 한 가지 까다로운 제약 조건이 있습니다. 바로 뺄셈 연산자를 사용할 수 없다는 점입니다.왜 이 문제가 어려울까?만약 뺄셈을 사용할 수 있다면 문제는 아주 간단합니다. 전체 요소의 합을 미리 구한 뒤, 각 위치에서 해당 요소만 빼주면 되기 때문입니다. 하지만 뺄셈이

문제 개요이 글에서는 C++ 배열에서 서로 인접한 두 요소(연속된 쌍) 사이의 절대 차이를 구하는 방법을 알아봅니다. 배열에 n개의 요소가 있다면, 결과 배열에는 n-1개의 값이 저장됩니다.예를 들어 배열이 {8, 5, 4, 3}이라면 계산 과정은 다음과 같습니다.|8 - 5| = 3|5 - 4| = 1|4 - 3| = 1따라서 최종 결과 배열은 {3, 1, 1}이 됩니다.알고리즘pairDiff(arr, n)begin    res := 결과 값을 저장할 배열   &nbs

이 글에서는 배열에 포함된 짝수 인덱스 요소와 홀수 인덱스 요소의 절대 차이를 구하는 방법을 알아봅니다. 여기서 절대 차이란 두 값의 차가 음수로 나올 경우 절댓값을 취한다는 의미입니다.예를 들어 배열이 {1, 2, 3, 4, 5, 6, 7, 8, 9}라고 할 때, 인덱스는 0부터 시작하므로 짝수 인덱스(0, 2, 4, 6, 8)에 있는 요소는 1, 3, 5, 7, 9이고, 홀수 인덱스(1, 3, 5, 7)에 있는 요소는 2, 4, 6, 8입니다.짝수 인덱스 요소의 차이는 이전 계산 결과와 다음 요소를 비교하는 방식으로 누적됩니다.

이번 글에서는 복소수(Complex Number)에 적용할 수 있는 acos() 함수에 대해 알아보겠습니다. C++에서 복소수는 <complex> 헤더 파일을 포함하여 사용할 수 있으며, 이 헤더 안에는 복소수 전용 acos() 함수도 함께 정의되어 있습니다.일반적으로 사용하는 acos() 함수가 실수의 아크코사인(역코사인)을 계산한다면, 복소수 버전은 복소수의 역코사인 값을 반환합니다. 즉, 입력 매개변수로 복소수를 받고, 그 결과로 해당 복소수의 아크코사인을 복소수 형태로 출력합니다.복소수 acos() 함수의 기본 동

시작 시간과 종료 시간이 주어진 n개의 서로 다른 활동이 있을 때, 한 사람이 시간이 겹치지 않도록 수행할 수 있는 최대 개수의 활동을 찾아야 하는 문제를 활동 선택 문제(Activity Selection Problem)라고 합니다.이 문제는 그리디(Greedy, 탐욕) 알고리즘으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다. 매 단계마다 남은 활동 중 종료 시간이 가장 빠른 활동을 선택하되, 해당 활동의 시작 시간이 반드시 마지막으로 선택한 활동의 종료 시간보다 크거나 같아야 합니다. 일찍 끝나는 활동을 먼저

이 글에서는 주어진 숫자가 아담 수(Adam Number)인지 판별하는 C++ 프로그램을 작성하는 방법을 알아봅니다. 코드를 살펴보기 전에, 먼저 아담 수가 무엇인지 정확히 이해해 보겠습니다.아담 수란?어떤 수 n이 있을 때, n의 제곱과 n을 뒤집은 수의 제곱이 서로 뒤집힌 관계라면 그 수를 아담 수라고 합니다.예를 들어 숫자 13을 생각해 보겠습니다.13을 뒤집으면 31이 됩니다.13의 제곱은 169입니다.31의 제곱은 961입니다.169와 961은 서로 뒤집힌 관계입니다.따라서 13은 아담 수입니다. 같은 원리로 12는 제곱이

숫자들로 이루어진 배열이 있다고 가정해 봅시다. 우리는 배열 요소들의 합을 짝수로 만들기 위해 최소한 얼마의 숫자를 더해야 하는지 구해야 합니다. 단, 추가하는 숫자는 반드시 0보다 커야 한다는 조건이 있습니다.따라서 로직은 매우 간단합니다. 요소들의 합이 홀수라면 1을 더해서 짝수로 만들고, 합이 이미 짝수라면 조건(0보다 큰 수)을 만족하기 위해 2를 더해 짝수 상태를 유지합니다.알고리즘addMinNumber(arr)begin   s := 0   for each element

이 글에서는 문자열 형태로 주어진 n개의 이진수를 더하는 프로그램을 작성하는 방법을 알아보겠습니다. 가장 간단한 방법은 이진수 문자열을 10진수로 변환한 뒤 모두 더하고, 그 결과를 다시 이진수로 변환하는 것입니다. 하지만 여기서는 변환 과정 없이 덧셈을 직접 구현해 보겠습니다.먼저 두 개의 이진수 문자열을 더하는 헬퍼 함수를 하나 만듭니다. 이 함수는 서로 다른 n개의 이진수 문자열에 대해 총 n-1번 호출되며, 내부 동작 방식은 아래와 같습니다.알고리즘addTwoBinary(bin1, bin2)= 0 then,

이 글에서는 숫자 A에 N개의 자릿수를 추가해 새로운 수를 만드는 방법을 살펴봅니다. 핵심 조건은 자릿수를 추가하는 매 단계마다 결과 숫자가 다른 수 B로 나누어떨어져야 한다는 점입니다.예를 들어 기존 숫자에 4개의 자릿수를 더해 5자리 숫자를 만들고, 7로 나누어떨어지는지 검사한다고 가정해 봅시다. 시작 숫자가 8이라면 먼저 4를 붙여 84를 만듭니다. 84는 7로 나누어떨어지므로 조건을 충족합니다. 이후에는 0을 붙여도 7의 배수라는 성질이 유지됩니다(84 × 10 = 840 역시 7로 나누어떨어짐). 따라서 나누어떨어지는 수를

개요이 글에서는 두 수의 공약수 개수를 구하는 방법을 알아보겠습니다. 모든 공약수를 일일이 나열하는 대신, 개수만 효율적으로 세는 것이 핵심입니다. 예를 들어 12와 24의 공약수는 1, 2, 3, 4, 6, 12로 총 6개이므로 정답은 6이 됩니다.핵심 아이디어두 수의 공약수는 결국 두 수의 최대공약수(GCD)의 약수와 같습니다. 따라서 먼저 GCD를 구한 뒤, 그 GCD의 약수 개수를 세면 문제가 간단해집니다. 또한 약수를 셀 때 1부터 √GCD까지만 확인하면 되기 때문에 연산량을 크게 줄일 수 있습니다.알고리즘countComm

이번 글에서는 두 개 이상의 숫자에 대한 최대공약수(GCD, Greatest Common Divisor)를 구하는 방법을 알아보겠습니다. 두 숫자의 GCD를 구하는 것은 비교적 간단하지만, 세 개 이상의 숫자가 대상이 되면 GCD의 결합 법칙(associativity rule)을 활용해야 합니다.예를 들어 {w, x, y, z} 네 숫자의 GCD를 구한다고 가정해 봅시다. 이 경우 다음과 같은 단계로 계산이 진행됩니다.{w, x, y, z} → {gcd(w,x), y, z} → {gcd(gcd(w,x), y), z} → 최종적으로

이 문제의 목표는 X로 나누어 떨어지는 가장 작은 K자리 숫자를 찾는 것입니다. 이를 위해 먼저 공식 10^(k-1)을 사용하여 가장 작은 K자리 숫자를 구합니다. 그다음 해당 숫자가 X로 나누어 떨어지는지 확인하고, 나누어 떨어지지 않는 경우에는 아래 공식을 활용해 정확한 값을 계산할 수 있습니다.(min + X) − ((min + X) mod X)예를 들어, 29로 나누어 떨어지는 5자리 숫자를 찾는다고 가정해 보겠습니다. 가장 작은 5자리 숫자는 10000이지만, 10000은 29로 나누어 떨어지지 않습니다. 이때 위 공식을

암호 산술(Crypt-arithmetic) 문제는 문자에 숫자를 대입하여 올바른 산술 연산이 성립하도록 만드는 퍼즐입니다. 서로 다른 열 개 이하의 문자가 0부터 9까지의 숫자 값을 각각 하나씩 할당받아야 하며, 두 단어를 더한 결과가 세 번째 단어와 일치해야 합니다.예를 들어 BASE와 BALL이라는 두 단어가 주어지고, 그 합의 답으로 GAMES가 주어졌다고 가정해 봅시다. 각 문자에 적절한 숫자를 대입하면 BASE + BALL = GAMES라는 등식이 실제 숫자 연산으로 성립하게 됩니다.참고: 등장하는 서로 다른 문자는 최대