개요본 문서에서는 빈 칸(_)의 위치 교환 규칙에 따라 한 문자열을 다른 문자열로 변환할 때 필요한 최소 이동 횟수를 C++의 너비 우선 탐색(BFS)으로 구하는 방법을 다룹니다. 상태 공간을 그래프처럼 탐색하는 대표적인 유형의 문제이므로, BFS와 방문 처리 맵을 함께 활용하는 접근 방식을 자연스럽게 익힐 수 있습니다.문제 설명두 문자열 str1과 str2가 주어집니다. 두 문자열은 모두 a와 b 문자로만 구성되어 있으며 길이가 서로 같고, 각 문자열에는 정확히 하나의 _(빈 칸)가 포함되어 있습니다.목표는 아래의 연산들을 최소

문제 설명크기가 N인 배열이 주어지며, 각 인덱스는 하나의 바구니(bucket)를 나타내고 해당 위치에는 배달해야 할 항목들이 담겨 있습니다. 모든 항목을 K번의 이동(tour) 안에 배달해야 하며, 한 번의 이동에서는 오직 하나의 바구니에서만 항목을 꺼낼 수 있습니다. 이때 목표는 모든 항목을 K번의 이동 안에 배달하기 위해 한 번의 이동당 최소 몇 개의 항목을 배송해야 하는지 구하는 것입니다.예시항목이 {1, 3, 5, 7, 9}개씩 담긴 5개의 바구니와 10번의 이동 기회가 주어졌다고 가정해 보겠습니다. 한 번에 3개씩 배달하

문제 설명정수 n이 주어졌을 때, 알파벳 소문자를 각각 a = 1, b = 2, c = 3, ..., z = 26과 같은 값으로 대응시킨다고 가정해 봅시다. 이때 이 알파벳들의 값을 합하여 정확히 n이 되도록 만들기 위해 필요한 최소한의 글자 수를 구하는 것이 과제입니다.예시n = 23인 경우 → 출력: 1 (w 한 글자로 표현 가능)n = 72인 경우 → 출력: 3 (26 + 26 + 20)예를 들어 n이 23이라면 w라는 한 글자만으로 값을 만들 수 있으므로 필요한 글자 수는 1입니다. 반면 n이 72라면 z(26) 두 개와 t

문제 설명 시험에 N개의 문제가 있고, 학급에는 총 K명의 학생이 있습니다. 이 가운데 N명의 학생은 각자 정확히 한 문제씩만 알고 있으며, 한 통의 메일에는 최대 X개의 문제까지 담을 수 있습니다. 목표는 학급의 모든 학생이 N개의 문제 전부를 알게 만드는 것이며, 이때 필요한 최소 메일 수를 구하는 것입니다. 예를 들어 N = 3, K = 3, X = 1인 경우 총 6통의 메일이 필요합니다. 학생 1이 자신의 문제를 학생 2와 학생 3에게 보냅니다 (2통). 학생 2와 학생 3도 마찬가지로 자신의 문제를 나머지 학생들에게 보내

문제 개요N개의 요소로 이루어진 배열과 정수 K가 주어집니다. 이 배열에는 다음과 같은 연산을 원하는 만큼 반복해서 수행할 수 있습니다.배열의 K번째 요소를 배열의 맨 뒤에 삽입하고, 동시에 배열의 첫 번째 요소를 삭제합니다.목표는 이 연산을 활용해 배열의 모든 요소를 동일한 값으로 만드는 데 필요한 최소 이동 횟수를 구하는 것입니다. 만약 어떻게 해도 모든 요소를 같게 만들 수 없다면 -1을 출력해야 합니다.예시배열이 arr[] = {1, 2, 3, 4, 5, 6}이고 k = 6인 경우, 최소 5번의 이동이 필요합니다. Move-

문제 정의AVL 트리는 스스로 균형을 유지하는 이진 탐색 트리(BST)의 일종으로, 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 반드시 -1, 0, 1 중 하나여야 합니다. 이번 글에서는 AVL 트리의 높이가 주어졌을 때, 그 트리가 가질 수 있는 최소 노드 개수를 구하는 방법을 알아보겠습니다.높이(height) = 0이면 AVL 트리는 1개의 노드를 가질 수 있습니다.높이(height) = 5이면 AVL 트리는 최소 20개의 노드를 가져야 합니다.알고리즘: 점화식 세우기AVL 트리의 높이 균형 속성에 따르면, 어떤

문제 설명 크기가 N인 배열이 주어지며, 배열의 각 요소는 1 또는 0입니다. 이 문제의 목표는 모든 요소를 0으로 만들기 위해 수행해야 하는 최소 연산 횟수를 구하는 것입니다. 수행할 수 있는 연산은 다음과 같습니다. 어떤 요소가 1이라면, 그 값을 0으로 변경할 수 있습니다. 이때 다음 규칙이 적용됩니다. 바로 다음에 오는 연속된 요소가 1이면, 해당 요소도 자동으로 0으로 변환됩니다. 바로 다음에 오는 연속된 요소가 이미 0이라면, 아무런 변화도 일어나지 않습니다. 예를 들어, 다음 배열을 살펴보겠습니다. arr[] =

문제 설명정수 배열 arr이 주어졌을 때, 배열의 모든 요소를 삭제하는 데 필요한 최소 연산 횟수를 구하는 것이 과제입니다. 단, 요소를 삭제할 때 다음과 같은 제약 조건이 적용됩니다.배열에서 임의의 요소 하나를 선택하면, 그 요소로 나누어 떨어지는 모든 요소를 한 번에 배열에서 제거할 수 있습니다.예를 들어 arr[] = {2, 4, 15, 10, 8, 5, 3}인 경우, 모든 요소를 삭제하는 데 3번의 연산이 필요합니다.2를 선택하면 {2, 4, 10, 8}이 삭제됩니다.5를 선택하면 {5, 15}가 삭제됩니다.3을 선택하면 {

문제 설명이진 문자열 str이 주어졌을 때, 이 문자열이 나타내는 수를 만들기 위해 수행해야 하는 최소 연산 횟수를 구하는 문제입니다. 사용할 수 있는 연산은 다음 두 가지뿐입니다.2x 더하기2x 빼기예를 들어 이진 문자열이 1000이라면 23을 한 번 더하는 연산만으로 충분하므로 최소 연산 횟수는 1입니다.반면 이진 문자열이 101이라면 22와 20을 각각 더해야 하므로 최소 연산 횟수는 2입니다.접근 방법: 동적 프로그래밍(DP)단순히 1인 비트의 개수를 세는 것만으로는 최적해를 보장할 수 없습니다. 예를 들어 111(= 7)의

문제 개요 N페이지로 구성된 책이 주어졌을 때, 원하는 페이지 K에 도달하기 위해 최소 몇 번의 페이지를 넘겨야 하는지 계산하는 것이 이번 문제의 목표입니다. 페이지 넘김은 책의 앞쪽(1페이지부터)에서 시작할 수도 있고, 뒤쪽(N페이지부터)에서 시작할 수도 있습니다. 각 페이지는 앞면과 뒷면 두 면으로 이루어져 있지만, 첫 번째 페이지는 뒷면만 존재하며 마지막 페이지 역시 전체 페이지 수에 따라 뒷면만 있을 수 있습니다. 예를 들어 N = 5, K = 4인 경우를 살펴보겠습니다. 이때 필요한 최소 페이지 넘김 횟수는 1회입니다

문제 정의하나의 숫자 N이 주어졌을 때, N을 여러 개의 회문(Palindrome)의 합으로 표현하기 위해 필요한 최소한의 회문 개수를 구하는 것이 목표입니다.회문이란 앞에서 읽으나 뒤에서 읽으나 같은 숫자를 의미합니다. 예를 들어 7, 8, 11, 121 등이 모두 회문입니다.예시: N = 15인 경우, 15 = 8 + 7처럼 두 개의 회문(8과 7)만 있으면 표현할 수 있습니다. 따라서 필요한 최소 회문 개수는 2입니다.접근 방법 및 알고리즘이 문제는 크게 두 단계로 나누어 해결할 수 있습니다.N 이하의 모든 회문을 오름차순으로

문제 정의 기차역에 도착하는 모든 열차의 도착 시간과 출발 시간이 주어졌을 때, 어떤 열차도 대기하지 않고 바로 진입할 수 있도록 하기 위해 필요한 최소 플랫폼 수를 구하는 문제입니다. 입력으로는 열차의 도착 시간과 출발 시간을 각각 담고 있는 두 개의 배열이 제공됩니다. 아래 입력 예시의 경우 최소 3개의 플랫폼이 필요합니다. 열차도착 시간출발 시간 열차-109:0009:15 열차-209:3511:45 열차-309:4011:05 열차-411:0012:00 열차-514:3018:15 열차-618:0019:00 알고리즘

문제 설명데카르트 좌표 평면에 N개의 점이 주어졌을 때, 남은 모든 점이 임의의 축(X축 또는 Y축)의 한쪽 면에 위치하도록 만들기 위해 제거해야 하는 점의 최소 개수를 구하는 문제입니다.예를 들어 입력이 {(10, 5), (-2, -5), (13, 8), (-14, 7)}라고 해보겠습니다. 이때 점 (-2, -5) 하나만 제거하면 나머지 세 점이 모두 X축 위쪽에 위치하게 됩니다.따라서 정답은 1입니다.접근 방법핵심 아이디어는 매우 단순합니다. 어떤 축의 한쪽 면에 점들을 남기려면, 반대편에 있는 점들을 모두 제거해야 합니다. 따

문제 설명두 개의 양의 정수 N과 X가 주어집니다. 이때 N을 X의 거듭제곱들의 합(X0 + X1 + … + Xn)으로 표현하되, 사용되는 거듭제곱 항의 개수가 최소가 되도록 만드는 것이 목표입니다.즉, 합이 N과 같아지도록 하기 위해 사용해야 하는 X의 거듭제곱 항의 최소 개수를 출력하면 됩니다.예를 들어 N = 15이고 X = 3이라면, 3의 거듭제곱 3개를 사용하여 다음과 같이 표현할 수 있습니다.15 = (32 + 31 + 31)알고리즘다음 공식을 활용하면 최종 결과를 손쉽게 계산할 수 있습니다.1. x = 1인 경우, 답은

양의 정수 n이 주어졌을 때, 각 요소의 합이 정확히 n이 되는 모든 양의 정수 조합을 찾아야 합니다. 이때 순서만 다른 경우는 같은 조합으로 간주하므로, 순열(permutation)이 아닌 조합(combination)만을 대상으로 합니다.예를 들어 n = 4라면 가능한 조합은 [1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3], [4]의 다섯 가지입니다.접근 방법이 문제는 재귀(recursion)를 이용해 효율적으로 해결할 수 있습니다. 조합을 저장할 배열을 하나 준비한 뒤, 재귀 호출을 통해 배열을 차례대로

개요이 튜토리얼에서는 C++을 사용하여 이진 트리(binary tree)에서 주어진 두 레벨 번호 사이에 있는 모든 노드를 출력하는 프로그램을 구현하는 방법을 살펴봅니다.문제의 정의는 다음과 같습니다. 하나의 이진 트리와 함께 낮은 레벨(low)과 높은 레벨(high)이 주어졌을 때, 해당 범위에 포함되는 레벨에 속한 모든 노드의 값을 출력해야 합니다.접근 방법이 문제는 큐(queue) 기반의 레벨 순회(level order traversal)를 활용하여 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.각 레벨의 끝

문제 정의정수 배열이 하나 주어집니다. 이 배열의 부분 집합(subset)으로 만들 수 있는 모든 고유한 합(distinct sum)을 구한 뒤, 오름차순으로 출력하는 것이 목표입니다. 단, 배열 원소들의 총합은 작다고 가정합니다.예를 들어 배열이 [1, 2, 3]일 때 가능한 부분 집합은 {}, {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3}, {1, 2, 3}이며, 각각의 합은 순서대로 0, 1, 2, 3, 3, 5, 4, 6입니다. 여기서 중복된 값(3)을 하나로 묶고 정렬하면 최종 출력은 0, 1, 2,

이 튜토리얼에서는 주어진 이진 트리의 상위 뷰(Top View)에 나타나는 모든 노드를 출력하는 프로그램을 다룹니다. 상위 뷰란 무엇인가? 이진 트리에서 어떤 노드가 상위 뷰에 나타난다는 것은, 트리를 위에서 내려다볼 때 해당 노드가 자신의 수평 거리(horizontal distance) 위치에서 가장 먼저 보이는 노드, 즉 그 위치에서 가장 위쪽에 있는 노드라는 의미입니다. 수평 거리는 다음과 같이 정의됩니다. 노드 x의 왼쪽 자식 노드의 수평 거리 = x - 1 노드 x의 오른쪽 자식 노드의 수평 거리 = x + 1 접근

이번 글에서는 주어진 집합의 모든 고유한 부분집합을 출력하는 방법을 알아보겠습니다. 예를 들어 집합이 {1, 2, 3}이라면 부분집합은 {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}이 됩니다.이렇게 한 집합의 모든 부분집합의 집합을 멱집합(Power Set)이라고 하며, 원소가 n개인 집합의 멱집합은 정확히 2n개의 부분집합을 가집니다.접근 방법: 비트마스킹가장 간단한 방법은 비트 연산을 활용하는 것입니다. 0부터 2n-1까지의 숫자를 하나씩 순회하면서, 현재 카운터 값의 i번째 비트

문제 소개 이 튜토리얼에서는 연속된 두 수는 서로소(coprime)가 아니면서, 연속된 세 수는 반드시 서로소가 되도록 수열을 출력하는 프로그램을 C++로 구현하는 방법을 알아봅니다. 문제를 정리하면 다음과 같습니다. 정수 N이 주어졌을 때, 10억(109)보다 작은 N개의 정수를 출력해야 하며, 출력 결과는 아래 두 조건을 동시에 만족해야 합니다. 조건 1. 이웃한 두 수의 최대공약수(GCD)는 1이 아니어야 합니다. 즉, 인접한 두 수는 반드시 공약수를 가져야 합니다.조건 2. 이웃한 세 수의 최대공약수는 1이어야 합니다. 즉