양의 정수로 이루어진 배열이 주어졌을 때, 배열 안의 두 정수로 만들 수 있는 쌍 중 GCD(최대공약수) 값이 가장 큰 쌍을 찾는 것이 이 글의 목표입니다. 예를 들어 A = {1, 2, 3, 4, 5}라면 결과는 2입니다. 쌍 (2, 4)의 GCD가 2이며, 그 외 모든 쌍의 GCD 값은 2보다 작기 때문입니다.문제 해결 접근 방법이 문제는 약수 카운트 배열(divisor count array)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.먼저 각 원소에 대해 1부터 √arr[i]까지의 수를 확인하며

문제 개요주어진 인덱스에 해당하는 N개의 피보나치 수에 대한 최대공약수(GCD)를 구하는 것이 이번 글의 목표입니다. 먼저 입력된 인덱스 중 최댓값을 확인하여 피보나치 수열을 생성해야 합니다. 피보나치 수열은 다음과 같은 형태를 가집니다.0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...인덱스는 0부터 시작하므로 0번째 인덱스의 값은 0입니다. 예를 들어 인덱스 {2, 3, 4, 5}에 해당하는 피보나치 수는 각각 {1, 2, 3, 5}이며, 이 수들의 GCD는 1입니다.핵심 원리: 피보나치 수의 GCD 성질이 문제는

문제 이해정렬되어 있던 배열이 어느 지점에서 회전된 형태, 즉 회전 정렬 배열(rotated sorted array)이 주어졌다고 가정해 봅시다. 해야 할 일은 이 배열을 원래의 정렬 상태로 되돌리기 위해 필요한 최소 회전 횟수를 구하는 것입니다. 단, 회전은 오른쪽 끝 요소를 왼쪽으로 옮기는 방향(오른쪽 → 왼쪽)으로 수행한다고 가정합니다.예를 들어 배열이 {15, 17, 1, 2, 6, 11}이라면, 두 번 회전했을 때 {1, 2, 6, 11, 15, 17}이 되어 완전히 정렬됩니다. 따라서 이 경우 정답은 2입니다.핵심 아이디

하한(lower bound)과 상한(upper bound)이 주어졌을 때, 다음 조건을 만족하는 비전이적(nontransitive) 삼중항 (x, y, z)을 찾는 문제를 생각해 보겠습니다.(x, y)는 서로소(coprime), 즉 최대공약수(GCD)가 1(y, z)도 서로소그러나 (x, z)는 서로소가 아님문제 이해하기예를 들어 하한이 2, 상한이 10이라면 후보 집합은 {2, 3, 4, 5, 6, 7, 8, 9, 10}입니다. 이 범위에서 가능한 삼중항 중 하나는 (4, 7, 8)입니다. (4, 7)과 (7, 8)은 각각 서로소

배열 A가 주어졌을 때, GCD(최대공약수) 연산을 사용하지 않고 모든 요소의 LCM(최소공배수)을 구해야 합니다. 예를 들어 배열이 {4, 6, 12, 24, 30}과 같다면, 최소공배수는 120이 됩니다. 알고리즘 개요 두 수 사이의 LCM은 비교적 간단하게 계산할 수 있습니다. 두 수 중 더 큰 값부터 시작하여, 그 값이 두 수 모두로 나누어떨어질 때까지 1씩 증가시키면 됩니다. 이를 의사 코드로 표현하면 다음과 같습니다. getLCM(a, b) − begin    if a > b, then

이번 글에서는 이진 탐색 트리(BST)에서 바닥(Floor)과 천장(Ceiling) 값을 찾는 방법을 살펴봅니다. 예를 들어, 가용 노드들을 BST 형태로 배치한 메모리 관리 시스템을 만든다고 가정해 봅시다. 입력된 요청에 가장 잘 맞는(best fit) 노드를 찾으려면 키 값보다 큰 데이터 중 가장 작은 값을 향해 트리를 내려가게 되는데, 이 탐색 과정에서 다음의 세 가지 경우가 발생합니다.천장(Ceiling) 값 탐색의 세 가지 경우루트가 키와 같은 경우: 루트 값이 곧 천장 값입니다.루트 데이터가 키보다 작은 경우: 천장 값은

양의 정수로 이루어진 배열 A[]가 있고, 모든 i에 대해 2 ≤ A[i] ≤ 106의 범위를 가진다고 가정해 봅시다. 이때 우리의 과제는 배열 안에 적어도 하나의 요소가 존재하여, 그 요소가 배열의 다른 모든 요소들과 서로소(coprime) 관계를 이루는지 확인하는 것입니다.예를 들어 배열이 {2, 8, 4, 10, 6, 7}이라고 해보겠습니다. 여기서 7은 배열의 다른 모든 요소와 서로소입니다. 7은 소수이고, 나머지 요소들은 모두 2를 소인수로 가지기 때문에 7과는 공약수가 없습니다.효율적인 접근 방법이 문제를 효율적으로 해결

프로그래밍에서 문자열이나 수식을 다룰 때 괄호가 올바르게 짝을 이루고 있는지 확인해야 하는 경우가 자주 발생합니다. 이번 글에서는 C++을 사용하여 표현식 내의 괄호가 균형 잡혀 있는지(balanced) 검사하는 방법을 알아보겠습니다.검사 대상이 되는 괄호는 소괄호 (), 중괄호 {}, 대괄호 [] 세 가지입니다. 예를 들어 다음과 같은 두 개의 문자열이 있다고 가정해 봅시다.()[(){()}] → 모든 괄호가 올바른 순서로 열리고 닫히므로 유효(valid)합니다.{[}] → 여는 괄호와 닫는 괄호의 짝이 서로 맞지 않으므로 유효하

이진 트리가 주어졌을 때, 아래 조건을 만족하면 해당 트리를 유효한(valid) 이진 트리라고 판단할 수 있습니다.모든 노드의 데이터 값은 왼쪽 자식과 오른쪽 자식 값의 합과 같아야 합니다.어느 한쪽에 자식 노드가 없다면, 그 값은 0으로 간주합니다.예를 들어 아래와 같은 트리는 위 속성을 만족하는 유효한 이진 트리입니다.접근 방법이 속성을 확인하는 특별한 트릭은 없으며, 트리를 재귀적으로 순회해야 합니다. 각 노드에서 현재 노드의 값이 두 자식 노드 값의 합과 일치하는지 검사하고, 모든 노드가 조건을 만족하면 true를, 하나라도

두 개의 배열이 있을 때, 각 배열의 요소를 왼쪽에서 오른쪽 순서대로 삽입하여 이진 탐색 트리(BST)를 만든다고 가정해 봅시다. 이때 두 배열이 동일한 BST를 형성하는지 확인해야 합니다. 단, 실제로 트리를 구축해서는 안 된다는 제약 조건이 있습니다.예를 들어 배열 {2, 4, 1, 3}과 {2, 1, 4, 3}이 있다면, 두 시퀀스 모두 같은 BST를 만들 수 있습니다.접근 방법BST의 기본 성질을 활용하면 됩니다. 왼쪽 서브트리의 모든 요소는 루트보다 작고, 오른쪽 서브트리의 모든 요소는 루트보다 큽니다.따라서 두 배열이 같

정렬된 배열이 주어졌을 때, 특정 숫자 x가 해당 배열의 과반수(majority) 요소인지 판별하는 문제를 살펴보겠습니다.여기서 과반수 요소란 배열 전체 길이 n의 절반, 즉 n/2번보다 많이 등장하는 요소를 의미합니다.문제 이해하기예를 들어 배열이 {1, 2, 3, 3, 3, 3, 6}이고 x = 3이라고 가정해 봅시다. 숫자 3은 총 4번 등장하고, 배열의 크기는 7이므로 4 > 7/2(=3.5)를 만족합니다. 따라서 3은 과반수 요소이며 결과는 true가 됩니다.만약 x = 6이라면 6은 한 번만 등장하므로 과반수 요소가

문제 개요하나의 문자열과 쿼리 집합 Q가 주어져 있다고 가정해 봅시다. 각 쿼리는 두 개의 정수 i와 j, 그리고 하나의 문자 c로 구성됩니다. 우리는 문자열에서 인덱스 i와 j에 위치한 문자들을 새로운 문자 c로 교체한 후, 그 문자열이 회문(palindrome)인지 아닌지를 판별해야 합니다.예를 들어 문자열이 AXCDCMP라고 해보겠습니다. 첫 번째 쿼리로 (1, 5, B)를 수행하면 문자열은 ABCDCBP가 됩니다. 이어서 두 번째 쿼리로 (0, 6, A)를 수행하면 문자열은 ABCDCBA가 되는데, 이 문자열은 앞에서 읽으나

2차원 배열이 주어졌을 때, 왼쪽 위 모서리에서 오른쪽 아래 모서리까지 도달할 수 있는 경로가 존재하는지 확인해야 합니다. 행렬은 0과 1로만 채워져 있으며, 0은 이동 가능한 열린 공간, 1은 막힌 구간(장애물)을 의미합니다. 단, 시작점인 왼쪽 위 칸은 항상 0이라고 가정합니다.문제 예시다음과 같은 5×5 행렬이 있다고 가정해 보겠습니다.0001010011000101000000100위 행렬에는 초록색으로 표시된 것처럼 여러 개의 유효한 경로가 존재합니다. 따라서 프로그램은 경로가 있으면 true, 없으면 false를 반환해야 합

이 글에서는 C++를 사용하여 주어진 행렬이 마방진(Magic Square)인지 판별하는 방법을 알아보겠습니다.마방진이란?마방진은 정사각형 행렬의 한 종류로, 각 행의 합, 각 열의 합, 그리고 두 대각선의 합이 모두 동일한 값이 되는 행렬을 말합니다.예를 들어 다음과 같은 3×3 행렬이 있다고 가정해 보겠습니다.618753294이 행렬은 마방진입니다. 실제로 각 행의 합(6+1+8, 7+5+3, 2+9+4), 각 열의 합(6+7+2, 1+5+9, 8+3+4), 그리고 두 대각선의 합(6+5+4, 8+5+2)을 계산해 보면 모두 1

문제 개요 배열 A가 주어졌을 때, 이 배열이 n개의 레벨(level)을 가진 BST(이진 탐색 트리)를 나타낼 수 있는지 확인해야 합니다. 트리를 구성할 때는 일반적인 BST의 규칙을 따릅니다. 즉, 어떤 값 k를 기준으로 k보다 큰 값은 오른쪽으로, k보다 작은 값은 왼쪽으로 이동하여 배치됩니다. 예시 {50, 20, 9, 25, 10}과 {50, 30, 20, 25, 10} 두 개의 리스트가 있다고 가정해 보겠습니다. 첫 번째 리스트는 유효하지 않지만, 두 번째 리스트는 유효합니다. 접근 방법 이 문제는 실제로 BST를

숫자로 이루어진 문자열이 주어졌을 때, 해당 숫자가 특정 진법 B에 유효한 값인지 확인해야 하는 경우가 있습니다. 예를 들어, 문자열이 101110이고 진법이 2라면 프로그램은 true를 반환합니다. 마찬가지로 문자열이 A8F이고 진법이 16이라면 역시 true를 반환하게 됩니다. 문제 해결 접근 방식 해결 방법은 매우 간단합니다. 문자열의 모든 문자가 주어진 진법에서 사용되는 기호의 범위 안에 있다면 true를 반환하고, 하나라도 범위를 벗어나는 문자가 있다면 false를 반환하면 됩니다. 검증 규칙 이 프로그램은 최대 16진법까

이번 글에서는 흥미로운 문제 하나를 살펴보겠습니다. 바로 주어진 숫자가 뒤죽박죽(Jumbled) 숫자인지 판별하는 방법입니다.여기서 뒤죽박죽 숫자란, 모든 자릿수에 대해 인접한 자릿수와의 차이가 최대 1 이하인 수를 의미합니다. 예를 들어 1223은 각 인접 자릿수의 차이가 1 이하이므로 뒤죽박죽 숫자이지만, 1256은 2와 5 사이의 차이가 3으로 1을 초과하므로 뒤죽박죽 숫자가 아닙니다.문제 해결 접근 방식이 문제를 해결하려면 숫자의 각 자릿수를 확인하면서, 인접한 자릿수와의 차이가 1보다 큰 경우가 있는지 검사해야 합니다.차이

이 글에서는 나눗셈(/)과 나머지(%) 연산자를 사용하지 않고 어떤 숫자가 5로 나누어 떨어지는지 확인하는 방법을 알아봅니다.가장 일반적인 방법은 num % 5 == 0인지 검사하는 것이지만, 여기서는 이 두 연산자를 쓰지 않는다는 조건이 있습니다. 대신 수학적 성질을 활용하면 훨씬 간단하게 문제를 해결할 수 있습니다.핵심 아이디어5의 배수에는 명확한 규칙이 있습니다. 바로 마지막 자릿수(일의 자리)가 반드시 0 또는 5라는 점입니다. 예를 들어 10, 15, 25, 100, 125처럼 5의 배수는 모두 이 규칙을 따릅니다.따라서

이 글에서는 C++을 사용하여 숫자가 회문(palindrome)인지 확인하는 방법을 살펴보겠습니다. 회문 수란 앞에서부터 읽으나 뒤에서부터 읽으나 동일한 숫자를 의미합니다. 예를 들어 12321은 거꾸로 읽어도 12321이므로 회문이지만, 12345는 뒤집으면 54321이 되기 때문에 회문이 아닙니다.핵심 로직은 매우 간단합니다. 주어진 숫자를 뒤집은 다음, 뒤집힌 숫자가 원래 숫자와 같은지 비교하면 됩니다. 두 값이 일치하면 회문이고, 그렇지 않으면 회문이 아닙니다. 그럼 알고리즘을 통해 자세히 살펴보겠습니다.알고리즘isPalin

프로그래밍 문제를 풀다 보면 주어진 숫자가 완전제곱수(perfect square)인지 확인해야 하는 경우가 자주 있습니다. 예를 들어 1024는 32 × 32로 표현되므로 완전제곱수지만, 1000은 어떤 정수의 제곱으로도 표현할 수 없으므로 완전제곱수가 아닙니다.보통은 sqrt()와 같은 제곱근 함수를 사용하면 간단하게 확인할 수 있지만, 이 글에서는 제곱근 연산 없이 완전제곱수 여부를 판별하는 방법을 다룹니다. 핵심 아이디어는 간단합니다. n이 완전제곱수라면 n = i × i를 만족하는 정수 i가 반드시 존재한다는 사실을 이용하는