트리의 간선 목록이 [u, v] 형태로 주어져 있다고 가정해 보겠습니다. 이는 노드 u와 노드 v 사이에 무방향 간선이 하나 존재한다는 의미입니다. 추가로 두 값 x와 y가 주어지며, 우리는 노드 x에 위치하고 상대방은 노드 y에 위치합니다. 첫 라운드에는 우리가 먼저 이동하고, 다음 라운드에는 상대방이 이동하는 식으로 번갈아 가며 게임이 진행됩니다. 단, 상대방은 자신의 차례에 이동하지 않고 제자리에 머무는 것을 선택할 수도 있습니다. 우리의 목표는 상대방을 반드시 잡기 위해 필요한 최소 라운드 수를 구하는 것입니다. 예를 들어

문제 설명각 값이 다음과 같은 의미를 가지는 2차원 행렬이 주어졌다고 가정해 봅시다.0: 빈 칸(이동 가능)1: 벽(지나갈 수 없음)2: 사람사람은 한 번의 시간 단위 동안 위, 아래, 왼쪽, 오른쪽 네 방향 중 하나로 이동하거나 제자리에 머무를 수 있습니다. 목표는 모든 사람이 만나는 데 걸리는 시간을 최소화하는 이동 가능한 칸을 찾아, 그 최소 시간을 반환하는 것입니다. 이때 여러 명이 같은 빈 칸을 동시에 지나갈 수 있으며, 임의의 두 사람 사이에는 항상 경로가 존재한다고 가정합니다.예시입력 행렬이 다음과 같다면:2010100

이진 트리가 주어졌을 때, 해당 트리의 탑 뷰(top view)를 구하는 문제입니다. 탑 뷰란 트리를 위에서 아래로 내려다볼 때 보이는 노드들을 의미하며, 결과는 반드시 왼쪽에서 오른쪽 순서로 정렬되어야 합니다.예를 들어 다음과 같은 트리가 입력으로 주어지면 출력은 [3, 5, 8, 6, 9]가 됩니다. 노드 3이 노드 2의 바로 위에 있고, 노드 5가 노드 7의 바로 위에 있기 때문에 2와 7은 위에서 볼 수 없습니다.접근 방법: BFS와 수평 좌표 활용이 문제는 너비 우선 탐색(BFS)과 각 노드에 수평 좌표를 부여하는 방식으로

문제 개요도미노(Domino)와 트로미노(Tromino)라는 두 가지 모양의 조각이 있다고 가정해 보겠습니다. 도미노는 2×1 크기의 직사각형 모양이고, 트로미노는 L자 형태의 모양입니다. 두 조각은 아래 그림과 같이 회전하여 사용할 수 있습니다.숫자 n이 주어졌을 때, 이 두 종류의 조각으로 2×n 크기의 보드를 완전히 채우는 배치의 가짓수를 구해야 합니다. 타일링 문제에서는 보드의 모든 칸이 반드시 하나의 타일로 덮여 있어야 한다는 점에 유의하세요.예시입력이 3이라면 출력은 5가 됩니다. 가능한 배치는 다음과 같습니다.[XYZ

문제 설명소문자로만 이루어진 두 문자열 s와 t가 주어집니다. 이때 문자열 s의 부분 수열(subsequence) 중 문자열 t와 정확히 일치하는 것의 개수를 구해야 합니다. 답이 매우 커질 수 있으므로, 결과는 10^9 + 7로 나눈 나머지를 반환합니다.예를 들어 입력이 s = abbd, t = bd라면 출력은 2가 됩니다. bd를 만들 수 있는 부분 수열이 두 가지 존재하기 때문입니다.s[1] 다음에 s[3]을 이어 붙인 경우s[2] 다음에 s[3]을 이어 붙인 경우해결 전략: 동적 계획법(DP)이 문제는 대표적인 동적 계획법(

문자열 s가 주어졌을 때, s에서 만들 수 있는 비어 있지 않은 고유한(서로 다른) 부분 수열의 개수를 구하는 문제입니다. 답이 매우 커질 수 있으므로 최종 결과는 109 + 7로 나눈 나머지를 반환해야 합니다.예를 들어 입력이 s = xxy라면 출력은 5가 됩니다. x, xx, xy, y, xxy의 다섯 가지 부분 수열이 존재하기 때문입니다.문제 해결 접근 방법이 문제는 동적 계획법(DP)을 활용하면 O(n) 시간에 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.현재까지 만들 수 있는 총 부분 수열의 개수를 re

문제 개요 같은 길이를 가진 두 개의 숫자 리스트 performance와 costs, 그리고 하나의 숫자 k가 주어집니다. 각 직원 i는 performance[i] 수준으로 업무를 수행하며, 최소한 costs[i]만큼의 보수를 받아야 합니다. 이때 k명의 직원을 고용하면서, 그룹 내 다른 직원들과 비교하여 각자의 성과에 비례해 급여를 지급한다는 조건을 만족하는 최소 비용을 구해야 합니다. 입력 예시 예를 들어 performance = [5, 3, 2], costs = [100, 5, 4], k = 2라고 가정해 봅시다. 이 경우

이번 글에서는 FrequencyStack이라는 특별한 스택을 C++로 구성하는 방법을 알아보겠습니다. 이 스택은 다음 두 가지 연산을 지원합니다.append(x): 값 x를 스택에 추가(push)합니다.pop(): 스택에서 가장 자주 등장한(빈도가 가장 높은) 요소를 제거하고 반환합니다. 만약 빈도가 같은 요소가 여러 개 있다면, 그중 스택 최상단(top)에 가장 가까운, 즉 가장 나중에 삽입된 요소를 제거하고 반환합니다.예를 들어 append를 통해 7, 9, 7, 9, 6, 7을 순서대로 삽입한 뒤 pop을 네 번 호출하면, 결

문제 개요숫자 리스트 nums가 주어지고, 리스트 안에서 임의의 부분 리스트(sublist)를 최대 한 번 반전(뒤집기)할 수 있다고 가정해 보겠습니다. 이 연산을 수행한 후, 아래 식으로 표현되는 값의 최댓값을 구하는 것이 목표입니다.Σi=0n−2 |nums[i+1] − nums[i]|예를 들어 입력이 nums = [2, 4, 6]이라면 결과는 6입니다. [4, 6] 구간을 반전하면 리스트가 [2, 6, 4]가 되고, 이때 |2 − 6| + |6 − 4| = 6이 되기 때문입니다.해결 전략이 문제는 모든 반전 구간을 일일이 시도하

최대 스택(Maximum Stack)이란?최대 스택은 일반적인 스택 기능에 더해, 현재 스택에 들어 있는 값들 중 최댓값을 빠르게 조회하거나 제거할 수 있는 자료구조입니다. 이번 글에서는 다음과 같은 연산을 지원하는 최대 스택을 C++로 구현해 보겠습니다.MaxStk() – 최대 스택의 새 인스턴스를 생성합니다.push(val) – val 값을 스택에 삽입합니다.top() – 스택의 가장 위(top)에 있는 요소를 반환합니다.max() – 스택에 있는 요소 중 최댓값을 반환합니다.pop() – 스택의 가장 위에 있는 요소를 제거하고

문제 이해하기 정수 n이 하나 주어졌을 때, n 이하의 양의 정수 중에서 적어도 한 개의 자릿수가 두 번 이상 등장하는 수가 몇 개인지 구하는 것이 이 문제의 목표입니다. 예를 들어 입력이 n = 200이라면 출력은 38이 됩니다. 실제로 11, 22, 33처럼 같은 숫자가 반복되는 수나 100, 101처럼 특정 자릿수가 겹치는 수를 1부터 200까지 세어 보면 정확히 38개가 존재합니다. 풀이 전략: 여집합으로 접근하기 중복 자릿수를 가진 수를 직접 세는 것보다, 전체 개수에서 모든 자릿수가 서로 다른 수의 개수를 빼는 방식이

MedianClass라는 클래스를 구현해야 한다고 가정해 봅시다. 이 클래스에는 다음과 같은 메서드가 포함되어야 합니다.add(value): 데이터 구조에 새로운 값을 추가합니다.median(): 현재 데이터 구조에 저장된 모든 숫자의 중앙값을 계산하여 반환합니다.예를 들어 5, 3, 8을 차례로 추가한 후 중앙값을 조회하면 결과는 5.0입니다. 이어서 9를 추가한 뒤 다시 중앙값을 조회하면 결과는 6.5가 됩니다.해결 접근 방식이 문제는 최대 힙(max-heap) 하나와 최소 힙(min-heap) 하나, 총 두 개의 우선순위 큐를

이 튜토리얼에서는 LCM(최소공배수) 개념을 활용한 프로그램을 작성해 보겠습니다. 목표는 주어진 수 N보다 작거나 같은 세 정수 중에서 LCM이 최대가 되는 조합을 찾는 것입니다. 간단한 예시로 문제를 이해한 뒤, LCM의 개념과 구현 방법을 차례대로 살펴보겠습니다. LCM(최소공배수)이란? LCM(Least Common Multiple, 최소공배수)은 두 수가 공통으로 가지는 배수 중 가장 작은 수를 의미합니다. 두 양의 정수 a와 b의 LCM은 a와 b 모두로 나누어 떨어지는 가장 작은 양의 정수입니다. 특히 두 수가 서로소,

문제 개요이 튜토리얼에서는 신호(signal)가 문자열의 모든 위치(position)에 도달하는 데 걸리는 시간을 계산하는 C++ 프로그램을 작성해 보겠습니다.문제 설명주어진 문자열에는 s와 p 두 종류의 문자만 포함되어 있습니다.s: 신호(signal)를 나타냅니다.p: 아직 신호가 닿지 않은 위치(position)를 나타냅니다.신호는 s에서 시작하여 왼쪽과 오른쪽 양방향으로 동시에 전파되며, 인접한 다음 위치로 이동하는 데 1단위의 시간이 걸린다고 가정합니다. 따라서 우리의 목표는 문자열의 모든 p가 s(신호)로 변환되는 데 필

이 튜토리얼에서는 주어진 문자열에 포함된 날짜들 중 고유한 연도(distinct year)의 개수를 찾는 C++ 프로그램을 작성해 보겠습니다. 여기서는 날짜 형식이 DD/MM/YYYY라고 가정합니다.문제 이해하기먼저 예제를 통해 문제를 살펴보겠습니다.입력 — 날짜가 포함된 문자열: 01/11/2020, 02/12/2020, 그리고 03/10/2019출력 — 2주어진 문자열에는 2020년과 2019년, 총 두 개의 서로 다른 연도가 존재하므로 결과는 2가 됩니다.접근 방법이 문제는 정규식(regex)을 활용하면 간단하게 해결할 수 있

이 튜토리얼에서는 동일한 행렬을 행 우선(row-major) 방식과 열 우선(column-major) 방식으로 각각 배치하여 만든 두 행렬을 더한 뒤, 그 결과 행렬의 자취(trace)를 구하는 프로그램을 작성해 보겠습니다.먼저 자취란 행렬의 주대각선(main diagonal), 즉 왼쪽 위에서 오른쪽 아래로 이어지는 대각선 요소들의 합을 의미합니다.행렬이 만들어지는 과정행렬의 차수(order)가 주어졌을 때 두 가지 방식으로 행렬이 어떻게 형성되는지 살펴보겠습니다.차수(Order) − 3 x 3행 우선(Row Major) 행렬행

개요 이 튜토리얼에서는 주어진 곱(곱셈의 결과값)을 만들 수 있는 두 개의 서로 다른 소수를 찾는 C++ 프로그램을 작성해 보겠습니다. 먼저 간단한 예시부터 살펴볼까요? 입력 − 21 출력 − 3 7 21 = 3 × 7이며, 3과 7은 모두 소수입니다. 이처럼 입력값을 두 소수의 곱으로 분해하는 것이 이번 문제의 핵심입니다. 문제 해결 접근 방법 핵심 아이디어는 간단합니다. 주어진 곱 이하의 모든 소수를 미리 구해두면, 곱이 입력값과 일치하는 두 소수의 쌍을 손쉽게 찾을 수 있습니다. 소수를 효율적으로 판별하

이 튜토리얼에서는 합과 곱이 모두 N과 같은 두 숫자, 즉 x + y = n이면서 동시에 x × y = n을 만족하는 두 수를 찾는 프로그램을 작성해 보겠습니다. 모든 n에 대해 이러한 숫자가 존재하는 것은 아니며, 조건을 만족하는 수가 없을 때는 None을 출력하도록 하겠습니다. 그럼 바로 시작해 보겠습니다. 수학적 접근 방법 주어진 두 값은 각각 이차방정식의 두 근의 합과 곱에 해당합니다. 근과 계수의 관계에 따라 우리가 찾고자 하는 두 수 x, y는 다음 이차방정식의 해가 됩니다. t2 − nt + n = 0 이 방정식의 판별

이 튜토리얼에서는 주어진 두 문자열에서 고유한(distinct) 문자, 즉 두 문자열 중 하나에만 등장하는 문자를 찾는 방법을 배워보겠습니다. 먼저 예제를 살펴볼까요?입력string_one = tutorialspoint string_two = tutorialsworld출력d n p w접근 방식: 해싱(Hashing)이 문제는 중첩 반복문을 사용하는 것보다 맵(map)을 이용한 해싱 기법으로 해결하는 것이 훨씬 효율적입니다. 각 문자의 존재 여부를 O(1) 시간 복잡도로 확인할 수 있기 때문입니다.문제 해결 단계두 개의 문자열을 임의

이 튜토리얼에서는 정렬되지 않은 두 배열의 합집합(union)과 교집합(intersection)을 구하는 프로그램을 C++로 작성하는 방법을 단계별로 알아보겠습니다. 먼저 예제를 통해 문제를 이해해 보겠습니다.문제 예시입력arr_one = [1, 2, 3, 4, 5] arr_two = [3, 4, 5, 6, 7]출력union: 1 2 3 4 5 6 7 intersection: 3 4 5두 배열에 공통으로 포함된 요소는 교집합이 되고, 중복 없이 모든 요소를 합친 결과가 합집합이 됩니다. 그럼 해결 절차를 하나씩 살펴보겠습니다.합집합