이 튜토리얼에서는 주어진 조건을 만족하는 N자리 숫자의 개수를 구하는 프로그램을 C++로 작성하는 방법을 알아봅니다.문제 이해하기하나의 정수 N이 주어졌을 때, 다음 조건을 만족하는 N자리 숫자가 몇 개인지 구하는 것이 우리의 과제입니다.숫자 + 뒤집은 숫자(Reverse) = 10N − 1여기서 10N − 1은 N개의 9로 이루어진 수를 의미합니다. 예를 들어 N이 4라면, 어떤 4자리 수와 그 수를 거꾸로 뒤집은 수를 더했을 때 9999가 되어야 한다는 뜻입니다.접근 방법두 수의 합이 모든 자릿수가 9가 되려면 덧셈 과정에서 받

이 튜토리얼에서는 그래프에서 두 정점 사이의 경로 개수를 구하는 프로그램을 만들어 보겠습니다. 방향 그래프(directed graph)가 주어지며, 우리가 해야 할 일은 주어진 두 정점 사이에 존재할 수 있는 모든 경로의 개수를 세는 것입니다. 문제 접근 방법 이 문제는 깊이 우선 탐색(DFS)과 백트래킹(backtracking) 기법을 활용하면 효과적으로 해결할 수 있습니다. 시작 정점에서 출발해 인접한 정점들을 하나씩 방문하다가 도착 정점에 도달할 때마다 경로 개수를 1씩 증가시키고, 한 정점에 대한 탐색이 끝나면 방문 표시를

이 튜토리얼에서는 m×n 크기의 행렬에서 왼쪽 상단 칸부터 오른쪽 하단 칸까지 이동할 수 있는 경로의 총 개수를 구하는 프로그램을 살펴봅니다. 여기서는 각 단계마다 오른쪽 또는 아래쪽으로 한 칸씩만 이동할 수 있다고 가정합니다. 이 조건에서 시작점에서 끝점까지 도달할 수 있는 모든 가능한 경로의 수를 계산하는 것이 우리의 과제입니다. 접근 방식 가장 직관적인 방법은 재귀를 활용하는 것입니다. 현재 위치에서 끝점까지 도달할 수 있는 경로의 수는 다음 두 경우의 합과 같습니다. 아래쪽 칸에서 출발하여 끝점에 도달하는 경로의 수 오른

이 튜토리얼에서는 변형 나이트(Modified Knight)가 도달할 수 있는 위치의 개수를 구하는 C++ 프로그램을 다룹니다.8×8 크기의 체스판과 시작 위치, 그리고 이동 횟수(steps)가 주어졌을 때, 정확히 주어진 횟수만큼 이동한 후 변형 나이트가 도달할 수 있는 서로 다른 칸의 개수를 계산하는 것이 목표입니다.변형 나이트란?일반적인 체스 나이트는 8가지 방향으로만 움직일 수 있지만, 변형 나이트는 여기에 대각선으로 인접한 칸으로의 이동까지 포함해 총 12가지 방향으로 이동할 수 있습니다. 즉, 기존 나이트의 L자 움직임에

이 글에서는 C++에서 0으로 나누기(Divide by Zero) 예외를 처리하는 세 가지 방법을 소개합니다.수학에서 어떤 수를 0으로 나누는 것은 정의되지 않은 연산입니다. 따라서 프로그램을 작성할 때 이러한 상황을 적절히 처리하지 않으면 런타임 오류가 발생하거나 프로그램이 비정상적으로 종료되어 사용자에게 불편을 줄 수 있습니다. C++의 예외 처리 메커니즘인 try, catch, throw를 활용하면 이러한 문제를 안전하게 방지할 수 있습니다.1. runtime_error 클래스 활용가장 간단한 방법은 C++ 표준 라이브러리(&

이 튜토리얼에서는 곱이 K보다 작은 부분 수열(subsequence)의 개수를 구하는 프로그램을 C++로 작성해 보겠습니다.문제 정의음이 아닌 정수로 구성된 배열과 하나의 값 k가 주어집니다. 우리의 목표는 배열에서 만들 수 있는 모든 부분 수열 중, 각 원소들의 곱이 k보다 작은 부분 수열의 개수를 세는 것입니다.예를 들어 배열이 [1, 2, 3, 4]이고 k = 10이라면, 곱이 10 미만인 부분 수열은 총 11개가 존재합니다.접근 방법: 동적 계획법(DP)모든 부분 수열을 일일이 생성하면 지수 시간이 걸리므로, 동적 계획법을

이 튜토리얼에서는 C++를 사용하여 주어진 범위 안에서 최소 약수(가장 작은 인수)가 K인 숫자의 개수를 구하는 프로그램을 살펴봅니다. 문제의 조건은 간단합니다. 범위 [a, b]가 주어졌을 때, 이 범위에 속한 숫자 중에서 가장 작은 약수가 정확히 K인 수의 개수를 세는 것이 우리의 과제입니다. 접근 방법 어떤 수 n의 최소 약수가 K가 되려면 아래 두 가지 조건을 동시에 만족해야 합니다. K는 반드시 소수여야 합니다. K가 합성수라면 K보다 작은 약수가 항상 존재하기 때문에, 어떤 수의 최소 약수가 K일 수 없습니다. n은

이 튜토리얼에서는 C++를 사용해 행렬(2차원 배열)에서 내림차순으로 정렬된 열의 개수를 구하는 방법을 알아봅니다. R×C 크기의 행렬이 주어졌을 때, 각 열의 원소들이 위에서 아래로 갈수록 같아지거나 작아지는(내림차순) 형태를 띠는 열이 몇 개인지 세는 것이 목표입니다. 접근 방법 핵심 아이디어는 단순합니다. 각 열을 하나씩 순회하면서, 해당 열의 인접한 두 원소가 항상 mat[j-1][i] >= mat[j][i] 조건(위 원소가 아래 원소보다 크거나 같음)을 만족하는지 검사합니다. 검사 도중 조건이 한 번이라도 깨지면 그

개요이 튜토리얼에서는 C++을 활용해 행렬(matrix) 안에서 오름차순 또는 내림차순으로 정렬된 행의 개수를 구하는 프로그램을 만들어 보겠습니다.문제 정의m×n 크기의 2차원 행렬이 주어졌을 때, 각 행이 오름차순(비내림차순)이거나 내림차순(비오름차순)으로 정렬되어 있는지 판별하고, 조건을 만족하는 행의 총 개수를 반환하는 것이 목표입니다.예를 들어 아래와 같은 4×5 행렬을 살펴보겠습니다.{1, 2, 3, 4, 5} → 오름차순 정렬 O {4, 3, 1, 2, 6} → 정렬되지 않음 X {8, 7, 6, 5, 4} →

개요 이 글에서는 배열에서 합이 k로 나누어 떨어지는 부분 배열(subarray)의 개수를 구하는 알고리즘을 다룹니다. 배열과 정수 k가 주어졌을 때, 연속된 원소들의 합이 k로 나누어 떨어지는 모든 부분 배열의 개수를 세는 것이 목표입니다. 접근 방법: 누적 합과 나머지 연산 활용 모든 부분 배열을 하나씩 확인하는 브루트 포스 방식은 O(n²) 이상의 시간이 소요됩니다. 하지만 누적 합(prefix sum)과 나머지 연산을 활용하면 O(n + k) 시간 안에 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

이 튜토리얼에서는 주어진 문자열 안에서 길이가 소수(prime)인 회문(palindrome) 부분 문자열의 개수를 구하는 프로그램을 다룹니다.예를 들어 하나의 문자열이 입력으로 주어졌을 때, 우리의 목표는 그 문자열의 모든 부분 문자열 중에서 회문이면서 동시에 길이가 소수인 것들의 개수를 세는 것입니다.접근 방법이 문제는 크게 두 단계로 나누어 해결할 수 있습니다.1단계: 소수 판별 (에라토스테네스의 체)부분 문자열의 길이는 최대 문자열 전체 길이까지 가능하므로, 에라토스테네스의 체(Sieve of Eratosthenes)를 이용해

문제 소개이번 튜토리얼에서는 4개의 배열에서 각각 하나씩 원소를 선택해 만든 쿼드러플(quadruple) 중, 그 XOR 연산 결과가 주어진 값 x와 같아지는 조합의 개수를 구하는 프로그램을 다룹니다.즉, 4개의 배열과 값 x가 입력으로 주어졌을 때, 각 배열에서 원소를 하나씩 골라 만들 수 있는 모든 조합을 검사하여 XOR 값이 x와 정확히 일치하는 경우의 수를 세는 것이 우리의 목표입니다.접근 방법: 브루트 포스(Brute Force)가장 직관적인 방법은 4중 반복문을 사용해 가능한 모든 조합을 하나씩 확인하는 것입니다. 각 단

이 튜토리얼에서는 이진 배열의 접두사 중 주어진 값 x로 나누어 떨어지는 것의 개수를 구하는 프로그램을 살펴보겠습니다.문제에서는 0과 1로만 구성된 이진 배열과 정수 값 x가 주어집니다. 우리의 목표는 배열의 각 위치까지의 접두사(앞부분)를 하나의 이진수로 해석했을 때, 그 값이 x로 나누어 떨어지는 경우의 수를 세는 것입니다.문제 이해하기예를 들어, 배열 {1, 0, 1, 0, 1, 1, 0}과 x = 2가 주어졌다고 가정해 보겠습니다. 각 인덱스까지의 접두사를 이진수로 변환하면 다음과 같습니다.1 → 1 (나누어 떨어지지 않음)

이 튜토리얼에서는 그래프에서 정확히 k개의 간선을 사용하여 출발 정점(source)에서 목적지 정점(destination)까지 도달하는 모든 경로(walk)의 개수를 구하는 프로그램을 다룹니다. 그래프와 출발점, 목적지의 정보가 주어졌을 때, 우리의 목표는 간선을 정확히 k번 거쳐 출발점에서 목적지에 도착하는 모든 가능한 경로의 수를 찾는 것입니다. 알고리즘 접근 방식 가장 기본적인 방법은 재귀(recursion)를 이용하는 것입니다. 현재 정점에서 간선으로 연결된 인접 정점으로 한 칸씩 이동하면서, 남은 간선의 개수 k를 하나씩

이 튜토리얼에서는 곱이 K 이하인 부분 수열(sub-sequence)의 개수를 구하는 프로그램을 다뤄보겠습니다.배열과 값 K가 주어졌을 때, 원소들의 곱이 K 이하가 되는 모든 부분 수열의 개수를 찾는 것이 목표입니다.핵심 아이디어: 로그 변환곱셈 값을 직접 다루면 오버플로우 위험이 있고 비교도 번거롭습니다. 이 코드는 로그의 성질을 활용합니다. log(a × b) = log(a) + log(b)이므로, 각 원소의 log2 값을 미리 구해 두면 곱이 K 이하라는 조건을 log2 값의 합이 log2(K) 이하라는 조건으로 바꿀 수 있

이 튜토리얼에서는 C++ STL(표준 템플릿 라이브러리)에서 생성자(Constructor)를 활용해 리스트(list) 컨테이너를 생성하는 방법을 자세히 알아봅니다.리스트(List)는 메모리상에 요소들을 연속적이지 않은(non-contiguous) 방식으로 저장하는 자료구조입니다. 각 노드가 포인터로 연결되는 이중 연결 리스트(doubly linked list) 형태로 구현되어 있기 때문에, 벡터(vector)와 비교했을 때 임의 위치에서의 삽입과 삭제가 훨씬 빠르다는 장점이 있습니다.C++ 코드 예제아래 예제에서는 생성자에 초기화

이번 튜토리얼에서는 C++에서 pair(쌍)를 키로 사용하는 unordered_map을 생성하는 방법에 대해 알아보겠습니다.C++의 unordered_map은 기본적으로 pair 타입에 대한 해시 함수(hash function)를 제공하지 않습니다. 따라서 특정 pair에 대한 해시 값을 사용하려면, 사용자가 직접 해시 함수를 정의하여 명시적으로 전달해 주어야 합니다.아래 예제에서는 두 개의 정수를 묶은 pair를 키로 사용하는 unordered_map을 만들기 위해, 커스텀 해시 구조체인 hash_pair를 정의하고 이를 맵 선언

이 글에서는 C++에서 사용자 정의 클래스(user-defined class)를 키(key)로 사용하는 unordered_map을 생성하는 방법을 알아봅니다.unordered_map은 내부적으로 해시 테이블을 기반으로 동작하기 때문에, 기본 자료형(int, string 등)이 아닌 사용자 정의 클래스를 키로 사용하려면 다음 두 가지 요소가 반드시 필요합니다.동등성 비교 연산자(operator==): 해시 충돌이 발생했을 때 두 키가 실제로 같은지 비교하기 위해 필요합니다.사용자 정의 해시 함수: 클래스 객체를 size_t 타입의 해

이 글에서는 C++에서 사용자 정의 클래스(user-defined class) 또는 구조체(struct)를 요소로 가지는 unordered_set을 생성하는 방법을 단계별로 살펴보겠습니다.unordered_set은 내부적으로 해시 기반으로 동작하기 때문에, 기본 자료형(int, string 등)이 아닌 사용자 정의 타입을 저장하려면 두 가지가 반드시 필요합니다.동등성 비교 연산자(operator==): 두 객체가 같은지 판단하는 기준을 정의해야 합니다.사용자 정의 해시 함수: 객체를 해시 값으로 변환하는 규칙을 직접 제공해야 합니다

이 글에서는 C++의 STL(표준 템플릿 라이브러리)을 활용하여 두 배열 사이의 공통 원소를 찾는 방법을 알아보겠습니다.두 배열의 교집합을 구할 때는 set_intersection() 메서드를 사용하면 됩니다. 이 함수는 두 개의 정렬된 범위를 비교하여 양쪽에 모두 존재하는 원소만 결과 컨테이너에 저장합니다. 따라서 반드시 sort()로 배열을 먼저 정렬한 뒤 호출해야 올바른 결과를 얻을 수 있습니다.예제 코드#include <bits/stdc++.h> using namespace std; int main(){ /