문제 설명m × n 크기의 격자(grid)가 주어지며, 각 칸은 0 또는 1의 값만 가집니다. 여기서 0은 빈 칸, 1은 막혀 있는 칸(장애물)을 의미합니다. 한 번의 이동으로 상, 하, 좌, 우 방향의 인접한 빈 칸으로 움직일 수 있습니다.목표는 왼쪽 위 모서리 칸 (0, 0)에서 출발해 오른쪽 아래 모서리 칸 (m-1, n-1)에 도달할 때까지 걸리는 최소 이동 횟수를 구하는 것입니다. 단, 이동 과정에서 최대 k개의 장애물을 제거할 수 있습니다. 어떤 방법으로도 목적지에 도달할 수 없다면 -1을 반환해야 합니다.입력 예시000

문제 개요n개의 상자가 주어지며, 각 상자는 [status, candies, keys, containedBoxes] 형식으로 표현됩니다. 이때 다음과 같은 제약 조건이 존재합니다.status[i]: box[i]가 열려 있으면 1, 닫혀 있으면 0입니다.candies[i]: box[i]에 들어 있는 사탕의 개수입니다.keys[i]: box[i] 안의 열쇠로 열 수 있는 상자 인덱스들의 배열입니다.containedBoxes[i]: box[i] 안에서 발견되는 상자 인덱스들의 배열입니다.initialBoxes 배열에 담긴 상자부터 시작해

문제 개요 문자로 이루어진 정사각형 보드가 있다고 가정해 봅시다. 보드의 오른쪽 아래 끝 칸에는 시작점을 나타내는 S가, 왼쪽 위 끝 칸에는 도착점을 나타내는 E가 표시되어 있습니다. 나머지 칸은 1부터 9 사이의 숫자 문자이거나 장애물 X입니다. 한 번의 이동으로는 위쪽, 왼쪽, 왼쪽 위 대각선 세 방향 중 하나로만 움직일 수 있으며, 이동하려는 칸에 장애물이 있다면 그 방향으로는 진행할 수 없습니다. 우리가 구해야 하는 것은 다음 두 값을 담은 리스트입니다. 첫 번째 값: 이동 과정에서 수집할 수 있는 숫자들의 최대 합 두 번

문제 소개 왼쪽 항이 단어들로, 오른쪽 항이 결과 단어로 표현된 방정식이 있다고 가정해 봅시다. 우리는 다음 규칙을 모두 만족하면서 이 방정식이 성립할 수 있는지, 즉 풀 수 있는지를 판단해야 합니다. 각 문자는 정확히 한 자리 숫자(0~9)로 치환됩니다. 서로 다른 두 문자는 반드시 서로 다른 숫자에 대응되어야 합니다. 각 단어(words[i])와 결과(result)는 선행 0(leading zero)이 없는 수로 해석됩니다. 왼쪽에 있는 수들의 합은 오른쪽의 수와 정확히 같아야 합니다. 예시로 이해하기 예를 들어 words

문제 개요문자열 S가 주어졌을 때, 어떤 문자열을 그대로 한 번 더 이어 붙인 형태(예: "abcabc" = "abc" + "abc")로 표현할 수 있는 서로 다른 비어 있지 않은 부분 문자열의 개수를 구하는 것이 목표입니다.예를 들어 입력이 "elloelloello"라면 출력은 5가 됩니다. "elloello"("ello"+"ello"), "lloelloe"("lloe"+

문제 개요 다음과 같은 키보드 배치가 있다고 가정해 보겠습니다. ABCDEFGHIJKLMNOPQRSTUVWXYZ 각 알파벳 대문자는 키보드 위의 특정 좌표에 위치합니다. 예를 들어 문자 A는 (0,0), B는 (0,1), P는 (2,3), Z는 (4,1)에 해당합니다. 이때 하나의 단어가 주어지면, 두 손가락만 사용하여 이 단어를 입력할 때 드는 최소 총 이동 거리를 구해야 합니다. 두 좌표 (x1, y1)과 (x2, y2) 사이의 거리는 |x1 − x2| + |y1 − y2|로 정의되는 맨해튼 거리입니다. 또한 각 손가락은 키보

x축 위에 1차원 정원이 있다고 가정해 보겠습니다. 정원의 시작 위치는 0이고 끝 위치는 n입니다. 정원에는 [0, 1, ..., n] 위치에 총 n+1개의 수도꼭지가 설치되어 있습니다. 정수 n과 길이가 n+1인 배열 ranges가 주어질 때, ranges[i]는 i번째 수도꼭지를 열었을 때 [i - ranges[i], i + ranges[i]] 구간에 물을 줄 수 있다는 의미입니다.우리의 목표는 정원 전체에 물을 줄 수 있도록 열어야 하는 수도꼭지의 최소 개수를 구하는 것입니다. 만약 어떤 조합을 사용해도 정원 전체를 커버할 수

문제 소개정수 배열 nums가 있다고 가정해 봅시다. 이 배열의 값은 인접한 두 요소 차이의 절댓값을 모두 더한 합, 즉 0부터 n−2까지의 모든 i에 대한 |nums[i] − nums[i+1]|의 총합으로 정의됩니다. 여기서 n은 배열의 크기입니다.우리는 이 배열에서 임의의 하위 배열(연속된 구간)을 하나 선택해 뒤집을 수 있으며, 이 반전 연산은 오직 한 번만 수행할 수 있습니다. 목표는 반전을 적용한 후 얻을 수 있는 최종 배열 값의 최댓값을 구하는 것입니다.예를 들어 입력 배열이 [1, 5, 4, 2, 3]이라면, 적절한 구

문제 개요주어진 작업 목록을 d일에 걸쳐 수행하는 일정표를 만드는 문제입니다. 작업들 사이에는 의존 관계가 있어서, i번째 작업을 처리하려면 그 앞에 있는 모든 작업(0 ≤ j < i)을 먼저 완료해야 합니다.또한 매일 최소 한 개 이상의 작업을 반드시 완료해야 하며, 일정 전체의 난이도는 d일 각각의 난이도를 모두 더한 값으로 정의됩니다. 이때 하루의 난이도란 그날 수행한 작업 중 가장 높은 난이도를 의미합니다.정수 배열 jobDifficulty와 정수 d가 입력으로 주어지며, i번째 작업의 난이도는 jobDifficulty

문제 개요정수 배열 arr와 정수 d가 주어집니다. 한 번의 이동으로 인덱스 i에서 아래 두 가지 방식으로 점프할 수 있습니다.i + x : 단, i + x < n 이고 x는 1부터 d 사이의 값i - x : 단, i - x >= 0 이고 x는 1부터 d 사이의 값여기서 n은 배열의 크기입니다. 추가로, 인덱스 i에서 인덱스 j로 점프하려면 arr[i] > arr[j]를 만족해야 하며, i와 j 사이에 있는 모든 인덱스 k에 대해서도 arr[i] > arr[k] 조건을 충족해야 합니다. 우리는 배열의 어떤 인덱

문제 설명정수 배열 arr가 주어졌을 때, 우리는 처음에 인덱스 0에 위치해 있습니다. 한 번의 점프로 다음 세 가지 이동이 가능합니다.i + x : 단, i + x < n (오른쪽으로 이동)i - x : 단, i - x >= 0 (왼쪽으로 이동)j : arr[i]와 arr[j]의 값이 같고 i != j인 임의의 인덱스로 이동여기서 n은 배열의 크기입니다. 우리가 구해야 하는 것은 배열의 마지막 인덱스(n-1)에 도달하기 위한 최소 점프 횟수입니다.입력 예시입력이 다음과 같다고 가정해 보겠습니다.{20, -5, -5, 2

정수로 이루어진 목표 배열 target이 주어졌다고 가정해 봅시다. 모든 원소가 1로 구성된 시작 배열 A에서 다음과 같은 작업을 수행할 수 있습니다.현재 배열에 있는 모든 원소의 합을 x라고 합니다.0부터 n 사이의 인덱스 i를 선택하고(n은 배열의 크기), 배열 A의 i번째 값을 x로 설정합니다.이 과정은 필요한 만큼 몇 번이든 반복할 수 있습니다.우리가 해야 할 일은 시작 배열 A에서 목표 배열 target을 만드는 것이 가능한지 판별하고, 불가능하다면 false를 반환하는 것입니다.예를 들어 입력이 [3, 9, 5]라면 출력

n개의 주문 목록이 있으며, 각 주문에는 하나의 픽업(Pickup)과 하나의 배송(Delivery) 서비스가 포함되어 있다고 가정해 보겠습니다. 이 문제의 목표는 배송[i]이 반드시 픽업[i]보다 뒤에 위치하도록 만들 수 있는 모든 유효한 순서(시퀀스)의 개수를 구하는 것입니다. 결과값이 매우 커질 수 있으므로 109 + 7로 나눈 나머지를 반환합니다.예시로 이해하기입력이 2인 경우를 살펴보겠습니다. 이때 정답은 6이며, 가능한 모든 유효한 순서는 다음과 같습니다.(P1, P2, D1, D2)(P1, P2, D2, D1)(P1, D

문제 설명숫자 배열(digits)이 하나 주어졌을 때, 주어진 숫자들을 원하는 순서대로 이어 붙여 만들 수 있는 가장 큰 3의 배수를 구하는 문제입니다. 결과값이 매우 커질 수 있으므로 반드시 문자열 형태로 반환해야 하며, 만들 수 있는 답이 존재하지 않으면 빈 문자열을 반환합니다.예를 들어 입력이 [7, 2, 8]이라면 출력은 87이 됩니다.핵심 아이디어이 문제를 해결하는 열쇠는 3의 배수 판정법입니다. 어떤 수든 각 자릿수의 합이 3으로 나누어떨어지면 그 수 역시 3의 배수입니다. 따라서 다음과 같은 전략을 세울 수 있습니다.모

문제 개요이진 트리의 루트(root)가 주어졌을 때, 그중에서 이진 탐색 트리(BST) 조건을 동시에 만족하는 서브트리를 골라 해당 서브트리에 속한 모든 노드 값의 합이 최대가 되도록 구하는 문제입니다.예를 들어 다음과 같은 트리가 입력으로 주어진다면,정답은 20이 됩니다. 선택된 BST에 포함된 모든 노드 값의 합이 20이기 때문입니다.접근 방법이 문제는 후위 순회(postorder traversal) 기반의 재귀적 풀이로 깔끔하게 해결할 수 있습니다. 각 노드를 기준으로 하는 서브트리가 BST인지 여부, 노드 개수, 서브트리 내

문제 소개n개의 정점으로 구성된 무방향 트리가 하나 주어진다고 가정해 봅시다. 정점에는 1부터 n까지 번호가 붙어 있습니다. 개구리는 정점 1에서 점프를 시작하며, 현재 정점과 인접한 아직 방문하지 않은 정점으로 1초에 한 번씩 점프할 수 있습니다. 단, 이미 방문한 정점으로는 되돌아갈 수 없습니다.점프할 수 있는 정점이 여러 개라면 개구리는 동일한 확률로 그중 하나를 무작위로 선택해 이동하고, 더 이상 이동할 곳이 없다면 같은 정점 위에 영원히 머무르게 됩니다.트리는 간선(edge) 배열의 형태로 주어지며, 우리가 구해야 하는 값

문제 설명n명의 엔지니어가 있다고 가정해 보겠습니다. 각 엔지니어에게는 1부터 n까지 번호가 매겨져 있으며, 두 개의 배열 speed와 efficiency가 주어집니다. 여기서 speed[i]와 efficiency[i]는 각각 i번째 엔지니어의 속도와 효율을 나타냅니다.목표는 최대 k명의 엔지니어로 구성된 팀의 최대 성능(maximum performance)을 구하는 것입니다. 계산 결과가 매우 커질 수 있으므로, 답은 10^9 + 7로 나눈 나머지(modulo)로 반환해야 합니다.여기서 팀의 성능은 다음 공식으로 정의됩니다.팀의

크기가 제각각인 3n개의 조각으로 이루어진 피자가 있다고 가정해 봅시다. 저와 두 친구는 다음과 같은 규칙에 따라 번갈아 가며 피자 조각을 나눠 갖습니다. 제가 먼저 원하는 피자 조각을 하나 자유롭게 선택합니다. 친구 Amal은 제가 고른 조각을 기준으로 반시계 방향에 인접한 다음 조각을 가져갑니다. 친구 Bimal은 제가 고른 조각을 기준으로 시계 방향에 인접한 다음 조각을 가져갑니다. 피자 조각이 더 이상 남지 않을 때까지 이 과정을 반복합니다. 피자 조각의 크기는 시계 방향 순서대로 배치된 원형 배열 slices로 표현됩니

문제 개요문자열 s가 주어졌을 때, 가장 긴 해피 접두사(happy prefix)를 찾는 것이 이번 문제의 목표입니다. 여기서 해피 접두사란 문자열 자기 자신을 제외했을 때, 접두사이면서 동시에 접미사가 되는 비어 있지 않은 부분 문자열을 의미합니다. 만약 조건을 만족하는 해피 접두사가 존재하지 않는다면 빈 문자열()을 반환하면 됩니다.예를 들어 입력이 madam이라면 출력은 m입니다. madam에는 자기 자신을 제외한 네 개의 접두사(m, ma, mad, mada)와 네 개의 접미사(m, am, dam, adam)가 있습니다. 이

문제 소개 길이가 n인 두 개의 문자열 s1과 s2, 그리고 evil이라는 이름의 문자열 하나가 주어집니다. 목표는 좋은(good) 문자열의 개수를 구하는 것입니다. 어떤 문자열이 다음 조건을 모두 만족할 때 좋은 문자열이라고 정의합니다. 길이가 정확히 n이다. 사전 순으로 s1보다 크거나 같다. 사전 순으로 s2보다 작거나 같다. evil을 부분 문자열로 포함하지 않는다. 정답은 매우 커질 수 있으므로, 결과를 109 + 7로 나눈 나머지를 반환해야 합니다. 예시 n = 2, s1 = bb, s2 = db, evil = a가