문제 개요 세 개의 정수 A, B, C가 주어졌을 때, 다음 두 조건을 동시에 만족하는 가장 작은 정수 X를 구하는 것이 목표입니다. X는 C로 나누어떨어져야 합니다. 즉, X mod C = 0을 만족해야 합니다. X는 닫힌 구간 [A, B]에 포함되지 않아야 합니다. 예를 들어 A = 5, B = 10, C = 4라고 가정해 보겠습니다. 이때 정답은 X = 4입니다. 4는 4로 나누어떨어지면서 동시에 [5, 10] 범위에 속하지 않기 때문입니다. 해결 아이디어 이 문제는 간단한 논리만으로 O(1) 시간 안에 해결할 수 있습니

배열 A에 N개의 요소가 저장되어 있다고 가정해 보겠습니다. 우리가 구해야 할 값은 배열의 모든 요소에 대해 팩토리얼(계승)을 계산한 뒤, 그 값들의 최대공약수(GCD)입니다. 예를 들어 요소가 {3, 4, 8, 6}이라면 각각의 팩토리얼은 3! = 6, 4! = 24, 6! = 720, 8! = 40320이 되고, 이 넷의 GCD는 6입니다.핵심 아이디어: 최솟값의 팩토리얼이 곧 정답두 수의 GCD는 두 수를 모두 나누어 떨어지게 하는 가장 큰 수입니다. 여기에 중요한 수학적 성질이 하나 숨어 있습니다. 바로 n ≤ m일 때 n!

최대공약수(HCF, GCD)는 일반적으로 유클리드 호제법(Euclidean Algorithm)을 사용하면 매우 쉽게 계산할 수 있습니다. 하지만 이번 글에서는 유클리드 알고리즘도, 재귀 함수도 사용하지 않고 두 수의 최대공약수를 구하는 방법을 알아보겠습니다.예를 들어 16과 24라는 두 수가 주어졌을 때, 이 두 수의 최대공약수는 8입니다. 접근 방식 핵심 아이디어는 단순한 반복문 탐색입니다. 로직은 다음과 같습니다. 두 수 중 더 작은 값(min)을 구합니다. 만약 작은 값이 두 수를 모두 나누어 떨어뜨린다면, 그 값이 곧 최대

원의 중심 좌표와 반지름이 주어져 있고, 별도의 한 점의 좌표가 주어졌다고 가정해 보겠습니다. 이때 해당 점이 원의 내부에 속하는지 여부를 판별하는 것이 이 글의 목표입니다.문제 해결 접근법이 문제는 유클리드 거리 공식을 이용하면 간단하게 해결할 수 있습니다. 먼저 주어진 점으로부터 원의 중심까지의 거리를 계산합니다. 두 점 사이의 거리는 다음과 같은 공식으로 구할 수 있습니다.거리 = √((x − cx)² + (y − cy)²)여기서 (cx, cy)는 원의 중심 좌표, (x, y)는 주어진 점의 좌표입니다. 계산된 거리가 반지름

세 개의 변수 N, R, P가 있다고 가정해 보겠습니다. N과 R은 이항계수 NCR을 구하는 데 사용되며, P는 소수입니다. 우리의 목표는 NCR이 P로 나누어 떨어지는지 판별하는 것입니다. 예를 들어 N = 7, R = 2, P = 3이라면 7C2 = 21이고, 21은 3으로 나누어 떨어지므로 결과는 참(true)이 됩니다.NCR은 다음과 같이 정의됩니다.NCR = N! / (R! × (N − R)!)접근 방법: 르장드르 공식(Legendres Formula)이 문제를 효율적으로 해결하려면 르장드르 공식을 활용할 수 있습니다. 르

C++에서 유리수의 최소공배수(LCM) 구하기 이 글에서는 여러 개의 유리수가 주어졌을 때 그 최소공배수(LCM)를 구하는 방법을 알아봅니다. 예를 들어 유리수 목록이 {2/7, 3/14, 5/3}과 같다면, 이들의 LCM은 30/1이 됩니다. 유리수 LCM의 기본 원리 정수와 달리 유리수의 LCM은 분자와 분모를 각각 따로 처리해야 한다는 점이 특징입니다. 핵심 아이디어는 다음과 같습니다. 모든 분자의 LCM(최소공배수)을 구합니다. 모든 분모의 GCD(최대공약수)를 구합니다. 분자의 LCM을 분모의 GCD로 나누면 유리수 전체

이 글에서는 드래곤 커브(Dragon Curve) 수열의 n번째 항을 구하는 C++ 프로그램을 살펴보겠습니다.드래곤 커브 수열은 무한히 이어지는 이진수 수열입니다. 수열은 1로 시작하며, 각 단계마다 이전 항의 각 원소를 차례대로 살펴보면서 그 뒤에 1과 0을 번갈아 추가하고, 맨 앞에는 항상 1을 붙여 다음 항을 완성합니다.제1항 : 1제2항 : 110제3항 : 1101100제4항 : 110110011100100생성 과정을 조금 더 자세히 보면, 먼저 결과 문자열을 1로 초기화한 뒤 이전 항의 문자를 하나씩 붙이고, 그때마다 0과

문제 개요배열 A가 하나 주어졌을 때, 각 요소의 서퍼서(surpasser) 개수를 구하는 것이 목표입니다. 서퍼서란 현재 요소보다 오른쪽에 위치하면서 값이 더 큰 원소들을 의미합니다.예를 들어 A = {2, 7, 5, 3, 0, 8, 1}이라면 각 요소의 서퍼서 개수는 {4, 1, 1, 1, 2, 0, 0}이 됩니다. 첫 번째 요소인 2의 오른쪽에는 7, 5, 3, 8처럼 2보다 큰 숫자가 네 개 있으므로 서퍼서는 4개이며, 나머지 요소들도 같은 방식으로 계산됩니다.접근 방법풀이 방법은 매우 간단합니다. 두 개의 중첩 반복문을 사

두 수의 곱은 항상 그 수들의 최소공배수(LCM)와 최대공약수(GCD/HCF)의 곱과 같다는 잘 알려진 수학적 성질이 있습니다. 이 성질을 활용하면 한 수와 두 수의 LCM, HCF 값만 알고 있어도 나머지 수를 손쉽게 계산할 수 있습니다.예를 들어, A = 5이고 LCM이 25, HCF가 4라고 가정해 보겠습니다. 아래 공식에 따르면 다른 수는 20이 됩니다.수학적 원리두 수 A와 B에 대해 다음 관계식이 항상 성립합니다.$$A \times B = LCM \times HCF$$이 식을 B에 대해 정리하면 다음과 같습니다.$$B =

문제 개요세 가지 색상(G, B, Y)으로 이루어진 문자열이 주어졌을 때, 아래의 관계식을 이용해 최종적으로 얻어지는 색상을 구하는 문제입니다.B * G = YY * B = GG * Y = B예를 들어 문자열이 GBYGB라면 결과는 B가 되고, BYB라면 결과는 Y가 됩니다.접근 방법풀이 방법은 매우 간단합니다. 문자열의 첫 번째 문자를 초기 색상으로 설정한 뒤, 나머지 문자들을 순서대로 확인하며 현재 색상과 비교합니다. 두 색상이 서로 다르다면 위의 관계식에 따라 새로운 색상을 결정하고, 같다면 기존 색상을 그대로 유지합니다. 모

문제 개요두 숫자 a와 b의 합(sum)과 최대공약수(GCD)가 주어졌을 때, 해당 조건을 동시에 만족하는 두 숫자를 찾는 문제입니다. 만약 그러한 숫자 쌍이 존재하지 않는다면 -1을 반환해야 합니다.예를 들어 합이 6이고 GCD가 2라고 가정해 보겠습니다. 이때 정답은 4와 2입니다. 실제로 4 + 2 = 6이고, gcd(4, 2) = 2이므로 두 조건을 모두 충족합니다.접근 방법GCD 값이 이미 주어져 있으므로, 두 숫자는 반드시 그 GCD의 배수여야 한다는 점을 활용합니다. 구체적인 풀이 단계는 다음과 같습니다.첫 번째 숫자를

두 수 A와 B를 곱한 결과를 구하고자 할 때, 그 결과값이 64비트 정수(long long)의 표현 범위를 초과하는지, 즉 오버플로(overflow)가 발생하는지 반드시 확인해야 합니다.예를 들어 100 × 200 = 20,000은 64비트 정수 범위 안에 있으므로 문제가 없지만, 10,000,000,000 × (-10,000,000,000)처럼 매우 큰 수를 곱하면 결과가 범위를 벗어나 오버플로가 발생합니다.오버플로 확인 절차곱셈 결과의 오버플로 여부는 다음 단계를 통해 판별할 수 있습니다.두 수 중 하나라도 0이면 → 곱셈 결

마법 수(Magic Number)란 무엇인가?이번 글에서는 어떤 숫자가 마법 수(Magic Number)인지 판별하는 프로그램을 살펴보겠습니다. 마법 수란 각 자릿수의 합을 한 자리 숫자가 될 때까지 반복해서 더했을 때 최종 결과가 1이 되는 수를 말합니다.예를 들어 숫자 50311을 살펴보겠습니다.5 + 0 + 3 + 1 + 1 = 101 + 0 = 1최종적으로 1이 되므로 50311은 마법 수입니다.판별 방법어떤 수가 마법 수인지 확인하려면 다음 과정을 따릅니다.1. 숫자의 모든 자릿수를 더한다.2. 그 합이 두 자리 이상이면,

이 글에서는 어떤 숫자가 두 소수 사이에 끼워져(sandwiched) 있는지 판별하는 방법을 알아봅니다. 어떤 수 n이 소수 사이에 끼워져 있다는 것은, n 바로 아래의 수(n-1)와 n 바로 위의 수(n+1)가 모두 소수일 때를 의미합니다.해결 접근 방식판별 로직은 매우 간단합니다. 주어진 수 n에 대해 다음 두 가지만 확인하면 됩니다.n - 1이 소수인지 검사하고, n + 1이 소수인지 검사합니다. 두 조건이 모두 참이라면 해당 숫자는 두 소수 사이에 끼워져 있는 것입니다. 소수 판별은 2부터 n/2까지의 수로 나누어 나머지가

세 개의 숫자 a, b, c가 주어졌을 때, 각 숫자에서 0을 모두 제거한 후에도 a + b = c가 성립하는지 확인해야 합니다. 예를 들어 a = 102, b = 130, c = 2005라고 가정해 보겠습니다. 각 숫자에서 0을 제거하면 a + b = c는 (12 + 13 = 25)가 되므로 이 식은 참이 됩니다.문제를 해결하는 접근 방식은 매우 간단합니다. 먼저 숫자에서 모든 0을 제거하는 함수를 작성하고, 그 변환된 값들을 사용하여 a + b = c가 여전히 성립하는지 검사하면 됩니다.알고리즘 동작 원리deleteZeros 함

이진 문자열(binary string)이 주어졌을 때, 문자열 안에 연속으로 같은 문자가 존재하는지 확인하는 것이 이번 문제의 목표입니다. 연속된 동일 문자가 있다면 그 문자열은 유효하지 않고(invalid), 없다면 유효한(valid) 문자열로 판단합니다.예를 들어 101010처럼 0과 1이 번갈아 나타나는 문자열은 유효하지만, 10111010처럼 11이 연속으로 등장하는 문자열은 유효하지 않습니다.해결 접근 방식이 문제는 매우 간단하게 해결할 수 있습니다. 문자열을 왼쪽부터 오른쪽까지 한 번 순회하면서, 인접한 두 문자가 서로

문제 개요두 개의 원, 즉 각각의 중심 좌표와 반지름 값이 주어졌을 때, 한 원이 다른 원 안에 들어가는지 확인해야 합니다. 이때 가능한 경우는 세 가지입니다.첫 번째 경우: 작은 원이 큰 원 안에 완전히 들어가 있지만 서로 닿지 않는 경우입니다. 이때 두 중심 사이의 거리와 작은 원의 반지름을 더한 값이 큰 원의 반지름보다 작기 때문에, 작은 원은 큰 원의 내부에 온전히 위치하게 됩니다.두 번째 경우: 작은 원이 큰 원 안에 들어가 있으면서 동시에 큰 원의 둘레(원주)에 닿아 있는 경우입니다.세 번째 경우: 작은 원의 일부만 큰

n개의 요소를 가진 배열 A가 주어졌을 때, 이 배열이 쌍 단위로 정렬(pairwise sorted)되어 있는지 확인해야 합니다. 예를 들어 배열이 {8, 10, 18, 20, 5, 15}라고 가정해 보겠습니다. 각 쌍인 (8, 10), (18, 20), (5, 15)가 모두 오름차순으로 정렬되어 있으므로, 이 배열은 쌍 단위로 정렬된 것입니다. 만약 배열의 요소 개수가 홀수라면 마지막 요소는 짝이 없으므로 검사에서 제외됩니다.접근 방법접근 방식은 매우 간단합니다. 인덱스 i를 0부터 시작하여 2씩 증가시키면서 다음을 반복합니다.i

이번 글에서는 C++를 사용하여 주어진 행렬이 희소 행렬(Sparse Matrix)인지 판별하는 방법을 알아보겠습니다.희소 행렬이란?희소 행렬은 행렬 내 대부분의 요소가 0으로 채워져 있는 행렬을 의미합니다. 일반적으로 전체 요소의 3분의 2(2/3) 이상이 0일 경우 해당 행렬을 희소 행렬로 정의합니다. 희소 행렬은 메모리 절약과 연산 최적화를 위해 특수한 저장 기법으로 다뤄지는 경우가 많습니다.다음은 희소 행렬의 예시입니다.{0, 2, 0, 0, 0} {8, 0, 0, 0, 0} {0, 3, 0, 0, 0} {0, 9, 0, 3

이번 글에서는 주어진 숫자가 희소 수(Sparse Number)인지 아닌지 판별하는 방법을 알아보겠습니다.희소 수란 무엇인가?희소 수는 숫자의 이진수 표현에서 연속된 두 개 이상의 1이 존재하지 않는 숫자를 의미합니다.예를 들어 숫자 72의 이진수 표현은 01001000입니다. 이 표현을 살펴보면 연속해서 나타나는 1이 전혀 없으므로, 72는 희소 수입니다.판별 원리숫자가 희소 수인지 확인하는 방법은 매우 간단하며 비트 연산만으로 해결할 수 있습니다.주어진 숫자를 n이라고 합니다.n을 오른쪽으로 1비트 시프트한 값(n >>