문제 개요x축 위에 n개의 점이 있고, 점들 사이에서 허용된 이동(transactions) 목록이 주어진다고 가정해 봅시다. 이때 허용된 이동만을 사용하여 시작 지점에서 끝 지점까지 도달할 수 있는지 판별하는 것이 문제입니다.두 점 x1과 x2 사이의 이동이 허용되어 있다면, 현재 위치한 점 x에서 x1과 x2 사이의 임의의 중간 지점으로 이동할 수도 있고, x2로 곧바로 이동할 수도 있습니다.예를 들어 n = 5이고, 허용된 이동 구간이 0→2, 2→4, 3→5라고 해 보겠습니다. 이 경우 출력은 YES입니다. 0→2→3→5로 이

문제 개요0과 1로만 구성된 크기 N의 배열이 주어졌을 때, 단 하나의 0을 1로 바꿔서 가장 긴 연속된 1의 시퀀스를 얻으려면 어느 위치의 0을 바꿔야 할까요?예를 들어 배열이 arr = [1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1]이라고 가정해 봅시다. 이 경우 정답은 인덱스 9입니다. 인덱스 9의 0을 1로 바꾸면 앞쪽의 세 개(인덱스 6~8)와 뒤쪽의 세 개(인덱스 10~12)가 하나로 연결되어 총 7개로 이루어진 최대 연속 1 시퀀스가 만들어지기 때문입니다.알고리즘 접근 방식이 문제는 세 개의 인덱

숫자 n이 주어졌을 때, n보다 작거나 같은 가장 큰 특수 소수(special prime)를 찾아야 합니다. 특수 소수란 자릿수를 하나씩 차례대로 붙여가며 만들어지는 모든 중간 숫자가 소수인 수를 의미합니다.예를 들어 379를 살펴보면, 한 자리 숫자 3은 소수이고, 두 자리 숫자 37도 소수이며, 세 자리 숫자 379 역시 소수입니다. 이처럼 왼쪽부터 잘라 만든 모든 접두사가 소수일 때 그 수를 특수 소수라고 부릅니다.접근 방법: 에라토스테네스의 체이 문제는 에라토스테네스의 체(Sieve of Eratosthenes)를 활용하면

두 문자열 X와 Y가 주어졌을 때, X의 부분 수열(subsequence) 중에서 Y의 부분 문자열(substring)이 되는 가장 긴 것의 길이를 구하는 문제입니다.예를 들어 X = ABCD, Y = BACDBDCD라고 한다면 결과는 3이 됩니다. ACD가 X의 부분 수열이면서 동시에 Y의 부분 문자열이 되는 가장 긴 경우이기 때문입니다.동적 계획법(Dynamic Programming) 접근이 문제는 동적 계획법을 활용해 효율적으로 해결할 수 있습니다. X의 길이를 n, Y의 길이를 m이라고 할 때, (m+1)×(n+1) 크기의

C++에서 두 문자열을 비교해야 하는 경우가 자주 있습니다. 다행히 C++은 string 클래스를 기본으로 제공하며, 표준 라이브러리에는 문자열 비교를 위한 compare() 함수가 포함되어 있습니다.compare() 함수는 두 문자열의 문자를 처음부터 하나씩 순서대로 검사합니다. 검사 중 일치하지 않는 문자가 발견되면 그 차이를 나타내는 0이 아닌 값을 반환하고, 모든 문자가 일치하면 0을 반환합니다. 반환값의 부호를 통해 어느 문자열이 사전순으로 더 큰지도 알 수 있습니다.예제 코드다음 예제는 compare() 함수를 활용하여

서로 다른 문자들로 구성된 행렬이 주어졌을 때, 하나의 시작 문자에서 출발하여 현재 문자보다 알파벳 순서상 1만큼 큰 문자들을 따라 이동하며 만들 수 있는 가장 긴 연속 경로의 길이를 구하는 문제입니다. 예를 들어 e에서 출발했다면 f, g, h, i처럼 연속되는 문자만 거치며 진행할 수 있습니다. 위 그림은 E에서 시작하는 경우의 예시입니다. 문제 해결 접근 방식 가장 긴 경로를 찾기 위해 깊이 우선 탐색(Depth First Search, DFS) 알고리즘을 사용합니다. DFS를 수행하는 도중에는 동일한 부분 문제(subpro

경쟁 프로그래밍에서는 문제를 빠르고 정확하게 해결하는 능력이 무엇보다 중요합니다. 이 글에서는 코딩 시간을 단축하고 코드 효율을 높여 주는 실용적인 C++ 트릭들을 소개합니다. 비트 연산부터 STL 알고리즘까지, 초보자도 바로 활용할 수 있는 팁들을 하나씩 살펴보겠습니다.1. % 연산자 없이 홀수·짝수 판별하기비트 AND 연산을 활용하면 나머지 연산자(%) 없이도 숫자의 홀짝을 쉽게 판별할 수 있습니다. 모든 홀수는 최하위 비트(LSb)가 1이므로, 숫자와 1을 AND 연산했을 때 결과가 0이 아니면 홀수입니다.if ((n &

이번 글에서는 C++에서 복소수(Complex Number)를 생성하고 활용하는 방법을 알아보겠습니다. C++은 객체지향 언어이므로 복소수를 하나의 클래스로 정의할 수 있습니다. 복소수는 실수부(real part)와 허수부(imaginary part)로 구성되므로, 이 두 값을 멤버 변수로 가지는 클래스를 만들고, 복소수 연산을 처리하는 멤버 함수들을 함께 구현하면 됩니다.복소수 클래스의 기본 구조아래 예제에서는 다음과 같은 요소들을 포함하는 복소수 클래스를 만들어 보겠습니다.기본 생성자: 복소수를 0+0i로 초기화매개변수 생성자:

개요스택 안에서 최댓값(maximum element)을 저장하고, 이를 O(1) 시간에 조회할 수 있는 스택을 만들어야 한다고 가정해 봅시다. 여기서 중요한 제약 조건은 추가 공간을 O(1)만 사용해야 한다는 점입니다.이 문제는 별도의 보조 스택 없이, 하나의 사용자 정의 스택으로 해결할 수 있습니다. 핵심 아이디어는 현재까지의 최댓값(stack_max) 변수 하나를 유지하면서, 새로 삽입되는 값이 기존 최댓값보다 클 경우 수학적 변환을 통해 이전 최댓값 정보를 인코딩하는 것입니다.동작 원리peek(조회) 연산: 스택의 top 요소

개요C++ 표준 템플릿 라이브러리(STL)가 제공하는 sort() 함수를 사용하면 배열이나 벡터를 단 한 줄의 코드로 손쉽게 정렬할 수 있습니다. 이 글에서는 <algorithm> 헤더에 포함된 sort() 함수를 이용해 배열을 오름차순으로 정렬하는 방법을 예제와 함께 살펴보겠습니다.예를 들어 배열이 A = [52, 14, 85, 63, 99, 54, 21]과 같다면, 정렬 후 결과는 [14, 21, 52, 54, 63, 85, 99]가 됩니다.예제 코드아래 코드는 배열을 선언한 뒤, sort() 함수에 배열의 시작 주소

문제 이해n개의 요소로 이루어진 배열이 있다고 가정해 보겠습니다. 이때 선택된 임의의 두 요소 간 절대 차이가 1보다 작거나 같도록 배열에서 선택할 수 있는 요소의 최대 개수를 구하는 것이 목표입니다.예를 들어 배열이 [2, 2, 3, 4, 5]라고 한다면 정답은 3이며, 이때 최대 개수를 만족하는 수열은 2, 2, 3입니다.접근 방법절대 차이가 0 또는 1이라는 조건은 선택된 숫자들이 반드시 x 또는 x + 1 형태여야 한다는 의미입니다. 따라서 다음과 같은 아이디어로 문제를 해결할 수 있습니다.맵(map) 자료구조를 사용해 배열

C++에서 클래스에 포인터 멤버 변수가 없다면, 컴파일러가 자동으로 생성해 주는 기본 복사 생성자와 대입 연산자만으로도 충분합니다. 하지만 클래스가 포인터를 멤버로 가지고 있다면 이야기가 달라집니다. 기본 대입 연산자는 얕은 복사(shallow copy)를 수행하기 때문에, 여러 객체가 같은 메모리 주소를 공유하게 되어 예기치 않은 동작이나 문제를 일으킬 수 있습니다. 이럴 때는 사용자 정의 대입 연산자를 직접 작성해야 합니다.문제 상황: 기본 대입 연산자의 얕은 복사아래 예제는 포인터 멤버를 가진 클래스이지만, 사용자 정의 대입

문제 개요n자리 숫자가 하나 주어졌다고 가정해 봅시다. 이때 해당 숫자의 모든 자릿수를 그대로 사용하여 만들 수 있는 최댓값을 찾아야 합니다.예를 들어 입력이 339625라면, 각 자릿수(3, 3, 9, 6, 2, 5)를 재배열하여 얻을 수 있는 최대 숫자는 965332입니다.접근 방법가장 직관적인 방법은 자릿수들을 내림차순으로 정렬한 뒤 출력하는 것입니다. 하지만 정렬 알고리즘은 일반적으로 O(n log n)의 시간 복잡도를 가지므로, 더 효율적인 방법을 사용할 수 있습니다.핵심 아이디어는 다음과 같습니다.크기가 10인 배열을 만

객체 지향 프로그래밍(OOP) 언어의 기본 특징으로는 상속(Inheritance), 캡슐화(Encapsulation), 다형성(Polymorphism)이 있습니다. 이 세 가지 특징을 완전하게 지원하는 언어를 객체 지향 프로그래밍 언어라고 부릅니다. C++는 이 세 가지 기능을 대부분 지원하지만 완벽하지 않기 때문에 부분적인 객체 지향 언어로 분류됩니다. 그렇다면 C++가 완전한 객체 지향 언어로 인정받지 못하는 이유는 무엇일까요?C++가 완전한 객체 지향 언어가 아닌 이유1. main() 함수가 클래스 외부에 존재C++에서는 프로

문제 개요두 개의 수 n과 fact가 주어졌을 때, fact!(fact의 팩토리얼)를 나눌 수 있는 n의 최대 거듭제곱을 구하는 것이 목표입니다.예를 들어 fact = 5, n = 2라면 답은 3입니다. 5! = 120이며, 120은 2³ = 8로는 나누어 떨어지지만 2⁴ = 16으로는 나누어지지 않기 때문입니다.접근 방법: 르장드르 공식(Legendres Formula)이 문제는 르장드르 공식을 활용하면 효율적으로 해결할 수 있습니다. 르장드르 공식은 어떤 소수 p가 fact!를 나누는 최대 거듭제곱을 구하는 공식으로, 다음과 같

문제 개요두 정수 N과 K가 주어졌을 때, [1부터 N] 범위의 정수들로 구성된 순열 P 중에서 gcd(P[i], i) > 1을 만족하는 인덱스(1-based indexing)의 개수가 정확히 K가 되는 순열을 찾는 것이 목표입니다.예를 들어 N = 4, K = 3이라면 정답은 [1, 2, 3, 4]입니다. 각 위치별로 gcd(1, 1) = 1, gcd(2, 2) = 2, gcd(3, 3) = 3, gcd(4, 4) = 4이므로, 최대공약수가 1보다 큰 인덱스는 2번, 3번, 4번으로 총 3개(K = 3)이기 때문입니다.핵심

문제 개요두 개의 정수 n과 k가 주어졌을 때, n! mod (k^x) = 0을 만족하는 x의 최댓값을 구하는 것이 목표입니다.예를 들어 n = 5, k = 2라고 가정해 보겠습니다. 이때 n! = 120이며, x 값에 따라 나머지는 다음과 같이 변합니다.120 mod 2⁰ = 0120 mod 2¹ = 0120 mod 2² = 0120 mod 2³ = 0120 mod 2⁴ = 8120 mod 2⁵ = 24120 mod 2⁶ = 56120 mod 2⁷ = 120x = 3까지는 나머지가 0이지만 x = 4부터는 그렇지 않으므로, 정답은

세타(θ), 즉 각도 값이 하나 주어져 있다고 가정해 보겠습니다. 목표는 시침과 분침 사이의 각도가 정확히 이 값이 되는 시각을 hh:mm 형식으로 찾는 것입니다. 예를 들어 주어진 각도가 90°라면 답은 3:00이 될 수 있습니다.접근 방법시계에는 총 12시간이 표시되므로 시(hour)의 후보는 12가지, 분(minute)의 후보는 60가지입니다. 따라서 가능한 모든 시각 조합을 반복문으로 하나씩 확인하는 완전 탐색(brute force) 방식을 사용할 수 있습니다. 각 시각에서 시침과 분침이 이루는 각도를 계산하여, 주어진 세타

문제 개요이진 트리가 하나 주어져 있다고 가정해 봅시다. 우리가 해야 할 작업은 수직 순회(vertical order traversal)를 수행했을 때, 각 수직 라인(열)에 속한 노드 값들의 합을 계산하고, 그중 최댓값을 출력하는 것입니다.예를 들어 아래와 같은 이진 트리가 있다고 하겠습니다.이 트리를 수직 순회하면 각 열의 노드 합은 다음과 같습니다.4 2 1 + 5 + 6 = 12 3 + 8 = 11 7 9여기서 가장 큰 값은 12입니다. 접근 방법은 생각보다 단순합니다. 먼저 수직 순회를 수행하여 각 열별 노드 값을 모은 뒤

문제 개요하나의 수 k가 주어졌을 때, 설정된 비트(set bit)의 개수가 n개(1 ≤ n ≤ k)인 k비트 숫자의 모든 조합을 찾는 것이 목표입니다. 결과는 설정 비트가 1개인 숫자들부터 먼저 출력하고, 이어서 2개인 숫자들, 마지막으로 모든 비트가 설정된 숫자까지 차례로 출력합니다. 설정 비트의 개수가 서로 같다면 더 작은 숫자가 앞에 오도록 정렬합니다.예를 들어 k = 3일 때 결과는 [001, 010, 100, 011, 101, 110, 111] 순서가 됩니다.풀이 접근: 동적 계획법이 문제는 동적 계획법(Dynamic P