문제 이해문자열 S가 주어졌다고 가정해 봅시다. S에는 두 가지 종류의 문자, 즉 x와 a만 포함되어 있습니다. 우리가 해야 할 일은 S에서 몇 개의 문자를 제거하여 남은 문자열이 좋은 문자열(good string)이 되도록 만들 때, 남길 수 있는 최대 길이를 구하는 것입니다.여기서 좋은 문자열이란, 문자열 전체 길이의 절반보다 엄격하게 많은 부분이 문자 a로 채워진 문자열을 의미합니다.예시입력이 S = xaxxxxa라고 해봅시다. 이 경우 출력은 3이 됩니다. x 네 개를 제거하면 문자열은 xaa가 되는데, 길이 3 중 a가 2

두 개의 숫자 n과 k가 주어졌을 때, 오직 a, b, c 세 종류의 문자만으로 구성된 길이 n의 문자열 S를 생성하는 문제를 살펴보겠습니다. 여기서 핵심 조건은 문자열 S 안에 존재하는 회문(palindrome) 부분 문자열 중 가장 긴 것의 길이가 k를 초과하지 않아야 한다는 점입니다. 예를 들어 n = 3, k = 2가 입력으로 주어진 경우를 생각해 봅시다. 이때 가능한 답 중 하나는 aab입니다. 문자열의 길이는 3이고, 가장 긴 회문 부분 문자열은 aa(길이 2)이므로 k 이하라는 조건을 만족합니다. 물론 abc처럼 회문

문제 개요n개의 요소를 가진 배열 A가 주어졌을 때, 요소들의 합이 짝수가 되는 비어 있지 않은 부분 집합(subset)의 길이를 구해야 합니다. 만약 조건을 만족하는 부분 집합이 존재하지 않는다면 -1을 반환합니다.예를 들어 입력이 A = [1, 3, 7]이라면 출력은 2가 됩니다. 그 이유는 [1, 3]의 합이 4로 짝수이기 때문입니다.해결 접근 방식이 문제는 배열에 포함된 숫자들의 홀짝성(짝수 또는 홀수 여부)만 확인하면 간단하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.배열에 짝수가 하나라도 있는 경우: 그 짝수

문제 개요 n개의 요소로 이루어진 배열 A가 주어졌다고 가정해 봅시다. 우리는 아래 연산들을 원하는 만큼 여러 번 수행할 수 있습니다. 임의의 양의 정수 k를 하나 선택합니다.수열에서 원하는 위치를 골라 그 자리에 k를 삽입합니다.삽입으로 수열이 변경되면, 이후 연산부터는 변경된 수열을 기준으로 진행합니다. 목표는 0부터 n-1까지의 모든 인덱스 i에 대해 A[i] <= i 조건을 만족시키는 데 필요한 최소 연산 횟수를 구하는 것입니다. 예를 들어 입력이 A = [1, 2, 5, 7, 4]라면 정답은 3입니다. 아래와 같은 과

두 개의 정수 n과 k가 주어졌다고 가정해 봅시다. 아말(Amal)과 비말(Bimal)은 간단한 규칙의 게임을 진행합니다. 먼저 아말이 일렬로 n개의 막대기를 그린 뒤, 두 플레이어는 번갈아 가며 자신의 차례마다 왼쪽 또는 오른쪽 끝에서 정확히 k개의 막대기를 지웁니다. 아말이 선공입니다. 만약 어떤 차례가 시작되기 전에 남아 있는 막대기가 k개 미만이라면 게임은 종료됩니다. 아말이 비말보다 엄격하게 많은 횟수로 움직였을 때만 아말이 승리하며, 우리는 최종 승자가 누구인지 판별해야 합니다. 예를 들어 입력이 n = 10, k =

문제 설명L, R, 그리고 0부터 9까지의 숫자로 구성된 문자열 S가 주어진다고 가정해 봅시다. 왼쪽에서 오른쪽 순서로 0번부터 9번까지 번호가 붙은 객실 10개를 가진 호텔이 있다고 생각해 보겠습니다. 이 호텔에는 왼쪽과 오른쪽, 두 개의 출입구가 있습니다.손님이 왼쪽 출입구로 도착하면 왼쪽 출입구에서 가장 가까운 빈 객실을 배정받고, 오른쪽 출입구로 도착하면 오른쪽 출입구에서 가장 가까운 빈 객실을 배정받습니다. 안타깝게도 객실 배정 목록을 잃어버렸지만, 모든 손님에 대해 어떤 출입구로 들어왔는지, 언제 몇 번 객실에서 퇴실했는

문제 개요n개의 원소를 가진 배열 A가 주어졌다고 가정해 보겠습니다. 일렬로 n개의 블록 타워가 세워져 있으며, i번째 타워의 높이는 A[i]입니다. 하루에 한 번씩 다음 연산을 수행할 수 있습니다. 서로 다른 두 인덱스 i와 j(i ≠ j)를 골라 타워 i에서 타워 j로 블록 하나를 옮기는 것인데, 이때 A[i]는 1 감소하고 A[j]는 1 증가합니다.여기서 건물의 추함(ugliness)은 max(A) − min(A), 즉 가장 높은 타워와 가장 낮은 타워의 높이 차이로 정의됩니다. 목표는 위 연산을 자유롭게 반복했을 때 얻을 수

문제 소개세 개의 정수 n, a, b가 주어진다고 가정해 봅시다. 우리는 정확히 n리터의 물을 구매하려고 하며, 근처에서 판매하는 물병은 두 종류뿐입니다. 첫 번째 종류는 1리터 병으로 가격이 a루피이고, 두 번째 종류는 2리터 병으로 가격이 b루피입니다. 목표는 가능한 한 적은 돈을 지출하여 정확히 n리터의 물을 구매하는 것이며, 이때 지불해야 하는 최소 금액을 구하는 것이 이 문제의 핵심입니다.예를 들어, 입력이 n = 7, a = 3, b = 2라고 해보겠습니다. 이 경우 출력은 9가 됩니다. 2리터 병 3개를 구매하면 6리터

이 튜토리얼에서는 감독관에게 들키지 않고 과제를 전달할 수 있는 방법을 찾는 알고리즘을 작성해 보겠습니다. 모든 학생은 한 줄로 앉아 있으며, 각자 자신의 과제를 감독관에게 제출해야 합니다. 그런데 A학생의 과제가 B학생의 손에 들어 있는 상황입니다. 따라서 B학생은 감독관에게 발각되지 않도록 과제를 A학생에게 되돌려주어야 합니다. 모든 학생은 한 줄(큐)로 앉아 있습니다. 우리는 과제를 들키지 않고 A학생에게 되돌려주는 방법을 찾아야 합니다. 과제를 주고받을 수 있는 조건은 다음과 같습니다. A학생(인덱스 i)은 바로 옆에 앉

이 글에서는 숫자로만 이루어진 문자열이 주어졌을 때, 이를 정수 값으로 해석하여 6으로 나누어 떨어지는 부분 문자열이 총 몇 개인지 구하는 문제를 다룹니다. 입력은 숫자(정수)로 구성된 문자열 형태이지만, 나눗셈 가능 여부는 반드시 정수 값 기준으로 판단해야 하며, 문자의 ASCII 값을 사용해서는 안 된다는 점에 유의하세요. 문제 예시 입력 str = 648 출력: 3 설명: 부분 문자열 6, 48, 648이 각각 6으로 나누어 떨어집니다. 입력 str = 38342 출력 4 설명: 부분 문자열 3834, 342, 834, 42

문제 개요0부터 9 사이의 숫자로 이루어진 문자열이 주어집니다. 이 문제의 목표는 8로 나누어떨어지면서 3으로는 나누어떨어지지 않는 부분 문자열의 개수를 계산하는 것입니다. 문제를 두 단계로 나누어 한 단계씩 코드를 작성하며 차근차근 해결해 보겠습니다.입력 예시 1str = 80출력2입력 예시 2str = 7675636788출력15해결 접근 방식이 문제를 효율적으로 풀기 위해서는 두 가지 수학적 성질을 활용합니다.8의 배수 판별: 어떤 수가 8로 나누어떨어지는지 확인하려면 마지막 3자리 숫자만 검사하면 됩니다.3의 배수 판별: 각

이 튜토리얼에서는 길이가 N인 연결 리스트 A와 정수 K가 주어졌을 때, 크기가 K인 노드 그룹들을 번갈아 가며 역순으로 뒤집는 문제를 다룹니다. 여기서 N은 K로 나누어떨어진다는 조건이 있습니다. 함수의 첫 번째 인자는 연결 리스트 A의 헤드 포인터이고, 두 번째 인자는 정수 K입니다. 입력 예시 5 -> 6 -> 2 -> 8 -> 5 -> 2 -> 4 -> 8 -> 9 -> 6 -> null, K = 2 출력 6 -> 5 -> 2 -> 8 -> 2 -&

신장 트리(Spanning Tree)는 그래프의 모든 정점을 연결하는, 연결된 무방향 그래프의 부분 그래프입니다. 하나의 그래프에는 여러 개의 신장 트리가 존재할 수 있으며, 그중 최소 신장 트리(MST, Minimum Spanning Tree)는 다른 모든 신장 트리와 비교해 같거나 더 작은 가중치의 합을 가집니다. 각 간선에는 가중치가 할당되고, 그 합이 해당 신장 트리의 총 가중치가 됩니다. 그래프의 정점 수를 V라고 할 때, 최소 신장 트리는 항상 (V − 1)개의 간선으로 구성됩니다. 크루스칼(Kruskal) 알고리즘으로

이진 트리와 이진 탐색 트리(BST)의 개념 이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드, 즉 왼쪽 자식과 오른쪽 자식만을 가질 수 있는 트리 구조입니다. 트리 구조는 데이터를 계층적으로 표현하는 대표적인 방법입니다. 그중에서도 이진 탐색 트리(Binary Search Tree, BST)는 다음 조건을 만족하는 특수한 형태의 이진 트리입니다. 왼쪽 자식 노드는 항상 부모 노드보다 작은 값을 가집니다. 오른쪽 자식 노드는 항상 부모 노드보다 큰 값을 가집니다. 문제 정의: 이진 트리에서 가장 큰 BST

Madam이나 racecar처럼 거꾸로 읽어도 앞에서 읽은 것과 똑같은 단어를 회문(palindrome)이라고 부릅니다.문자열들의 집합 또는 리스트가 주어졌을 때, 리스트 안의 어떤 두 문자열을 서로 연결했을 때 회문을 만들 수 있는지 확인하는 C++ 코드를 작성해야 합니다. 그런 쌍이 존재하면 Yes를, 존재하지 않으면 No를 출력하면 됩니다.이 튜토리얼에서는 입력으로 문자열 배열이 주어지고, 그에 따라 문자열 값이 출력됩니다.입력 예시list[] = {flat, tea, chair, ptalf, tea}출력Yesflat과 pta

병렬 배열(Parallel Array)은 구조체 배열(Array of Structures)이라고도 불리며, 여러 개의 배열을 하나의 논리적 레코드처럼 다루는 프로그래밍 기법입니다.병렬 배열이란?정의 — 병렬 배열은 여러 개의 배열로 구성되며, 각 배열의 i번째 요소들이 서로 밀접하게 연관되어 하나의 개체(entity)를 이루는 구조를 말합니다. 배열은 C++ 언어의 가장 기본적인 기능 중 하나로, 병렬 배열을 활용하면 두 개 이상의 배열을 함께 비교하고 관리할 수 있습니다.예를 들어,first_name = [John, Dexter,

파티션 문제(Partition Problem)는 주어진 배열을 두 개의 부분집합으로 나눌 수 있는지, 그리고 나누어진 두 부분집합에 속한 원소들의 합이 정확히 같은지를 판단하는 문제입니다. 이 문제는 부분집합 합 문제(Subset Sum Problem)의 변형이며, 부분집합 합 문제는 다시 배낭 문제(Knapsack Problem)의 변형에 해당합니다. 조건이 충족되면 Yes, 그렇지 않으면 No를 출력해야 합니다. 입력 예시 arr[] = {6, 4, 8, 12, 15} 위 배열의 전체 합은 6 + 4 + 8 + 12 + 15

문제 개요최대 5번까지 사용할 수 있는 배터리 n개가 있다고 가정해 봅시다. 배터리 3개가 필요한 기기들이 있으며, 기기를 한 번 사용할 때마다 사용된 배터리의 사용 횟수가 1씩 증가합니다. 기기를 k번 사용해야 한다면, 이를 구동하기 위해 만들 수 있는 배터리 조합이 몇 개인지 구해야 합니다.단, 하나의 배터리는 두 개의 기기에서 동시에 사용될 수 없으며, 이미 5번 사용된 배터리는 더 이상 포함될 수 없습니다. 각 배터리의 현재 사용 횟수는 배열 batt에 주어집니다.예를 들어 입력이 n = 6, k = 2, batt = {2,

두 명의 플레이어가 참여하는 n라운드 게임이 있다고 가정해 보겠습니다. 각 라운드의 점수는 scores 배열에 담겨 있으며, 각 요소는 {P1 점수, P2 점수} 형태로 구성됩니다. 매 라운드마다 더 높은 점수를 기록한 플레이어가 해당 라운드에서 승리하고, 더 많은 라운드를 이긴 플레이어가 최종적으로 게임에서 승리합니다. 만약 두 플레이어가 이긴 라운드 수가 같다면 무승부(Draw)로 처리됩니다.따라서 우리에게 주어진 과제는 라운드별 점수 데이터를 바탕으로 최종적으로 누가 게임에서 승리했는지 판별하는 것입니다.예를 들어 입력이 다음

n쌍의 상자를 정사각형 모양의 컨테이너에 실어 보내야 한다고 가정해 봅시다. 각 상자 쌍의 크기는 (a, b) 형태의 순서쌍으로 주어지며, 이 값들은 dimensions 배열에 담겨 있습니다. 상자들을 위로 쌓을 수는 없고, 나란히 배치해야 할 때 각 쌍의 상자가 컨테이너 안에서 차지하게 되는 면적을 구하는 것이 우리의 과제입니다.여기서 핵심은 두 상자를 긴 변을 세로로 세워 나란히 놓으면, 컨테이너의 높이는 max(a, b)가 되고 전체 폭은 2 × min(a, b)가 된다는 점입니다. 정사각형 컨테이너의 한 변의 길이는 이 두