이번 글에서는 하나의 자연수를 2의 0이 아닌 거듭제곱 두 개의 합으로 나타낼 수 있는지 확인하는 방법을 살펴보겠습니다. 다시 말해, 주어진 숫자 N을 2x + 2y(단, x, y > 0) 형태로 표현할 수 있는지 검사하는 문제입니다. 예를 들어 숫자 10은 23 + 21, 즉 8 + 2로 표현할 수 있으므로 조건을 만족합니다. 접근 방법 풀이 아이디어는 매우 단순하며, 크게 두 가지 경우로 나누어 생각할 수 있습니다. N이 짝수인 경우: 지수가 1 이상인 2의 거듭제곱들은 모두 짝수이므로, 그 합 역시 항상 짝수가 됩니다.

개요이 글에서는 어떤 숫자가 연속된 세 정수의 합으로 표현될 수 있는지 확인하는 방법을 알아보겠습니다. 예를 들어 숫자 27은 8 + 9 + 10처럼 연속된 세 정수의 합으로 나타낼 수 있습니다.문제 해결 접근 방법이 문제는 두 가지 방식으로 해결할 수 있습니다.1. 단순 탐색(Naïve) 방법첫 번째 방법은 가능한 모든 경우를 하나씩 검사하는 단순한 방식입니다. i + (i + 1) + (i + 2)의 값이 주어진 숫자와 같아지는 정수 i가 존재하는지 차례대로 확인합니다.2. 수학적 접근(효율적인 방법)훨씬 더 효율적인 방법은 숫

이번 글에서는 어떤 숫자의 이진 표현에서 설정된 비트(set bit, 1)와 설정되지 않은 비트(unset bit, 0)의 개수가 서로 같은지 확인하는 방법을 알아보겠습니다.예를 들어 숫자 12의 이진 표현은 1100입니다. 여기에는 1이 두 개, 0이 두 개 있으므로 두 종류의 비트 개수가 동일합니다.접근 방법알고리즘은 매우 간단합니다. 숫자의 각 비트를 하나씩 검사하면서, 해당 비트가 1이면 set_bit_count를 증가시키고, 0이면 unset_bit_count를 증가시킵니다. 모든 비트를 확인한 후 두 카운트가 같으면 tr

이 글에서는 어떤 수의 이진수 표현에 인접한 세트 비트(set bit, 즉 1)가 존재하는지 확인하는 방법을 알아봅니다. 예를 들어 숫자 12는 이진수로 1100이므로 연속된 두 개의 1을 가지고 있습니다.이를 확인하는 아이디어는 매우 간단합니다. 숫자를 오른쪽으로 1비트 시프트한 뒤, 원래 값과 비트 AND 연산을 수행합니다. 그 결과가 0이 아니라면 어딘가에 연속된 1이 반드시 존재한다는 의미입니다. 시프트를 하면 원래 인접해 있던 1들이 같은 자리에 겹치게 되므로, AND 연산 결과에 1이 남게 되는 원리입니다.예제 코드#in

이 글에서는 C++을 사용하여 어떤 숫자가 미스터리 넘버(Mystery Number)인지 확인하는 방법을 알아보겠습니다.미스터리 넘버란 두 개의 수의 합으로 표현할 수 있고, 그 두 수가 서로 자릿수를 뒤집은 관계(예: 29와 92)에 있는 숫자를 의미합니다. 예를 들어 121은 29 + 92 = 121이므로 미스터리 넘버입니다.확인 알고리즘미스터리 넘버를 확인하려면 다음 단계를 따릅니다.단계1부터 n/2까지의 모든 숫자 i에 대해 반복합니다.각 i에 대해 자릿수를 뒤집은 숫자 j를 계산합니다.i + j == n이면 n은 미스터리

이 글에서는 어떤 숫자가 다른 숫자의 거듭제곱인지 판별하는 방법을 알아보겠습니다. 예를 들어 125와 5라는 두 숫자가 주어졌을 때, 125가 5의 거듭제곱이면 참(true)을 반환해야 합니다. 실제로 125 = 53이므로 이 경우 결과는 참이 됩니다.알고리즘핵심 아이디어는 간단합니다. 밑(base)이 되는 숫자 x를 계속 곱해가면서 목표 값 y에 도달하는지 확인하는 것입니다.isRepresentPower(x, y): 시작 만약 x = 1이라면 y = 1이면 true 반환, 아니면 false 반환 pow

이번 글에서는 어떤 숫자가 피타고라스 소수(Pythagorean Prime)인지 판별하는 C++ 프로그램을 살펴보겠습니다. 로직을 자세히 다루기 전에, 먼저 피타고라스 소수가 무엇인지 이해하는 것이 중요합니다.피타고라스 소수란?피타고라스 소수는 4n + 1 형태로 표현할 수 있는 소수를 의미합니다. 흥미로운 점은 이런 소수들이 두 제곱수의 합(a² + b²)으로도 나타낼 수 있다는 것인데, 예를 들어 5 = 1² + 2², 13 = 2² + 3²처럼 표현됩니다. 이러한 성질 때문에 피타고라스 정리와 연관 지어 피타고라스 소수라고 부

이 글에서는 주어진 숫자가 완전 소수(Full Prime)인지 판별하는 방법을 알아보겠습니다. 완전 소수란 숫자 자체가 소수이면서, 그 숫자를 구성하는 모든 자릿수도 소수인 경우를 말합니다. 예를 들어 37은 37 자체가 소수이고 각 자릿수인 3과 7도 모두 소수이므로 완전 소수입니다. 반면 97은 숫자 자체는 소수지만 자릿수 중 9가 소수가 아니기 때문에 완전 소수가 아닙니다.효율적인 접근 방법가장 효율적인 방법은 다음 두 단계로 검사를 진행하는 것입니다.먼저, 숫자를 구성하는 각 자릿수 중 소수가 아닌 것이 있는지 확인합니다.

쿼턴 소수(Quartan Prime)란?쿼턴 소수는 네 번째 거듭제곱의 합, 즉 x⁴ + y⁴ 형태로 표현할 수 있는 소수를 말합니다. 이때 x와 y는 모두 0보다 커야 한다는 조건이 있습니다.쿼턴 소수 판별 원리주어진 숫자가 쿼턴 소수인지 확인하는 과정은 생각보다 간단합니다. 다음 두 단계만 거치면 됩니다.소수 여부 검사 — 먼저 해당 숫자가 소수(prime number)인지 확인합니다.나머지 연산 검사 — 소수라면 그 숫자를 16으로 나누었을 때 나머지가 1인지 검사합니다. 나머지가 1이면 쿼턴 소수입니다.정리에 따르면 홀수인

숫자 N과 진법 b가 주어졌을 때, N을 b진법으로 표현했을 때 맨 앞자리 숫자가 1인지 확인하는 프로그램을 만들어 보겠습니다. 예를 들어 숫자 6이 주어졌다면 이진수로는 110이므로 1로 시작하고, 4진법으로 표현하면 124 역시 마찬가지로 1로 시작합니다.접근 방식어떤 수 N이 b진법으로 표현되면 m+1자리 숫자 나열 bm bm-1 … b0이 됩니다. 이는 다음 등식을 의미합니다.bm·bm + bm-1·bm-1 + … + b0·b0 = N만약 맨 앞자리 숫자가 1이라

이 튜토리얼에서는 두 수(예: a와 b)가 다음 조건을 모두 만족하도록 만드는 프로그램을 다룹니다.a + b = N 이고 a × b = N수학적 접근 방법두 방정식에서 a를 소거하면 b와 N에 대한 이차방정식을 얻을 수 있습니다.b2 - bN + N = 0이 이차방정식은 두 개의 근을 가지며, 각각의 근이 곧 a와 b의 값이 됩니다. 판별식(determinant) 공식을 사용해 근을 구하면 다음과 같습니다.$a= \frac{N-\sqrt{N*N-4N}}{2} \\ b= \frac{N+\sqrt{N*N-4N}}{2}$C++ 예제 코드

개요이 글에서는 서로 다른 두 문자열을 비교했을 때 공통되지 않은(uncommon) 문자를 찾아내는 C++ 프로그램을 살펴보겠습니다.문자열은 본질적으로 문자(character)들의 배열입니다. 따라서 비교를 수행하려면 한 문자열의 각 문자를 순회하면서, 그 문자가 다른 문자열에도 존재하는지 동시에 확인하면 됩니다.첫 번째 문자열을 A, 두 번째 문자열을 B라고 가정해 보겠습니다. 이때 A에는 있지만 B에는 없는 문자들의 집합은 A − B로 표현할 수 있으며, 같은 방식으로 B − A도 구할 수 있습니다.이 두 결과를 합치면 다음과

개요이 글에서는 정렬되지 않은 두 개의 배열이 주어졌을 때, 두 배열의 합집합(union)과 교집합(intersection)을 구하는 C++ 프로그램을 살펴봅니다.두 배열을 각각 A와 B라고 하겠습니다. 두 배열의 합집합은 A ∪ B로 표현되며, 두 배열에 포함된 모든 원소를 담되 각 원소는 중복 없이 한 번만 나타나는 배열을 의미합니다.합집합을 구하는 방법은 다음과 같습니다. 먼저 별도의 배열을 만들어 첫 번째 배열의 모든 원소를 복사해 넣습니다. 그다음 두 번째 배열의 원소를 하나씩 순회하면서 해당 원소가 합집합 배열에 이미 존

이 글에서는 각 요소가 N보다 작거나 같으면서 아래 두 가지 조건을 동시에 만족하는 고유한 숫자 쌍을 찾는 C++ 프로그램에 대해 알아보겠습니다.두 수의 차이의 제곱이 그 두 수의 최소공배수(LCM)와 같아야 합니다.두 수의 최대공약수(HCF)가 연속된 두 자연수의 곱으로 표현될 수 있어야 합니다.접근 방법이 문제를 해결하는 가장 효율적인 방법은 연속된 두 자연수(1부터 시작)를 선택한 후, 그 두 수의 곱의 배수들을 구하는 것입니다. 그다음 배수들 중에서 하나의 쌍을 특정하기 위해, 쌍을 이루는 두 수가 첫 번째 조건을 만족하는지

이 글에서는 하나의 정수(예: X)가 서로 다른(unique) 자연수들의 n제곱의 합으로 표현될 수 있는 모든 방법의 개수를 구하는 프로그램을 다룹니다.예를 들어, X = 100이고 n = 2라고 가정해 보겠습니다.이 경우 100은 자연수 제곱의 합으로 다음과 같이 세 가지 방법으로 표현할 수 있습니다.100 = 102 100 = 62 + 82 100 = 12 + 32 + 42 + 52 + 72접근 방법: 재귀 활용이 문제는 재귀(recursion)를 사용하면 비교적 쉽게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.1부터

이 글에서는 주어진 선행 조건(종속성)을 바탕으로 모든 작업을 완료할 수 있는지 확인하는 C++ 프로그램을 살펴보겠습니다. 예를 들어 세 개의 작업이 있고, 선행 조건이 [[1, 0], [2, 1], [3, 2]]로 주어졌다고 가정해 보겠습니다. ([1, 0]은 작업 1을 수행하려면 먼저 작업 0을 완료해야 한다는 의미입니다.) 이 예제에서 작업 0은 선행 조건이 없으므로 가장 먼저 완료할 수 있습니다. 작업 0이 끝났으므로 이어서 작업 1을 완료할 수 있고, 같은 방식으로 작업 2와 3도 차례대로 완료할 수 있습니다. 따라서 이

이 글에서는 문자열 패턴 검색(Pattern Searching) 문제를 해결하기 위해 유한 오토마타(Finite Automata) 알고리즘을 활용하는 C++ 프로그램을 살펴보겠습니다.문제 조건은 다음과 같습니다. 길이 n의 텍스트 text[0...n-1]과 길이 m의 패턴 pattern[0...m-1]이 주어졌을 때, 텍스트 안에서 패턴이 등장하는 모든 위치(인덱스)를 찾아내야 합니다.유한 오토마타 패턴 검색의 동작 원리유한 오토마타 기반 접근 방식은 크게 두 단계로 이루어집니다.1. 전처리(Preprocessing) 단계: 패턴을

문제 개요이 글에서는 주어진 배열의 모든 요소로 나눈 나머지가 서로 동일해지는 정수 k를 찾는 프로그램을 다룹니다.예를 들어 다음과 같은 배열이 주어졌다고 가정해 보겠습니다.arr = {12, 22, 32}이 경우 조건을 만족하는 k 값은 1, 2, 5, 10입니다. 실제로 이 값들로 배열의 각 요소를 나누면 나머지가 모두 같아지는 것을 확인할 수 있습니다.접근 방법배열 안의 두 값 x와 y(x > y)를 생각해 봅시다. 두 값의 나머지가 같으려면 다음 식이 성립해야 합니다.(y + 차이) % k = y % k이 식을 정리하면

이 글에서는 대권 거리(Great Circle Distance) 공식을 활용해 사용자 위치에서 약 50km 이내에 있는 택시를 찾아내는 C++ 프로그램을 소개합니다. 문제 정의 택시 호출 앱을 개발할 때 핵심이 되는 기능은 바로 현재 위치에서 가까운 차량 찾기입니다. 여기서는 다음과 같은 상황을 가정합니다. 승객의 이름과 GPS 좌표(위도, 경도), 그리고 현재 배차 가능한 모든 택시의 좌표가 담긴 JSON 파일이 하나 주어집니다. 우리가 해야 할 일은 이 데이터를 분석하여 승객으로부터 50km 이내에 있는 택시만 골라내는 것입

이 글에서는 두 수열이 처음으로 만나는 지점, 즉 두 수열이 공통으로 가지는 첫 번째 값을 찾는 프로그램을 다룹니다.문제에서는 다섯 개의 변수 a, b, c, d, n이 주어집니다. 이 값들을 이용해 각각 n개의 항을 가지는 두 개의 등차수열을 만들어야 합니다.b, b+a, b+2a, …, b+(n-1)ad, d+c, d+2c, …, d+(n-1)c그런 다음, 이 두 수열이 공통으로 포함하는 첫 번째 값을 찾으면 됩니다.해결 접근 방법이 문제를 해결하려면 먼저 첫 번째 수열의 항들을 하나씩 생성합니다. 그리고 각 항에 대해 다음 두