문제 개요 두 개의 정수 k와 n이 주어졌을 때, 다음과 같은 급수의 합을 구하는 프로그램을 작성해야 합니다. Kn + (Kn-1 × (K-1)1) + (Kn-2 × (K-1)2) + … + (K-1)n 예시로 문제 이해하기 입력: n = 3, k = 4 출력: 175 설명: 급수의 각 항은 다음과 같습니다. = 4^3 + (4^2 × 3^1) + (4^1 × 3^2) + (4^0 × 3^3) = 64 + 48 + 36 + 27 = 175 방법 1: 반복문을 이용한 기본 풀이 가장 직관적인 방법은 for 반복문을 사용해 급수의 각

C++의 기본 정수 타입(long long 등)으로는 담을 수 없는 매우 큰 숫자 두 개가 문자열 형태로 주어집니다. 이 문제의 목표는 이 두 큰 수의 합을 정확하게 계산하는 프로그램을 작성하는 것입니다. 문제 이해를 돕는 예시 입력: number1 = 341299123919 number2 = 52413424 출력: 341351537343 이 문제를 해결하는 핵심 아이디어는 손으로 직접 덧셈을 할 때와 같습니다. 두 문자열을 일의 자리부터 순회하면서 각 자릿수끼리 더하고, 합이 10을 넘으면 올림수(carry)를 다음 자릿수로 전파

문제 소개 이 문제에서는 두 개의 수가 주어지며, 그중 하나는 일반적인 정수이고 다른 하나는 자릿수(digit) 배열로 표현되어 있습니다. 우리의 과제는 자릿수 배열 형태로 표현된 수와 일반 정수의 합을 구하는 프로그램을 작성하는 것입니다. 문제 이해를 돕는 예제 입력: n = 213, m[] = {1, 5, 8} 출력: 371 설명: 213 + 158 = 371 접근 방법 이 문제는 우리가 익히 알고 있는 세로셈 덧셈 원리를 그대로 적용하면 쉽게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다. 배열의 마지막 요소(n-1

개요이 튜토리얼에서는 C++을 활용하여 곱이 주어진 값과 같아지는 두 개의 서로 다른 소수를 찾는 프로그램을 다룹니다.정수 N이 하나 주어지면, 곱이 N과 정확히 일치하는 소수 쌍을 찾는 것이 목표입니다. 예를 들어 N = 15라면 3 × 5 = 15이므로 정답은 3과 5입니다. 반면 N = 24처럼 어떤 소수 조합으로도 표현할 수 없는 경우에는 쌍이 존재하지 않는다고 출력해야 합니다.알고리즘 접근 방식에라토스테네스의 체를 이용해 N 이하의 모든 소수를 미리 구합니다.2부터 N-1까지 반복하면서 각 수 i에 대해 몫 x = N /

이 튜토리얼에서는 두 문자열에서 공통되지 않은(uncommon) 문자를 찾는 프로그램을 다룹니다.두 개의 문자열이 주어졌을 때, 어느 한쪽에만 존재하는 문자들을 골라내어 알파벳 순서로 정렬해 출력하는 것이 우리의 과제입니다.알고리즘 접근 방식이 문제는 크기 26의 정수 배열을 활용하면 효율적으로 해결할 수 있습니다. 각 인덱스는 알파벳 소문자 하나에 대응되며, 배열 값의 의미는 다음과 같습니다.0: 두 문자열 모두에 해당 문자가 없음1: 첫 번째 문자열에만 해당 문자가 존재함2: 두 번째 문자열에만 해당 문자가 존재함-1: 두 문자

이 글에서는 동일한 하나의 행렬을 행 우선(row-major) 순서와 열 우선(column-major) 순서로 각각 배치한 뒤, 이 둘을 더해서 새롭게 형성되는 행렬의 대각합(trace)을 C++로 구하는 방법을 알아봅니다. 문제 정의 두 개의 배열이 주어집니다. 하나는 행 우선 순서로 채워진 행렬이고, 다른 하나는 열 우선 순서로 채워진 행렬입니다. 우리가 해야 할 일은 이 두 행렬을 더해 만들어진 새로운 행렬의 대각합을 계산하는 것입니다. 여기서 대각합(trace)이란 정방 행렬의 주대각선(i == j)에 위치한 원소들의 합을

개요이 튜토리얼에서는 트리에서 세 개의 노드로 이루어진 삼중항(triplet)을 찾되, 이 세 노드를 서로 연결하는 경로가 커버하는 노드의 수가 최대가 되도록 만드는 프로그램을 살펴봅니다.N개의 노드로 구성된 트리가 주어집니다. 우리의 과제는 세 노드를 연결하는 경로 위에 놓인 노드의 수가 최대가 되는 노드 조합을 찾는 것입니다.접근 방법이 문제는 트리의 지름(diameter), 즉 트리 내에서 가장 긴 경로를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.임의의 노드에서 DFS를 수행하여 가장 멀리 있는

이 튜토리얼에서는 합과 곱이 모두 주어진 값 N과 같은 두 숫자를 찾는 프로그램을 다룹니다.하나의 정수 값이 주어졌을 때, 두 수의 곱과 합이 모두 해당 값과 일치하는 두 개의 값을 찾는 것이 우리의 과제입니다.문제 접근 방법a + b = N이고 a × b = N을 만족하는 두 수 a와 b를 찾으려면 이차방정식을 활용하면 됩니다.두 수를 근으로 갖는 이차방정식은 다음과 같은 형태가 됩니다.x² − Nx + N = 0근의 공식에 따라 두 값은 다음과 같이 계산됩니다.x = (N ± √(N² − 4N)) / 2여기서 판별식 D = N²

이 튜토리얼에서는 신호가 문자열의 모든 위치에 도달하는 데 걸리는 시간을 구하는 프로그램을 C++로 작성해 보겠습니다.문제 개요x와 o로만 구성된 문자열이 주어집니다. 신호는 x 위치에서 발생하여 왼쪽과 오른쪽 두 방향으로 동시에 전파되며, 1단위 시간마다 인접한 o 하나를 x로 바꿉니다. 우리의 목표는 문자열 전체가 x로 변환되기까지 필요한 총 시간을 계산하는 것입니다.접근 방법핵심 아이디어는 연속된 o로 이루어진 각 구간(블록)을 기준으로 생각하는 것입니다.블록의 양쪽 끝에 x가 있는 경우: 신호가 양방향에서 동시에 진행되므로,

이 튜토리얼에서는 문자열에 포함된 고유한 연도의 총 개수를 구하는 프로그램을 다룹니다.주어진 문자열에는 DD-MM-YYYY 형식으로 작성된 날짜들이 포함되어 있습니다. 우리가 해야 할 작업은 이 문자열에서 언급된 서로 다른 연도의 개수를 세는 것입니다.접근 방법문자열을 한 글자씩 순회하면서 숫자인 경우 임시 문자열에 추가하고, 하이픈(-)을 만나면 임시 문자열을 초기화합니다. 임시 문자열의 길이가 4가 되면 이를 연도로 간주하여 unordered_set에 삽입합니다. 집합(set)은 중복을 허용하지 않으므로, 최종적으로 집합의 크기

이 튜토리얼에서는 배열의 특정 인덱스 값을 갱신하고, 주어진 범위 내 요소들의 최대 공약수(GCD)를 구하는 쿼리를 처리하는 프로그램을 다룹니다.정수로 이루어진 배열과 Q개의 쿼리가 제공되며, 각 쿼리는 다음 두 가지 작업 중 하나를 수행해야 합니다:값 갱신(Update): 특정 인덱스의 값을 새로운 값으로 변경범위 조회(Query): 지정된 두 인덱스 구간 사이의 최대 공약수(GCD) 계산접근 방법: 세그먼트 트리(Segment Tree)매번 배열 전체를 순회하며 GCD를 계산하면 O(n)의 비용이 들어 잦은 조회에 비효율적입니다

개요이 글에서는 C++에서 BIT(Binary Indexed Tree, 펜윅 트리)를 활용하여 색상이 칠해진 트리의 특정 서브트리에 포함된 서로 다른 색상의 개수를 효율적으로 구하는 프로그램을 다룹니다.입력으로는 각 노드가 배열로 주어진 색상을 가지는 루트 있는 트리(rooted tree)가 제공됩니다. 우리의 목표는 주어진 노드를 루트로 하는 서브트리 안에 존재하는 서로 다른 색상 노드의 개수를 구하는 것입니다.접근 방법매 쿼리마다 서브트리를 직접 순회하면 최악의 경우 O(N×Q)의 시간이 소요되어 비효율적입니다. 이 문제는 다음

이 튜토리얼에서는 L번째로 작은 숫자와 R번째로 작은 숫자가 배열에서 위치한 인덱스 간의 절대 차이를 반환하는 쿼리를 처리하는 프로그램을 살펴봅니다.정수로 이루어진 배열과 Q개의 쿼리가 주어졌을 때, 각 쿼리 (L, R)에 대해 배열에서 L번째로 작은 값의 인덱스와 R번째로 작은 값의 인덱스 사이의 절대 차이를 구하는 것이 목표입니다.접근 방법이 문제는 다음과 같은 단계로 효율적으로 해결할 수 있습니다.배열의 각 요소를 (값, 원래 인덱스) 형태의 쌍(pair)으로 저장합니다.값을 기준으로 배열을 오름차순으로 정렬합니다.각 쿼리 (

이 튜토리얼에서는 주어진 정수 N보다 작거나 같은 세 정수를 찾아, 그 세 수의 최소공배수(LCM)가 가능한 한 최대가 되도록 만드는 프로그램을 살펴봅니다. 정수 하나가 입력으로 주어지면, 그 값 이하의 범위에서 세 정수를 골라 세 수의 LCM이 최대가 되는 조합을 출력하는 것이 목표입니다. 접근 방법 세 수의 곱이 클수록 LCM도 커지는 경향이 있으므로, 직관적으로는 N에 가장 가까운 연속된 세 수 N, N-1, N-2가 답일 것 같습니다. 하지만 N이 짝수라면 N과 N-2가 공약수 2를 공유하여 LCM이 손실되므로, 경우를 나

문제 소개 이 글에서는 트리에서 두 노드 사이의 조상-자손 관계를 판별하는 쿼리 문제를 다룹니다. 루트가 있는 트리(rooted tree)와 Q개의 쿼리가 주어지며, 각 쿼리에 담긴 두 노드 중 한 노드가 다른 노드의 조상인지 아닌지를 확인하는 것이 과제입니다. 접근 방법: DFS 진입·탈출 시간 활용 쿼리마다 매번 부모를 거슬러 올라가며 조상 여부를 확인하면 매우 비효율적입니다. 대신 DFS(깊이 우선 탐색)를 딱 한 번 수행하면서 각 노드의 진입 시간(timeIn)과 탈출 시간(timeOut)을 기록해 두면, 이후 모든 쿼리를

문제 개요숫자로 채워진 정사각형 미로가 있다고 가정해 보겠습니다. 목표는 모서리 셀에서 출발하여 중앙 셀에 도달하는 모든 경로를 찾는 것입니다.이동 규칙은 간단합니다. 현재 셀의 값을 n이라 할 때, 상·하·좌·우 네 방향 중 하나를 선택해 정확히 n칸 이동해야 합니다. 즉, 셀 [i, j]에서 n은 해당 셀의 값이며, 다음 네 위치로만 이동할 수 있습니다.[i+n, j] — 아래로 n칸[i-n, j] — 위로 n칸[i, j+n] — 오른쪽으로 n칸[i, j-n] — 왼쪽으로 n칸미로를 벗어나는 이동은 허용되지 않으며, 이미 방문한

k개의 서로 다른 리스트가 주어졌다고 가정해 보겠습니다. 각 리스트의 요소는 오름차순으로 정렬되어 있습니다. 이때 k개의 리스트 각각에서 최소 한 개 이상의 숫자를 포함하는 가장 작은 범위를 찾아야 합니다.여기서 범위 [a, b]가 범위 [c, d]보다 작다는 것은 다음 조건 중 하나를 만족하는 경우입니다.b - a < d - c 인 경우b - a == d - c 이면서 a < c 인 경우예를 들어 입력이 [[4,10,15,25,26], [0,9,14,20], [5,18,24,30]]이라면, 세 리스트에서 각각 15, 1

이진 탐색 트리(Binary Search Tree, BST)와 하나의 목표(target) 값이 주어졌을 때, 주어진 BST에서 목표값에 가장 가까운 k개의 값을 찾아야 합니다. 이때 목표값은 부동소수점(floating-point) 숫자입니다. k는 항상 유효하며, k ≤ 전체 노드 수라고 가정할 수 있습니다.예를 들어, 아래와 같은 트리가 있다고 가정해 보겠습니다.target = 3.714286, k = 2라면 출력 결과는 [4, 3]이 됩니다.접근 방법이 문제는 두 개의 스택을 활용하여 효율적으로 해결할 수 있습니다. 하나는 목표

문제 개요어떤 문자열이 주어지며, 이 문자열은 오직 두 가지 문자로만 구성되어 있다고 가정해 봅시다. L은 왼쪽 회전(left rotation), R은 오른쪽 회전(right rotation)을 의미합니다. 우리의 목표는 이 회전 명령들을 모두 수행한 후 피벗(pivot)이 향하게 되는 최종 방향을 찾는 것입니다.방향은 나침반의 네 방위, 즉 북(N), 동(E), 남(S), 서(W)로 표현하며, 처음에 피벗은 항상 북쪽(N)을 가리키고 있다고 가정합니다.예를 들어 입력이 RRLRLLR라면 출력은 E(동)가 됩니다. 그 과정을 살펴보

문제 소개크기가 N인 숫자 배열이 있다고 가정해 봅시다. 이 배열의 모든 요소는 정확히 m번씩 등장하지만, 단 하나의 요소만 다른 횟수로 나타납니다. 우리의 목표는 바로 그 특별한 요소를 찾아내는 것입니다.예를 들어, 배열 A = [6, 2, 7, 2, 2, 6, 6]이고 m = 3이라면, 대부분의 요소(6과 2)는 세 번씩 등장하지만 7은 한 번만 등장합니다. 따라서 출력 결과는 7이 됩니다.해결 접근 방식: 비트 단위 카운팅이 문제는 각 비트 위치별로 1이 등장하는 횟수를 세는 비트 연산 기법으로 효율적으로 해결할 수 있습니다.