문제 개요이진 트리의 루트 노드가 주어졌을 때, 루트의 레벨은 1이고 자식 노드의 레벨은 2이며, 그 아래로 내려갈수록 레벨이 하나씩 증가합니다. 이때 해당 레벨에 있는 모든 노드 값의 합이 가장 큰 레벨 X 중에서 가장 작은 값을 반환해야 합니다.예를 들어 다음과 같은 이진 트리가 있다고 가정해 보겠습니다.각 레벨의 합을 계산해 보면 레벨 1의 합은 1, 레벨 2의 합은 7 + 0 = 7, 레벨 3의 합은 7 + (-8) = -1입니다. 따라서 합이 가장 큰 레벨은 2이므로 출력 결과는 2가 됩니다.접근 방법이 문제는 너비 우선

길이가 양의 정수인 막대(stick) 여러 개가 주어져 있다고 가정해 봅시다. 길이가 각각 X와 Y인 두 막대를 하나로 이을 때 비용은 X + Y가 되며, 이 과정은 막대가 하나만 남을 때까지 반복됩니다. 우리가 구해야 할 것은 모든 막대를 하나로 연결할 때 드는 최소 비용입니다.예를 들어 막대 배열이 [2, 4, 3]이라면, 정답은 14가 됩니다.해결 전략: 그리디 알고리즘과 최소 힙(Min Heap)연결 비용이 항상 두 막대 길이의 합이기 때문에, 매 단계에서 가장 짧은 막대 두 개를 먼저 연결하는 것이 전체 비용을 최소화하는

정수 배열이 주어졌을 때, 최대 한 개의 원소를 삭제할 수 있다는 조건에서 비어 있지 않은 연속 부분 배열의 최대 합을 구하는 문제입니다. 즉, 부분 배열을 하나 선택한 뒤 원한다면 그중 원소 하나를 제거할 수 있으며, 삭제 후에도 최소 한 개 이상의 원소가 남아 있어야 하고 남은 원소들의 합이 가능한 한 최대가 되어야 합니다.예를 들어 입력이 [1, -2, 0, 3]이라면 출력은 4입니다. 여기서 -2를 삭제하면 나머지 원소들의 합인 4가 최댓값이 되기 때문입니다.접근 방법: 동적 계획법(DP)이 문제는 카데인 알고리즘(Kadan

문제 설명두 개의 이진 탐색 트리(Binary Search Tree, BST)가 주어졌을 때, 첫 번째 트리의 어떤 노드와 두 번째 트리의 어떤 노드를 골라 그 값의 합이 주어진 정수 target과 일치한다면 true를 반환하고, 그런 경우가 존재하지 않으면 false를 반환하는 문제입니다.예를 들어 아래와 같은 두 개의 트리가 있다고 가정해 보겠습니다.첫 번째 트리는 [2,1,4], 두 번째 트리는 [1,0,3]으로 구성되어 있고, target이 5라면 결과는 true입니다. 실제로 첫 번째 트리의 노드 2와 두 번째 트리의 노드

문제 개요 정수 배열 arr과 정수 difference가 주어졌을 때, 인접한 원소 간의 차이가 모두 difference와 같은 가장 긴 등차 부분 수열의 길이를 찾아야 합니다. 예를 들어 입력이 [1,5,7,8,5,3,4,2,1]이고 difference가 -2라면, 출력은 4입니다. 이 경우 가장 긴 등차 수열은 [7,5,3,1]이며, 인접한 원소들이 모두 -2씩 감소하기 때문입니다. 풀이 접근 방식 이 문제는 해시 맵을 활용한 동적 계획법(DP)으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다. m[x] =

```html 게임이나 경쟁 서비스에서 리더보드(Leaderboard)는 필수적인 요소입니다. 이번 글에서는 C++로 리더보드 클래스를 설계하는 방법을 단계별로 살펴보겠습니다. 설계해야 할 리더보드 클래스는 다음과 같은 세 가지 기능을 제공해야 합니다. addScore(playerId, score) – 주어진 플레이어의 현재 점수에 score를 더해 리더보드를 갱신합니다. 만약 해당 playerId를 가진 플레이어가 리더보드에 없다면, 주어진 점수로 새롭게 등록합니다. top(K) – 상위 K명 플레이어의 점수 합계를 반환합니다.

문제 개요무방향 트리가 하나 주어졌을 때, 이 트리의 지름(diameter)을 구하는 것이 목표입니다. 트리의 지름이란 트리 안에서 가장 긴 경로에 포함된 간선의 개수를 의미합니다.트리는 간선 리스트 형태로 주어지며, edges[i] = [u, v]는 노드 u와 노드 v를 잇는 양방향 간선을 나타냅니다. 각 노드의 레이블은 {0, 1, ..., edges.length} 범위에 속합니다.예를 들어 다음과 같은 트리가 있다고 가정해 보겠습니다.이 경우 가장 긴 경로는 3 → 2 → 1 → 4 → 5이며, 여기에는 간선이 4개 포함되어

x와 y 문자로만 구성되고 길이가 서로 같은 두 문자열 s1과 s2가 있다고 가정해 보겠습니다. 우리의 목표는 이 두 문자열을 완전히 동일하게 만드는 것입니다. 단, 문자 교환은 반드시 서로 다른 문자열에 속한 두 문자 사이에서만 허용됩니다. 즉, s1[i]와 s2[j]를 맞바꾸는 방식입니다. 두 문자열을 같게 만들기 위해 필요한 최소 스왑 횟수를 구하고, 불가능한 경우에는 -1을 반환해야 합니다.예를 들어 s1 = xy, s2 = yx라고 한다면 정답은 2입니다. 먼저 s1[0]과 s2[0]을 스왑하면 s1 = yy, s2 = x

정수 배열 nums와 정수 k가 주어졌다고 가정해 보겠습니다. 어떤 부분 배열(subarray) 안에 홀수가 정확히 k개 포함되어 있다면, 그 부분 배열을 좋은(nice) 부분 배열이라고 부릅니다. 우리의 목표는 이러한 좋은 부분 배열의 개수를 구하는 것입니다.예를 들어 배열이 [1,1,2,1,1]이고 k = 3이라면 출력은 2가 됩니다. 조건을 만족하는 부분 배열은 [1,1,2,1]과 [1,2,1,1] 두 가지뿐이기 때문입니다.해결 접근 방법이 문제는 다음 단계를 따라 해결할 수 있습니다.ans := 0, n := nums 배열의

문제 개요정렬되어 있고 서로 겹치지 않는(disjoint) 구간 목록이 주어졌다고 가정해 봅시다. 각 구간은 intervals[i] = [a, b] 형태로 표현되며, 이는 a <= x < b를 만족하는 수 x들의 집합을 의미합니다. 이때 intervals에 포함된 모든 구간과 주어진 toBeRemoved 구간 사이의 교집합을 제거한 뒤, 남은 구간들을 정렬된 상태로 반환해야 합니다.예를 들어 입력이 [[0,2],[3,4],[5,7]]이고 toBeRemoved가 [1,6]이라면, 구간 [0,2]에서는 [1,2) 부분이, 구

노드 0을 루트로 하는 트리가 하나 있다고 가정해 보겠습니다. 이 트리는 다음과 같은 정보로 주어집니다.노드의 총 개수는 nodesi번째 노드의 값은 value[i]i번째 노드의 부모는 parent[i]우리가 해야 할 작업은 노드 값들의 합이 0이 되는 모든 서브트리를 제거하고, 그 후 트리에 남아 있는 노드의 개수를 반환하는 것입니다.예를 들어 다음과 같은 트리가 있다고 가정해 봅시다.총 7개의 노드가 있고, 이 경우 출력 결과는 2가 됩니다.문제 해결 접근 방법이 문제는 DFS(깊이 우선 탐색)를 활용하면 효율적으로 해결할 수

문제 개요조합(Combination)을 순차적으로 탐색할 수 있는 반복자(Iterator) 클래스를 설계해야 합니다. 이 클래스는 다음과 같은 연산을 제공해야 합니다.생성자: 정렬되어 있고 중복 없는 소문자 영어 알파벳으로 구성된 문자열과 숫자 combinationLength를 매개변수로 받습니다.next(): 알파벳 순서를 기준으로 길이가 combinationLength인 다음 조합을 반환합니다.hasNext(): 다음 조합이 존재하는 경우에만 true를 반환하고, 그렇지 않으면 false를 반환합니다.예를 들어 입력이 다음과 같

문제 개요간격(intervals) 목록이 주어졌을 때, 목록 내 다른 간격에 완전히 포함되는(덮이는) 간격을 모두 제거해야 합니다. 여기서 간격 [a, b)는 c <= a 이고 b <= d 인 경우에만 간격 [c, d)에 의해 덮인 것으로 간주합니다.모든 포함된 간격을 제거한 뒤에는 남아 있는 간격의 개수를 반환해야 합니다.예를 들어, 입력이 [[1,4], [3,6], [2,8]]이라면 출력은 2가 됩니다. 간격 [3,6]은 [1,4]와 [2,8] 두 간격에 의해 덮여 있기 때문입니다.해결 접근 방법이 문제는 정렬과 스택

문제 개요m × n 크기의 행렬 mat와 하나의 정수 threshold(임계값)가 주어졌을 때, 모든 원소의 합이 임계값 이하인 정사각형 중에서 가장 큰 변의 길이를 구하는 문제입니다. 만약 조건을 만족하는 정사각형이 하나도 존재하지 않는다면 0을 반환해야 합니다.예를 들어 입력 행렬이 다음과 같다고 가정해 보겠습니다.113243211324321132432여기서 임계값이 4라면, 아래 표에서 초록색으로 표시한 부분처럼 변의 길이가 2인 정사각형(합 = 1+1+1+1 = 4)을 찾을 수 있습니다. 이러한 정사각형이 총 두 개 존재하므

문자열 s가 주어졌을 때, 다음 조건을 만족하는 임의의 부분 문자열이 나타나는 최대 횟수를 구해야 합니다.부분 문자열에 포함된 서로 다른 문자의 개수는 maxLetters 이하여야 합니다.부분 문자열의 길이는 minSize 이상 maxSize 이하 범위 안에 있어야 합니다.예를 들어 입력이 aababcaab, maxLetters = 2, minSize = 3, maxSize = 4라면 결과는 2가 됩니다. 부분 문자열 aab는 원본 문자열 안에서 두 번 등장하며, 서로 다른 문자가 2개이고 길이가 3(minSize와 maxSize

이진 트리가 하나 주어졌다고 가정해 보겠습니다. 우리가 구해야 할 것은 트리에서 가장 깊은 위치에 있는 잎(리프) 노드들의 값의 합입니다. 예를 들어 아래와 같은 트리가 있다고 합시다. 이 경우 출력 결과는 15가 됩니다. 문제 해결 접근 방법 이 문제는 DFS(깊이 우선 탐색) 방식의 재귀 함수를 활용하면 간단하게 해결할 수 있습니다. 단계별로 살펴보겠습니다. 레벨별 노드 값의 합을 저장할 맵(map) m과 최대 깊이를 나타내는 maxDepth 변수를 정의합니다. 노드와 레벨을 매개변수로 받는 재귀 함수 solve()를 정

문제 개요두 개의 이진 탐색 트리(Binary Search Tree, BST)가 주어졌을 때, 두 트리에 존재하는 모든 요소를 하나의 리스트에 담아 오름차순으로 반환하는 것이 이번 문제의 목표입니다.예를 들어 아래와 같은 두 트리가 있다고 가정해 보겠습니다.이 경우 출력 결과는 [0, 1, 1, 2, 3, 4]가 됩니다.해결 접근 방식이진 탐색 트리를 중위 순회(In-order Traversal)하면 값이 항상 오름차순으로 나온다는 성질을 활용하면 이 문제를 효율적으로 풀 수 있습니다. 재귀 호출 대신 스택 두 개를 사용해 반복적으

문제 설명음이 아닌 정수로 구성된 배열 arr가 주어지고, 우리는 배열의 특정 시작 인덱스(start)에 위치해 있습니다. 현재 인덱스 i에 있을 때, i + arr[i] 또는 i − arr[i]로 점프할 수 있습니다. 이때 목표는 값이 0인 인덱스에 도달할 수 있는지 판별하는 것입니다. 단, 어떤 경우에도 배열의 범위를 벗어나서는 안 된다는 점에 유의해야 합니다.예를 들어, 입력이 arr = [4,2,3,0,3,1,2]이고 시작 인덱스가 5라면 결과는 true입니다. 왜냐하면 5 → 4 → 1 → 3 또는 5 → 6 → 4 → 1

문제 개요양의 정수로 이루어진 배열 arr과 쿼리 배열 queries가 주어진다고 가정해 봅시다. 각 쿼리는 queries[i] = [Li, Ri] 형태이며, 매 쿼리마다 인덱스 Li부터 Ri까지의 모든 요소를 XOR 연산한 값(즉, arr[Li] XOR arr[Li+1] XOR ... XOR arr[Ri])을 계산해야 합니다. 모든 쿼리의 결과를 담은 배열을 반환하는 것이 목표입니다.예를 들어 입력 배열이 [1,3,4,8]이고 쿼리가 [[0,1],[1,2],[0,3],[3,3]]이라면, 결과는 [2,7,14,8]이 됩니다.그 이유

문제 개요m × n 크기의 행렬 mat과 정수 K가 주어졌을 때, 새로운 행렬 answer를 만들어야 합니다. 이때 각 원소 answer[i][j]는 다음 조건을 만족하는 모든 mat[r][c] 값의 합입니다.i − K ≤ r ≤ i + Kj − K ≤ c ≤ j + K(r, c)는 행렬 내부의 유효한 위치즉, 각 위치를 기준으로 K만큼 떨어진 범위(정사각형 영역)에 포함된 원소들을 모두 더한 값을 결과 행렬에 저장하는 것입니다.입력 예시다음과 같은 3×3 행렬이 주어지고,123456789K = 1일 때 출력 결과는 다음과 같습니다