문제 개요 이번 문제에서는 정수 n과 각 칸(cell)의 가중치를 담고 있는 n×n 크기의 행렬이 주어집니다. 목표는 마지막 행의 어느 요소든 도착점으로 삼을 수 있는 최대 가중치 경로를 찾는 프로그램을 작성하는 것입니다. 경로 탐색은 항상 좌측 상단(0,0)에서 시작하며, 이동할 수 있는 방향은 아래쪽과 대각선 두 가지뿐입니다. 왼쪽으로 이동하는 것은 허용되지 않습니다. 예시로 이해하기 입력 − n = 3 Mat[3][3] = { {4, 3, 1} {5, 8, 9} {6, 7, 2}} 출력 − 19 설명 −

문제 설명 A와 B로만 구성된 문자열이 주어집니다. 임의의 문자를 토글(다른 문자로 변경)하면 주어진 문자열을 다른 문자열로 변환할 수 있으며, 이렇게 만들 수 있는 변환의 수는 매우 많습니다. 이때 우리가 구해야 할 것은 가능한 변환 중 최대 가중치 변환의 가중치입니다. 문자열의 가중치는 다음 공식으로 계산됩니다. 문자열의 가중치 = 전체 쌍(pair)의 가중치 합 + 단일 문자의 가중치 합 − 총 토글 횟수 가중치 계산 규칙 연속된 두 문자는 서로 다를 때만 하나의 쌍으로 간주됩니다. 한 쌍의 가중치(두 문자가 서로 다른 경

문제 설명이진 트리가 주어졌을 때, 해당 트리의 최대 너비(maximum width)를 구하는 함수를 작성하는 것이 목표입니다. 여기서 트리의 너비란 각 레벨(깊이)에 존재하는 노드의 개수를 의미하며, 트리의 최대 너비는 모든 레벨의 너비 중 가장 큰 값으로 정의됩니다.다음 트리를 예로 들어 살펴보겠습니다. 10 / \ 7 4 / \ \ 9 2 1 / \ 2 5레벨 1의 너비: 1레벨 2의 너비: 2레벨 3의 너비: 3레벨 4의 너비: 2각 레벨의 너

문제 개요이 문제에서는 두 개의 양의 정수 n과 k가 주어집니다. 우리가 해야 할 일은 1부터 n까지의 숫자들 중 k개를 사용하여 만들 수 있는 최대 XOR 값을 찾는 것입니다.예시를 통해 문제를 이해해 보겠습니다.입력 − n = 5, k = 2출력 − 7설명 −5까지의 숫자는 1, 2, 3, 4, 5입니다.가능한 모든 XOR 쌍:1^2 = 3, 1^3 = 2, 1^4 = 5, 1^5 = 42^3 = 4, 2^4 = 6, 2^5 = 73^4 = 7, 3^5 = 64^5 = 1따라서 최댓값은 7입니다.접근 방법이 문제를 해결하기 위한

문제 정의주어진 범위 [L, R] 내에서 두 정수를 선택할 때, 가능한 모든 조합 중 XOR 값이 가장 큰 경우를 찾는 문제입니다.예를 들어 범위가 L = 1, R = 21로 주어진 경우 출력값은 31이 됩니다. 31은 15와 16을 XOR 연산한 값으로, 해당 범위에서 얻을 수 있는 최대 XOR 값입니다.접근 방식이 문제는 L과 R을 XOR 연산한 결과의 최상위 비트(MSB)를 활용하면 간단하게 해결할 수 있습니다. L ^ R의 결과에서 가장 높은 비트가 1인 위치를 찾으면, 그 위치부터 하위 비트까지 모두 1로 채운 값이 곧 최

이 문제에서는 크기가 n × n인 정방 행렬이 주어지며, 우리의 목표는 특정 행 전체 또는 특정 열 전체를 XOR 연산했을 때 나올 수 있는 최댓값을 계산하는 프로그램을 작성하는 것입니다.문제 이해를 위한 예시입력N = 3mat[N][N] = {{4, 9, 1}{2, 8, 3}{10, 12, 11}}출력13설명행(Row) 기준:1행: 4 ^ 9 ^ 1 = 122행: 2 ^ 8 ^ 3 = 93행: 10 ^ 12 ^ 11 = 13열(Col) 기준:1열: 4 ^ 2 ^ 10 = 122열: 9 ^ 8 ^ 12 = 133열: 1 ^ 3 ^

문제 소개 크기가 n×n인 2차원 배열(행렬)이 주어졌을 때, 행렬에 포함된 모든 원소의 평균(mean)과 중앙값(median)을 출력하는 C++ 프로그램을 작성하는 것이 이번 문제의 목표입니다. 평균(Mean)이란? 평균은 데이터 집합 전체를 대표하는 값으로, 행렬에서는 행렬을 구성하는 모든 원소 값의 산술 평균을 의미합니다. 평균 = (행렬의 모든 원소의 합) ÷ (행렬의 원소 총개수) n×n 행렬이라면 원소의 총개수는 n²이므로, 모든 원소를 한 번씩 더한 뒤 n²로 나누면 됩니다. 중앙값(Median)이란? 중앙값은 데이

문제 개요 이 문제에서는 n개의 정수로 이루어진 배열과 m개의 범위 쿼리가 주어집니다. 각 쿼리가 지정하는 범위에 포함된 요소들의 평균을 구하고, 소수점 이하는 버린 정수 값을 출력하는 프로그램을 작성해야 합니다. 예시를 통해 문제를 자세히 살펴보겠습니다. 입력 − array = {5, 7, 8, 9, 10} m = 2; [0, 3], [2, 4] 출력 − 7 9 설명 − [0, 3] 범위의 요소는 5, 7, 8, 9이며, 합은 29이고 개수는 4이므로 평균은 29 ÷ 4 = 7.25 → 7 [2, 4] 범위의 요소는 8, 9,

문제 소개이 문제에서는 용량이 각각 x와 y인 두 개의 물통과 무한한 양의 물 공급원이 주어집니다. 목표는 한 물통에 정확히 1리터의 물을 담아내는 프로그램을 작성하는 것입니다. 단, x와 y가 서로소(co-prime)라는 조건이 전제됩니다.서로소(Co-prime)란?서로소는 상대 소수(relatively prime), 상호 소수(mutually prime)라고도 불리며, 두 수 사이의 공약수가 1뿐인 관계를 말합니다. 즉, 두 수의 최대공약수(gcd, greatest common divisor)가 1이라는 의미입니다.해결 접근 방

이 문제에서는 n개의 정수로 이루어진 배열이 주어지며, 여기에 K개의 요소를 추가한 뒤 결과 배열의 중앙값(median)을 찾아야 합니다. 단, N + k는 홀수라는 조건이 주어집니다.예시를 통해 문제를 살펴보겠습니다.입력 −array = {23, 65, 76, 67} ; k = 1출력 −67문제 해결 접근 방법이 문제를 해결하기 위해 먼저 주어진 배열을 오름차순으로 정렬합니다. 그런 다음 K개의 요소를 배열의 끝에 추가한다고 가정합니다. 즉, 기존 요소보다 큰 값들을 추가하는 것입니다.N + k가 홀수라는 조건이 주어졌으므로, 중

문제 정의데이터 스트림을 통해 정수가 하나씩 계속 입력되는 상황을 가정해 보겠습니다. 이때 지금까지 읽어 들인 모든 원소의 중앙값(median)을 매 순간 효율적으로 구해야 합니다.입력이 10, 20, 30 순서로 들어온다면 중앙값은 다음과 같이 변합니다.첫 번째 원소 10을 읽은 후 → {10}의 중앙값은 10두 번째 원소 20을 읽은 후 → {10, 20}의 중앙값은 15세 번째 원소 30을 읽은 후 → {10, 20, 30}의 중앙값은 20접근 방법: 두 개의 힙(Heap) 활용새 원소가 들어올 때마다 전체 데이터를 다시 정렬

이 문제에서는 정수를 지속적으로 읽어들이는 데이터 스트림이 주어집니다. 우리의 과제는 스트림에서 요소를 하나씩 읽을 때마다, 그 시점까지 입력된 모든 요소의 중앙값(median)을 계산하는 프로그램을 작성하는 것입니다.중앙값(Median)이란 정렬된 수열(오름차순 또는 내림차순)에서 가운데에 위치한 원소를 의미합니다.중앙값 계산 방법원소의 개수가 홀수일 때는 가운데 원소 하나가 중앙값이 됩니다.원소의 개수가 짝수일 때는 가운데 두 원소의 평균이 중앙값이 됩니다.예시로 이해하기입력 − 3, 65, 12, 20, 1각 입력이 들어올 때

개요이 튜토리얼에서는 C++를 활용하여 이진 트리에서 XOR 연산 결과가 홀수가 되는 인접 노드 쌍의 개수를 구하는 프로그램을 만들어 보겠습니다.여기서 인접 노드란 부모와 자식처럼 트리에서 직접 연결되어 있는 노드를 의미합니다. 즉, 이진 트리가 주어졌을 때 서로 연결된 노드 쌍 가운데 XOR 값이 홀수인 경우의 수를 세는 것이 우리의 과제입니다.핵심 원리XOR(배타적 논리합) 연산의 성질을 살펴보면, 두 수의 XOR 결과가 홀수가 되려면 반드시 한 수는 홀수이고 다른 한 수는 짝수여야 합니다. 따라서 이 문제는 사실상 홀짝성이 서

이 튜토리얼에서는 배열 안에서 이진 표현상 K비트만큼 서로 다른 쌍의 개수를 구하는 프로그램을 다룹니다.배열과 정수 K가 주어졌을 때, 우리의 목표는 두 수의 이진 표현을 비교했을 때 정확히 K개의 비트가 서로 다른 쌍의 개수를 찾는 것입니다.핵심 아이디어두 숫자를 XOR(^) 연산하면, 서로 다른 비트 자리에만 1이 설정됩니다. 따라서 XOR 연산 결과에서 1의 개수(즉, 해밍 거리)가 K와 같다면 해당 쌍은 조건을 만족하는 쌍입니다.예제 코드#include <bits/stdc++.h> using namespace st

이 튜토리얼에서는 주어진 XOR 값과 일치하는 쌍(pair)의 개수를 구하는 프로그램을 다룹니다.배열과 하나의 목표 값이 주어지며, 우리의 과제는 두 원소의 XOR 연산 결과가 해당 값과 같아지는 쌍이 배열 안에 몇 개 있는지 찾는 것입니다.접근 방식모든 쌍을 하나씩 확인하는 브루트 포스 방식은 O(n²)의 시간이 걸리기 때문에 비효율적입니다. 대신 해시 맵(unordered_map)을 활용하면 O(n) 시간 안에 문제를 해결할 수 있습니다.핵심 아이디어는 다음과 같습니다.배열을 순회하면서 각 원소 arr[i]에 대해, 이 원소와

이번 튜토리얼에서는 C++을 이용해 문자열 안에 포함된 회문(palindrome) 부분 문자열의 개수를 구하는 방법을 알아봅니다. 회문이란 앞에서부터 읽으나 뒤에서부터 읽으나 동일한 문자열을 뜻합니다. 예를 들어 aba, aa, baab처럼 좌우 대칭을 이루는 문자열이 여기에 해당합니다. 프로그램은 하나의 문자열을 입력받아, 그 안에서 두 글자 이상으로 구성된 모든 회문 부분 문자열을 찾아 총 개수를 출력하는 것이 목표입니다. 동적 계획법(DP)을 활용한 접근 가능한 모든 부분 문자열을 일일이 검사하는 완전 탐색 방식은 비효율적일

이 튜토리얼에서는 회문(palindrome)의 제곱에 해당하는 수, 즉 슈퍼 팰린드롬(Super Palindrome)의 개수를 구하는 프로그램을 다룹니다.두 값 L과 R이 주어졌을 때, 해당 범위 내에 존재하는 슈퍼 팰린드롬의 개수를 찾는 것이 목표입니다. 여기서 슈퍼 팰린드롬이란 숫자 자신과 그 숫자의 제곱이 모두 회문인 수를 의미합니다. 예를 들어 121은 회문이고, 그 제곱근인 11 역시 회문이므로 슈퍼 팰린드롬입니다.접근 방법모든 회문은 앞부분 절반을 뒤집어 뒤에 붙이는 방식으로 생성할 수 있습니다. 이 성질을 활용해 홀수

개요이 튜토리얼에서는 C++를 사용하여 주어진 문자열에 포함된 모든 회문(팰린드롬) 부분 수열의 개수를 구하는 프로그램을 작성하는 방법을 알아봅니다.여기서 회문 부분 수열이란, 원본 문자열에서 문자들을 임의로 선택해 만든 수열 중 앞에서 읽으나 뒤에서 읽으나 동일한 수열을 의미합니다. 예를 들어 abcb라는 문자열이 주어지면, 만들 수 있는 회문 부분 수열은 a, b, c, b, bb, bcb로 총 6개입니다.알고리즘 원리이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아

이 튜토리얼에서는 주어진 숫자의 모든 완전 약수(perfect divisors)의 개수를 구하는 프로그램을 C++로 작성해 보겠습니다.여기서 완전 약수란 약수 중에서 완전 제곱수인 값들을 의미합니다. 예를 들어 16의 약수는 1, 2, 4, 8, 16이며, 이중에서 1(1²), 4(2²), 16(4²)이 완전 제곱수이므로 정답은 3이 됩니다.접근 방법효율적인 계산을 위해 다음과 같은 방식을 사용합니다.1부터 √n까지의 수만 반복하면서 n의 약수 쌍(i와 n/i)을 동시에 확인합니다. 각 약수가 완전 제곱수인지 검사하여 맞다면 카운트

개요 이 튜토리얼에서는 주어진 정수 배열에서 합이 3의 배수가 되는 크기 2 또는 크기 3의 그룹이 총 몇 개 존재하는지 구하는 프로그램을 작성해 보겠습니다. 접근 방식 모든 조합을 일일이 검사하는 대신, 각 원소를 3으로 나눈 나머지를 활용하면 효율적으로 문제를 해결할 수 있습니다. 어떤 수들의 합이 3의 배수가 되려면, 그 수들을 3으로 나눈 나머지의 합 역시 3의 배수여야 하기 때문입니다. 먼저 배열의 모든 원소를 순회하면서 나머지가 0, 1, 2인 원소의 개수를 각각 세어 배열 c에 저장합니다. 이후 다음 조합들의 개수를 모