이 튜토리얼에서는 C++을 사용해 이진 행렬(binary matrix)에서 1로 둘러싸여 차단된 0의 개수를 구하는 프로그램을 다룹니다.0과 1로만 이루어진 이진 행렬이 주어졌을 때, 우리의 목표는 1에 의해 완전히 둘러싸여 행렬의 경계와 연결되지 않은 모든 0을 찾아 그 개수를 세는 것입니다.접근 방법이 문제는 DFS(깊이 우선 탐색)를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.행렬의 네 가장자리(첫 번째 행, 마지막 행, 첫 번째 열, 마지막 열)에 위치한 0에서 DFS를 시작합니다.DFS를 통해

이 튜토리얼에서는 정수 배열과 값 k가 주어졌을 때, 서로의 차이가 정확히 k가 되는 모든 고유한 쌍(distinct pairs)의 개수를 구하는 프로그램을 C++로 작성하는 방법을 알아보겠습니다.문제 이해하기예를 들어 배열이 {1, 5, 3, 4, 2}이고 k = 3이라면, 차이가 3이 되는 쌍은 (1, 4)와 (2, 5) 두 개입니다. 따라서 결과는 2가 됩니다.가장 기본적인 접근 방식은 배열의 모든 요소를 하나씩 선택하고, 나머지 요소들과 비교하여 차이가 k인지 확인하는 것입니다. 이 방법은 중첩 반복문을 사용하며 시간 복잡도

문제 소개이 글에서는 배열 내 요소 중 첫 등장 이후 최소 K번 이상 다시 나타나는 요소의 개수를 구하는 프로그램을 C++로 작성해 보겠습니다.문제의 조건은 다음과 같습니다. 정수형 배열과 값 k가 주어졌을 때, 각 요소를 기준으로 그 이후에 위치한 요소들 가운데 해당 요소와 같은 값이 k번 이상 등장하면 그 요소를 카운트합니다.접근 방법이 문제는 다음과 같은 단계로 해결할 수 있습니다.배열의 각 요소를 순회하면서 이미 확인한 적 있는 값인지 검사하여 중복 계산을 방지합니다.처음 만나는 값이라면, 그 뒤에 있는 요소들을 탐색하며 같

이 튜토리얼에서는 배열에서 만들 수 있는 증가하는 부분 수열(increasing subsequence)의 개수를 구하는 방법을 다룹니다.문제의 조건은 다음과 같습니다. 0부터 9까지의 숫자로 이루어진 배열이 주어지며, 우리는 배열 내에서 다음 원소가 항상 이전 원소보다 큰 모든 부분 수열의 개수를 세어야 합니다.접근 방식이 문제는 동적 계획법(DP)을 활용해 효율적으로 해결할 수 있습니다. 각 숫자(0~9)별로 해당 숫자로 끝나는 증가 부분 수열의 개수를 저장하는 카운트 배열을 사용합니다.배열을 왼쪽에서 오른쪽으로 순회하면서, 현재

이 튜토리얼에서는 C++를 사용해 배열에 포함된 짝수 요소와 홀수 요소의 개수를 구하는 프로그램을 다룹니다.정수형 배열이 하나 주어졌을 때, 우리가 해야 할 작업은 해당 배열을 순회하면서 짝수와 홀수가 각각 몇 개인지 계산하는 것입니다. 이 문제는 나머지 연산자(%)만 활용하면 아주 간단하게 해결할 수 있습니다.접근 방법핵심 로직은 다음과 같습니다.배열의 처음부터 끝까지 요소를 하나씩 순회합니다.각 요소를 2로 나눈 나머지가 0이 아니면 홀수, 0이면 짝수로 판별합니다.판별 결과에 따라 홀수 카운트 또는 짝수 카운트를 증가시킵니다.

이 튜토리얼에서는 1부터 n까지의 숫자 중에서 자릿수에 4가 포함된 숫자의 개수를 구하는 프로그램을 다룹니다.하나의 숫자 n이 주어지면, 우리의 목표는 그 범위 안에서 4를 자릿수 중 하나로 가지는 모든 숫자를 세어 그 결과를 출력하는 것입니다.예를 들어 n이 328이라면, 4, 14, 24, 34, 40~49 등처럼 어느 자리든 4가 들어간 숫자들을 모두 찾아 합산해야 합니다.구현 예제#include<iostream> using namespace std; bool has4(int x); // 주어진 범위에서 조건을 만족

이진 탐색 트리 반복자란?이진 트리를 위한 반복자(iterator)를 만든다고 가정해 봅시다. 이 반복자는 두 가지 핵심 메서드를 제공해야 합니다.next(): 다음으로 작은 원소를 반환하는 메서드hasNext(): 다음 원소가 존재하는지 여부를 불리언(Boolean) 값으로 반환하는 메서드예를 들어 다음과 같은 트리가 있다고 가정하겠습니다.함수 호출 순서가 [next(), next(), hasNext(), next(), hasNext(), next(), hasNext(), next(), hasNext()]라면, 출력 결과는 [3,

문제 개요이진 트리가 하나 주어져 있고, 이 트리를 오른쪽 측면에서 바라본다고 가정해 봅시다. 그러면 각 깊이(레벨)마다 가장 오른쪽에 위치한 노드만 눈에 보이게 됩니다. 이 문제의 목표는 그렇게 보이는 노드들의 값을 순서대로 출력하는 것입니다.예를 들어 다음과 같은 트리가 있다고 합시다.이 트리를 오른쪽에서 보면 레벨 순서대로 1 → 3 → 4가 차례로 보입니다.접근 방법: DFS(깊이 우선 탐색) 활용이 문제는 깊이 우선 탐색(DFS)으로 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 오른쪽 자식을 왼쪽 자식보다 먼저 방문하는

문제 개요당신은 전문 도둑이라고 상상해 봅시다. 한 거리에 늘어선 집들을 털 계획을 세우고 있는데, 각 집에는 일정 금액의 돈이 보관되어 있습니다. 이번 문제의 특징은 모든 집이 원형으로 배치되어 있다는 점입니다. 즉, 첫 번째 집과 마지막 집 역시 서로 이웃입니다.여기서 주의할 점은 인접한 집들끼리 보안 시스템이 연결되어 있어, 같은 밤에 연속된 두 집을 털면 자동으로 경찰에 신고된다는 사실입니다. 따라서 각 집의 돈의 양을 나타내는 정수 배열이 주어졌을 때, 경찰에 들키지 않고 한밤중에 훔칠 수 있는 최대 금액을 구해야 합니다.

문제 소개 1부터 9까지의 숫자만 사용하여, 합이 특정 값 n이 되는 k개의 숫자 조합을 모두 찾는 문제입니다. 이때 각 조합은 중복 없는 고유한 숫자 집합이어야 하며, 사용되는 모든 숫자는 양수여야 합니다. 또한 동일한 조합이 결과에 두 번 이상 나타나서는 안 됩니다. 예를 들어 k = 3, n = 9가 주어지면 가능한 조합은 [[1,2,6], [1,3,5], [2,3,4]] 세 가지입니다. 알고리즘 접근 방식 이 문제는 대표적인 백트래킹(backtracking) 기법으로 해결할 수 있습니다. 재귀 함수 solve()를 정의하고

완전 이진 트리(Complete Binary Tree)가 주어졌을 때, 전체 노드의 개수를 세는 문제입니다. 예를 들어 다음과 같은 트리가 있다고 가정해 보겠습니다.이 경우 출력 결과는 6이 됩니다.문제 해결 접근 방식완전 이진 트리는 마지막 레벨을 제외한 모든 레벨이 꽉 차 있고, 마지막 레벨의 노드들은 왼쪽부터 채워지는 특성이 있습니다. 이 특성을 활용하면 단순히 모든 노드를 순회하는 것보다 훨씬 효율적으로 노드 개수를 구할 수 있습니다.핵심 아이디어는 다음과 같습니다. 트리의 왼쪽 끝까지의 높이와 오른쪽 끝까지의 높이를 각각

양의 정수 n이 주어졌을 때, 그 합이 정확히 n이 되도록 만드는 완전 제곱수(perfect square)의 최소 개수를 구하는 문제입니다. 예를 들어 n이 13이라면 13 = 9 + 4로 표현할 수 있으므로, 필요한 완전 제곱수의 개수는 2개입니다.문제 접근 방법이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 j를 만들기 위해 필요한 최소 완전 제곱수의 개수를 작은 값부터 차례로 계산해 나가는 것입니다. 알고리즘의 단계는 다음과 같습니다.길이가 n + 1인 동

문제 개요배열이 하나 주어지며, i번째 원소는 i번째 날의 특정 주식 가격을 나타냅니다. 우리는 이 배열에서 얻을 수 있는 최대 이익을 계산하는 알고리즘을 설계해야 합니다. 거래 횟수에는 제한이 없어서 주식을 여러 번 사고팔 수 있지만, 다음 두 가지 규칙을 반드시 지켜야 합니다.동시에 여러 거래를 진행할 수 없습니다. 즉, 새로 매수하기 전에 보유 중인 주식을 반드시 먼저 매도해야 합니다.주식을 매도한 직후 다음 날에는 매수할 수 없습니다. 즉, 하루의 쿨다운(휴식) 기간이 필요합니다.예를 들어 입력이 [1,2,3,0,2]라면 출

문제 이해하기 이 문제에서는 양의 정수로 이루어진 배열과 숫자 k가 주어집니다. 우리의 목표는 주어진 크기(k)를 가지면서 서로 겹치지 않는 두 부분 배열(subarray)의 합이 최대가 되도록 만드는 프로그램을 작성하는 것입니다. 즉, 크기가 k인 서로 겹치지 않는(서로 다른) 두 부분 배열을 찾아 그 합이 최대가 되도록 출력해야 합니다. 예시를 통해 문제를 자세히 살펴보겠습니다. 입력 array = {7, 1, 6, 9, 2} , k = 2 출력 {7, 1} , {6, 9} 설명 크기가 2인 모든 부분 배열: {7, 1} : 합

이 문제에서는 하나의 배열이 주어지며, 우리의 과제는 배열에서 최대 삼중항 합(maximum triplet sum)을 찾는 프로그램을 작성하는 것입니다. 즉, 세 개의 원소를 골랐을 때 그 합이 가장 커지는 조합을 찾아야 합니다.문제 이해하기예시를 통해 문제를 살펴보겠습니다.입력 − array = {4, 6, 1, 2}출력 − 12설명 −배열의 모든 삼중항 : (4, 6, 1) = 4+6+1 = 11 (4, 6, 2) = 4+6+2 = 12 (4, 1, 2) = 4+1+2 = 7 (6, 1, 2) = 6+1+2 = 9 따라서 최대

문제 설명이 문제에서는 정수 배열과 정수 K가 주어집니다. 우리의 과제는 중복되지 않은(고유한) 요소만을 대상으로, 크기가 K인 모든 부분 배열에서 최대 고유 요소를 찾아 출력하는 프로그램을 작성하는 것입니다.예제를 통해 문제를 살펴보겠습니다.입력 −array = {4, 1, 1, 3, 3}k = 3출력 −4 3 1설명 −크기가 3인 부분 배열{4, 1, 1} → 고유 요소 중 최댓값 = 4{1, 1, 3} → 고유 요소 중 최댓값 = 3{1, 3, 3} → 고유 요소 중 최댓값 = 1해결 접근 방법가장 단순한 방법은 두 개의 반복

이 문제에서는 1부터 n 사이의 값을 가지는 n개의 정수로 이루어진 배열이 주어집니다. 우리가 해야 할 작업은 다음 식의 최댓값을 찾는 프로그램을 작성하는 것입니다.|arr[0] – arr[1]| + |arr[1] – arr[2]| + … + |arr[n – 2] – arr[n – 1]|문제 이해하기예제를 통해 문제를 살펴보겠습니다.입력 − array = {1, 2, 3}출력 − 3설명 −최대 합은|1-3| + |2-1| = 3해결 접근 방식이 문제를 해결하는 가장 단순한 방법은 배열의 모든 순열(permutation)을 생성하고,

이 문제에서는 n개의 정수로 이루어진 배열이 주어지며, 우리의 목표는 |arr[i] - arr[j]| + |i - j| 식의 최댓값을 찾는 프로그램을 작성하는 것입니다.문제 이해를 위한 예시입력: array = {4, 1, 2}출력: 4설명:|arr[0] - arr[1]| + |0-1| = |4-1| + |-1| = 3 + 1 = 4|arr[0] - arr[2]| + |0-2| = |4-2| + |-2| = 2 + 2 = 4|arr[1] - arr[2]| + |1-2| = |1-2| + |1-2| = 1 + 1 = 2해결 방법 1:

이 문제에서는 n개의 원소로 이루어진 배열이 주어지며, 주어진 배열에서 arr[i] % arr[j]의 최댓값을 찾는 프로그램을 작성해야 합니다.쉽게 말해, 배열의 두 원소를 나누었을 때 나올 수 있는 나머지 중 가장 큰 값을 구하는 것이 목표입니다.문제 이해를 위한 예시입력: array[] = {3, 6, 9, 2, 1}출력: 6설명:3%3 = 0; 3%6 = 3; 3%9 = 3; 3%2 = 1; 3%1 = 06%3 = 0; 6%6 = 0; 6%9 = 6; 6%2 = 0; 6%1 = 09%3 = 0; 9%6 = 3; 9%9 = 0;

이 문제에서는 정수로 이루어진 배열이 주어지며, 우리의 과제는 배열에서 선택할 수 있는 모든 삼중항(triplet)의 XOR 연산 결과 중 최댓값을 찾는 것입니다.문제 이해를 위한 예시입력 − array = {5, 6, 1, 2}출력 − 6설명 −가능한 모든 삼중항의 XOR 값:5^6^1 = 25^6^2 = 15^1^2 = 66^1^2 = 5위 결과에서 가장 큰 값은 6이므로, 정답은 6이 됩니다.해결 접근 방법1. 단순 무차별 대입 방식 (Brute Force)가장 직관적인 방법은 가능한 모든 삼중항 조합에 대해 XOR 값을 계산