이 글에서는 스턴의 이원 수열(Sterns Diatomic Series)에서 n번째 항을 구하는 방법을 알아봅니다. 이 수열은 다음과 같이 진행됩니다.0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, ...이 수열은 퓨스크(fusc) 함수라고도 불리며, 각 항은 다음과 같은 점화식으로 정의할 수 있습니다.점화식 정의n이 짝수일 때: p(n) = p(n / 2)n이 홀수일 때: p(n) = p((n − 1) / 2) + p((n + 1) / 2)기저 사례: p(0) = 0, p(1) = 1동적 계획

개요이 튜토리얼에서는 C++을 사용하여 특정 숫자 패턴을 출력하는 프로그램을 작성하는 방법을 알아봅니다.목표는 코드에서 반복문(loop) 구조를 활용해 아래와 같은 피라미드 형태의 숫자 패턴을 화면에 출력하는 것입니다. 1 232 34543 4567654 567898765패턴 분석패턴을 자세히 살펴보면 다음과 같은 규칙을 발견할 수 있습니다.총 5개의 행(row)으로 구성되어 있으며, 각 행은 왼쪽에 공백이 채워져 피라미드 모양을 이룹니다.각 행의 가장 왼쪽 숫자는 해당 행의 번호와 같습니다. 즉, 1번째 행은 1부

곡선 y = x(A − x)가 주어져 있고, 이 곡선 위의 특정 점 (x, y)에서 법선(normal)의 방정식을 구해야 한다고 가정해 봅시다. 여기서 A는 정수이며, x와 y 역시 정수입니다.법선(Normal)이란?법선은 곡선 위의 한 점에서 해당 점을 지나는 접선에 수직인 직선을 의미합니다. 접선의 기울기를 m이라 할 때, 법선의 기울기는 −1/m이 됩니다. 따라서 법선을 구하려면 먼저 접선의 기울기, 즉 곡선의 미분값을 알아야 합니다.풀이 접근 방식이 문제는 다음 세 단계로 해결할 수 있습니다.점 검증: 주어진 점 (x, y)

이 튜토리얼에서는 C++를 사용하여 주어진 크기의 사각형 패턴을 콘솔에 출력하는 프로그램을 다룹니다.사각형의 높이(height)와 너비(width)가 입력으로 주어지면, @ 문자를 활용해 해당 크기만큼의 테두리 형태 사각형을 화면에 그려내는 것이 목표입니다. 내부는 공백으로 채워 속이 빈 사각형 모양이 되도록 구현합니다.구현 아이디어핵심 로직은 이중 반복문을 사용하는 것입니다. 바깥쪽 반복문은 행(row)을 순회하고, 안쪽 반복문은 열(column)을 순회합니다.이때 다음 조건 중 하나라도 만족하는 위치에는 @ 문자를 출력합니다.첫

이 튜토리얼에서는 C++을 사용하여 주어진 범위 안에 있는 모든 회문(Palindrome)을 찾아 출력하는 프로그램을 다룹니다.회문이란?회문(Palindrome)은 앞에서부터 읽으나 뒤에서부터 읽으나 같은 숫자나 문자열을 의미합니다. 예를 들어 121, 1331, 99 같은 숫자는 거꾸로 읽어도 동일하기 때문에 회문에 해당합니다.문제 정의프로그램은 최솟값(min)과 최댓값(max)으로 이루어진 수학적 범위를 입력으로 받습니다. 우리가 해야 할 작업은 해당 범위 내에 존재하는 모든 회문을 찾아 순서대로 화면에 출력하는 것입니다.알고리

개요n개의 원소로 이루어진 배열 A가 있다고 가정해 보겠습니다. 우리가 해야 할 일은 배열의 모든 숫자를 곱한 뒤, 그 결과를 n으로 나눴을 때의 나머지를 구하는 것입니다.예를 들어 A = [100, 10, 5, 25, 35, 14]이고 n = 11이라면, 출력값은 9입니다. 즉, 100 * 10 * 5 * 25 * 35 * 14 mod 11 = 9가 되는 것입니다.접근 방법배열의 모든 값을 먼저 곱하면 수가 기하급수적으로 커져 정수 오버플로우(overflow)가 발생할 수 있습니다. 따라서 다음과 같은 순서로 계산해야 합니다.각

이 튜토리얼에서는 C++을 사용하여 주어진 문자열의 모든 부분 문자열(substring)을 출력하는 프로그램을 살펴보겠습니다.여기서는 하나의 문자열 또는 문자 배열이 입력으로 주어지며, 우리의 목표는 해당 문자열에서 만들 수 있는 모든 부분 문자열을 순서대로 출력하는 것입니다.접근 방법모든 부분 문자열을 구하기 위해 세 개의 중첩 반복문을 사용합니다.바깥쪽 루프(len): 출력할 부분 문자열의 길이를 1부터 n까지 결정합니다.중간 루프(i): 각 길이에 대해 부분 문자열의 시작 인덱스를 지정합니다.안쪽 루프(k): 시작 인덱스 i부

숫자 n이 주어졌을 때, n!(팩토리얼)의 각 자릿수를 모두 더한 값을 구하는 것이 이 글의 목표입니다. 예를 들어 n = 5라면 5! = 120이므로, 자릿수의 합은 1 + 2 + 0 = 3이 됩니다.문제 접근 방법팩토리얼은 n이 조금만 커져도 기본 정수형(int, long long)의 표현 범위를 훌쩍 넘어섭니다. 따라서 일반적인 자료형으로는 계산 자체가 불가능하며, 큰 수 곱셈을 직접 구현해야 합니다.여기서는 벡터(vector)를 활용합니다. 벡터의 각 원소에 팩토리얼 결과의 한 자릿수씩을 저장하고, 1부터 n까지의 수를 차례

개요이 튜토리얼에서는 주어진 숫자보다 작은 수 중에서 3과 5로 모두 나누어 떨어지는 모든 숫자를 출력하는 C++ 프로그램을 살펴봅니다.숫자 N이 주어졌을 때, 목표는 N보다 작은 수 중에서 3과 5로 동시에 나누어 떨어지는 숫자를 모두 찾아 출력하는 것입니다.접근 방법가장 간단한 방법은 0부터 N-1까지 모든 숫자를 하나씩 검사하는 것입니다. 각 숫자에 대해 나머지 연산자(%)를 사용하여 해당 숫자가 3과 5로 나누어 떨어지는지 확인하고, 두 조건을 모두 만족하는 숫자만 출력하면 됩니다.참고로 3과 5로 모두 나누어 떨어지는 수는

n개의 요소를 가진 배열 A가 있다고 가정해 보겠습니다. 이때 우리가 구해야 할 값은 배열의 모든 부분 집합(subset)의 합들을 다시 한 번 모두 더한 총합입니다.예를 들어 배열이 A = [5, 6, 8]이라면, 만들 수 있는 부분 집합과 각각의 합은 다음과 같습니다.부분 집합합5566885, 6116, 8145, 8135, 6, 819총합76핵심 아이디어: 각 원소의 등장 횟수배열의 원소 개수가 n개일 때, 만들 수 있는 부분 집합의 개수는 공집합을 포함하여 2n개입니다. 여기서 중요한 관찰은 다음과 같습니다.모든 부분 집합을

문제 개요 곡선 y = x(A − x)가 주어졌을 때, 이 곡선 위의 특정 점 (x, y)에서의 접선 방정식을 구하는 것이 목표입니다. 여기서 A는 정수이며, 좌표 x와 y 역시 모두 정수입니다. 풀이 접근 1단계: 점이 곡선 위에 있는지 확인 접선은 곡선 위의 점에서만 정의되므로, 먼저 주어진 점 (x, y)가 곡선의 방정식 y = Ax − x²를 만족하는지 검사해야 합니다. 만족하지 않는다면 해당 점에서의 접선은 존재하지 않습니다. 2단계: 미분으로 기울기 구하기 곡선 y = x(A − x)를 x에 대해 미분하면 다음과 같습니다

개요이 튜토리얼에서는 C++을 사용하여 역피라미드(Inverse Pyramid) 모양의 알파벳 문자 패턴을 출력하는 프로그램을 살펴봅니다.역피라미드 패턴은 위에서 아래로 갈수록 문자의 개수가 하나씩 줄어들고, 각 행마다 왼쪽 공백이 늘어나면서 뒤집힌 피라미드 형태를 이루는 패턴입니다. 행의 개수 n이 주어지면, 첫 번째 행에는 A부터 시작하는 알파벳이 정방향과 역방향으로 나란히 배치되고, 그다음 행부터는 양쪽 끝 글자가 하나씩 제거되며 대칭적인 삼각형 모양이 완성됩니다.예를 들어 n = 5일 때, 첫 행은 A B C D E E D

이등변 삼각형은 두 변의 길이가 같은 삼각형입니다. 이번 글에서는 이등변 삼각형의 세 변 정보가 주어졌을 때, C++ 코드를 사용해 높이(고도)와 넓이를 계산하는 방법을 알아보겠습니다.예를 들어, 삼각형의 세 변이 각각 2, 2, 3이라고 가정해 보겠습니다. 이 경우 높이는 약 1.32, 넓이는 약 1.98이 됩니다.계산 공식이등변 삼각형의 높이(h)는 다음 공식으로 구할 수 있습니다.높이(h) = √(a² − b²/4)여기서 a는 같은 길이를 가진 두 변 중 하나의 길이, b는 밑변의 길이입니다. 높이를 구한 후에는 일반적인 삼각

문제 개요 이진 트리가 하나 주어져 있고, 각 리프(잎) 노드는 서로 다른 깊이의 레벨에 위치한다고 가정해 보겠습니다. 여기에 특정 노드를 가리키는 포인터가 추가로 주어지는데, 우리가 구해야 할 것은 바로 그 노드로부터 가장 가까운 리프 노드까지의 거리입니다.아래와 같은 트리를 예로 들어 살펴보겠습니다. 이 트리에서 리프 노드는 2, -2, 6 세 개입니다. 만약 포인터가 노드 -5를 가리키고 있다면, -5에서 가장 가까운 리프 노드는 거리 1만큼 떨어진 곳에 위치합니다. 해결 접근 방법 이 문제는 크게 두 단계로 나누어 해결할

문제 개요두 개의 단일 연결 리스트(singly linked list)가 주어졌을 때, 두 리스트에 공통으로 존재하는 노드의 총 개수를 구하는 것이 목표입니다. 예를 들어, 첫 번째 리스트가 [15, 16, 10, 9, 7, 17]이고 두 번째 리스트가 [15, 16, 40, 6, 9]라면, 값이 15, 16, 9인 노드가 양쪽 모두에 존재하므로 공통 노드는 총 3개입니다.접근 방법두 개의 중첩 반복문(nested loop)을 사용하여 이 문제를 해결할 수 있습니다.첫 번째 리스트를 처음부터 끝까지 순회하면서 각 노드를 하나씩 선택

문제 개요반지름 r이 주어졌을 때, 해당 원의 지름(diameter), 즉 원 안에서 가장 긴 현(chord)을 구하는 것이 목표입니다. 기하학적으로 지름은 원의 중심을 지나는 현으로, 원에 그릴 수 있는 모든 현 중 가장 길기 때문에 최장 현과 지름은 본질적으로 같은 값입니다.예를 들어 반지름이 9라면 지름은 18이 됩니다. 계산 방식은 매우 단순합니다. 아래 공식처럼 반지름에 2를 곱하기만 하면 됩니다.지름 = 2 × 반지름 (2r)C++ 구현 예제다음 코드는 반지름을 매개변수로 받아 지름을 반환하는 함수 getDiameter(

문제 개요배열 A와 두 개의 정수 K, M이 주어졌을 때, 배열 A를 자기 자신에게 M번 이어붙인 결과에서 K번째 최솟값을 찾는 것이 이 글의 목표입니다.예를 들어 배열이 A = [3, 1, 2], K = 4, M = 3이라고 가정해 보겠습니다. 배열을 3번 이어붙이면 [3, 1, 2, 3, 1, 2, 3, 1, 2]가 되고, 이 배열에서 4번째로 작은 요소는 2입니다.접근 방법배열을 실제로 M번 복사해 붙이면 불필요한 메모리와 시간이 낭비됩니다. 하지만 각 요소가 정확히 M번씩 반복된다는 점을 활용하면 훨씬 간단하게 해결할 수 있

두 정수 A와 B가 주어지고 B ≥ A일 때, B!/A! 연산 결과의 마지막 자릿수를 구하는 문제를 살펴보겠습니다.예를 들어 A = 2, B = 4인 경우를 생각해 봅시다. 2! = 2이고 4! = 24이므로, 24 ÷ 2 = 12가 됩니다. 따라서 마지막 자릿수는 2입니다.해결 아이디어팩토리얼 값의 마지막 자릿수는 항상 {0, 1, 2, 4, 6} 중 하나라는 성질을 이용하면 다음과 같은 단계로 문제를 효율적으로 해결할 수 있습니다.A와 B의 차이(diff)를 구합니다.차이가 5 이상이면, 그 범위 안에 반드시 5의 배수가 포함되

문제 개요다음과 같은 규칙을 따르는 수열 f가 있다고 가정해 보겠습니다.f[i] = f[i – 1] – f[i – 2]첫 번째 항은 f[0] = X, 두 번째 항은 f[1] = Y로 주어지며, 목표는 이 수열의 N번째 항을 구하는 것입니다. 예를 들어 X = 2, Y = 3, N = 3이라면 결과값은 -2가 됩니다.핵심 아이디어: 수열의 주기성이 수열을 자세히 관찰해 보면 흥미로운 패턴을 발견할 수 있습니다. 바로 여섯 개의 항을 주기로 수열이 반복된다는 점입니다.X = 2, Y = 3일 때 앞의 여섯 항을 직접 계산해 보면 다음과

크기가 각각 n과 m인 두 개의 배열 A와 B가 있다고 가정해 봅시다. 이때 우리의 목표는 배열 A에서 배열 B의 모든 요소를 포함하면서 길이가 가장 짧은 부분 배열(subarray)을 찾는 것입니다. 단, B의 요소들은 A 안에서 연속적으로 존재하지 않아도 되지만, 반드시 동일한 순서를 유지해야 합니다.예를 들어 A = [2, 2, 4, 5, 8, 9], B = [2, 5, 9]라고 할 때, 정답은 5입니다. A에서 가장 짧은 부분 배열은 [2, 4, 5, 8, 9]이며, 여기에는 B의 요소인 2, 5, 9가 모두 같은 순서로 포