K개의 계란과 1층부터 N층까지 있는 건물이 주어져 있다고 가정해 봅시다. 모든 계란은 기능이 완전히 동일하며, 한 번 깨진 계란은 다시 사용할 수 없습니다.0부터 N 사이의 어딘가에는 특정 층 F가 존재합니다. F보다 높은 층에서 계란을 떨어뜨리면 반드시 깨지고, F층 이하에서 떨어뜨리면 깨지지 않습니다. 매 시도마다 계란 하나를 골라 1층부터 N층 사이의 임의의 층 X에서 떨어뜨릴 수 있습니다.우리의 목표는 F의 값을 확실하게 알아내는 것입니다. 그렇다면 F의 초기값과 무관하게 항상 F를 정확히 판별하기 위해 필요한 최소 시도

문제 개요 정수 배열 A가 주어졌을 때, A로 만들 수 있는 모든 비어 있지 않은 부분 수열(non-empty subsequence)을 생각해 봅시다. 임의의 수열 S에 대해 너비(width)는 S에 속한 원소들의 최댓값과 최솟값의 차이로 정의됩니다. 즉, width(S) = max(S) − min(S)입니다. 우리가 구해야 할 것은 A의 모든 부분 수열 너비의 총합입니다. 이 값은 매우 커질 수 있으므로 10^9 + 7로 나눈 나머지를 반환해야 합니다. 예를 들어 입력이 [3, 1, 2]라면 결과는 6입니다. 가능한 부분 수열은

FreqStack이라는 이름의 특수한 스택을 구현해야 한다고 가정해 보겠습니다. 이 스택은 다음 두 가지 연산을 제공합니다.push(x) — 정수 x를 스택에 삽입합니다.pop() — 스택에서 가장 자주 등장한(빈도가 가장 높은) 요소를 제거하고 반환합니다. 만약 빈도가 같은 요소가 여러 개라면, 그중 스택의 최상단(top)에 가장 가까운 요소를 제거하여 반환합니다.예를 들어, 7, 9, 7, 9, 6, 7 순서로 요소를 push한 후 pop을 네 번 호출하면 출력 결과는 각각 7, 9, 7, 6이 됩니다.해결 접근 방식이 문제는

문제 설명소문자로만 이루어진 문자열 S가 있다고 가정해 봅시다. 우리는 원하는 만큼 여러 번의 이동(move)을 수행할 수 있습니다.각 이동에서는 문자열의 앞쪽 K개 문자 중 하나를 선택해 제거한 뒤, 문자열의 맨 끝으로 옮깁니다. 목표는 임의의 횟수만큼 이동을 수행한 후 얻을 수 있는 사전순(lexicographically)으로 가장 작은 문자열을 찾는 것입니다.예를 들어 입력이 cabaa이고 K = 3이라면, 출력은 aaabc가 됩니다.해결 전략이 문제는 다음과 같은 단계로 해결할 수 있습니다.K > 1인 경우문자열 S를

문제 개요정렬된 자릿수 집합 D가 주어집니다. D는 0을 제외한 {1, 2, 3, 4, 5, 6, 7, 8, 9}의 공집합이 아닌 부분집합입니다. 우리는 이 자릿수들을 사용해 각 숫자를 원하는 만큼 반복하여 여러 수를 만들 수 있습니다. 예를 들어 D = {2, 3, 7}이라면 23, 771, 2372327과 같은 수를 작성할 수 있습니다.이 문제의 목표는 위 방식으로 만들 수 있는 양의 정수 중 N 이하인 수의 개수를 구하는 것입니다.예를 들어 입력이 D = [2, 3, 4, 7], N = 100이라면 출력은 20이 됩니다. 만들

문자열 S가 주어졌다고 가정해 봅시다. 이 문자열은 {D, I} 집합에 속한 문자들로만 구성되어 있습니다. 여기서 D는 감소(decreasing)를, I는 증가(increasing)를 의미합니다.유효한 순열(valid permutation)은 정수 {0부터 n}으로 이루어진 순열 P[0], P[1], ..., P[n] 중에서 모든 i에 대해 다음 규칙을 만족하는 순열을 말합니다.S[i] == D라면, P[i] > P[i+1]을 만족해야 합니다.S[i] == I라면, P[i] < P[i+1]을 만족해야 합니다.우리가 구해야

슈퍼 팰린드롬(superpalindrome)은 자기 자신이 회문(palindrome)일 뿐만 아니라, 어떤 회문의 제곱이기도 한 양의 정수를 의미합니다. 이번 글에서는 두 개의 양의 정수 L과 R이 주어졌을 때, 닫힌 구간 [L, R] 안에 포함된 슈퍼 팰린드롬의 개수를 찾는 방법을 살펴보겠습니다. 예를 들어 입력이 L = 5, R = 500이라면 출력은 3이 됩니다. 이 범위 내의 슈퍼 팰린드롬은 9, 121, 484입니다. 9 = 3² → 3과 9 모두 회문 121 = 11² → 11과 121 모두 회문 484 = 22² →

음악 플레이어에 서로 다른 N곡의 노래가 저장되어 있고, 여행 중 L곡을 듣고 싶다고 가정해 봅시다. 이때 다음 조건을 만족하는 플레이리스트를 만들어야 합니다.모든 노래는 최소 한 번 이상 재생되어야 합니다.어떤 노래를 다시 재생하려면, 그 전에 반드시 K개의 다른 노래가 먼저 재생되어야 합니다.우리가 구해야 할 것은 가능한 플레이리스트의 총 개수입니다. 답이 매우 커질 수 있으므로, 결과는 10^9 + 7로 나눈 나머지를 반환합니다.예를 들어 입력이 N = 2, L = 3, K = 0이라면 출력은 6입니다. [1,1,2], [1,

0과 1로만 이루어진 배열 A가 주어졌다고 가정해 봅시다. 이 배열을 세 개의 비어 있지 않은 부분으로 나누되, 세 부분이 모두 동일한 이진(binary) 값을 나타내도록 만들어야 합니다. 가능하다면 i + 1 < j 조건을 만족하는 인덱스 쌍 [i, j] 중 아무거나 하나를 반환하면 됩니다. 첫 번째 부분: A[0], A[1], ..., A[i] 두 번째 부분: A[i+1], A[i+2], ..., A[j-1] 세 번째 부분: A[j], A[j+1], ..., A[A.length - 1] 세 부분을 같은 이진 값으로 나

문제 소개 문자열 S가 주어졌을 때, S에서 만들 수 있는 서로 다른 부분 수열(distinct subsequences)의 개수를 구하는 문제입니다. 부분 수열이란 원본 문자열에서 몇 개의 문자를 삭제하거나 그대로 두어 얻을 수 있는 문자열로, 남은 문자들의 상대적인 순서는 유지되어야 합니다. 결과값이 매우 커질 수 있으므로, 정답은 10^9 + 7로 나눈 나머지를 반환해야 합니다. 예를 들어 입력이 "bab"라면 출력은 6입니다. 만들 수 있는 서로 다른 부분 수열은 "a", "b&qu

문자열 배열 A가 주어졌을 때, A에 속한 모든 문자열을 부분 문자열(substring)로 포함하는 가장 짧은 문자열, 즉 최단 슈퍼스트링(shortest superstring)을 찾아야 합니다. 이때 배열 A 안의 어떤 문자열도 다른 문자열의 부분 문자열이 아니라고 가정할 수 있습니다.예를 들어 입력이 [dbsh, dsbbhs, hdsb, ssdb, bshdbsd]라면 출력은 hdsbbhssdbshdbsd가 됩니다.문제 해결 접근 방식이 문제는 외판원 순환(TSP) 문제와 구조가 유사하며, 비트마스크(bitmask)와 동적 계획법

서로 다른 양의 정수로 이루어진 배열 A가 있다고 가정해 보겠습니다. 이 배열을 바탕으로 다음과 같은 그래프를 생각할 수 있습니다.그래프에는 배열 A의 길이만큼 노드가 존재하며, 각 노드는 A[0]부터 A[A.size() - 1]까지의 값으로 라벨링됩니다. 두 노드 A[i]와 A[j]가 1보다 큰 공통 약수(공통 인수)를 가질 때 두 노드 사이에 간선이 연결됩니다. 우리가 구해야 하는 것은 이 그래프에서 가장 큰 연결 요소(Connected Component)의 크기입니다.예를 들어 입력이 [4, 6, 15, 35]라면 출력은 4가

문제 설명 빌보드를 설치한다고 가정해 봅시다. 우리는 이 빌보드가 최대한 높은 높이를 갖기를 원합니다. 빌보드는 양쪽에 두 개의 강철 지지대로 받쳐지며, 두 지지대의 높이는 반드시 서로 같아야 합니다. 또한 서로 용접하여 연결할 수 있는 여러 개의 막대(rod)가 주어집니다. 예를 들어 길이가 1, 2, 3인 막대가 있다면, 이들을 모두 용접하여 길이 6짜리 하나의 지지대를 만들 수 있습니다. 목표는 빌보드를 지지할 수 있는 가장 큰 높이를 구하는 것이며, 빌보드를 지지하는 것이 불가능하다면 0을 반환해야 합니다. 예를 들어 입력

문제 개요소문자로만 구성되고 길이가 모두 같은 N개의 문자열로 이루어진 배열 A가 주어졌다고 가정해 봅시다. 이제 임의의 삭제 인덱스 집합 D를 선택하여, 각 문자열에서 해당 인덱스에 위치한 모든 문자를 제거합니다. 삭제가 완료된 후 최종 배열의 모든 요소가 사전순(lexicographic)으로 정렬된 상태가 되도록 하는 것이 목표입니다.조금 더 명확하게 설명하면, A[0]은 스스로 오름차순이어야 하고(A[0][0] <= A[0][1] <= ... <= A[0][n-1]), A[1] 역시 A[1][0] <= A

문제 이해하기양의 정수 x가 주어졌을 때, 다음과 같은 형태의 수식을 작성한다고 가정해 보겠습니다.x (op1) x (op2) x (op3) x ...여기서 op1, op2 등은 각각 덧셈(+), 뺄셈(-), 곱셈(*), 나눗셈(/) 중 하나입니다. 예를 들어 x = 3이라면 3 * 3 / 3 + 3 - 3처럼 수식을 작성할 수 있으며, 이 수식의 계산 결과는 3이 됩니다.적용되는 규칙나눗셈 연산자(/)는 유리수를 결과로 반환합니다.괄호는 어떤 위치에도 사용할 수 없습니다.일반적인 연산자 우선순위를 따릅니다. 즉, 곱셈과 나눗셈이

문제 개요두 개의 문자열 S와 T가 주어집니다. 각 문자열은 하나의 양의 유리수를 나타내며, 두 문자열이 서로 같은 수를 표현하고 있는지 판별해야 합니다. 문자열에는 유리수의 순환 소수 부분을 나타내기 위해 괄호가 사용될 수 있습니다.유리수는 최대 세 부분으로 구성할 수 있습니다. 바로 정수부, 순환하지 않는 소수부(비순환부), 그리고 순환 소수부입니다. 따라서 수는 다음 세 가지 형태 중 하나로 표현됩니다.정수부만 있는 경우 (예: 0, 12, 123)정수부.비순환부 형태 (예: 0.5, 1.0, 2.12, 2.0001)정수부.비

정수 배열 A가 주어졌을 때, 아래 조건을 모두 만족하는 인덱스 삼중항 (i, j, k)의 개수를 구하는 문제입니다. 0 <= i < 배열 A의 크기 0 <= j < 배열 A의 크기 0 <= k < 배열 A의 크기 또한 A[i] AND A[j] AND A[k]의 값이 0이 되어야 합니다. 여기서 AND는 비트 단위 AND(bitwise-AND) 연산자를 의미합니다. 문제 이해하기 예를 들어 입력이 [3, 1, 2]라면 출력은 12가 됩니다. 각 원소를 이진수로 표현하면 3 = 011, 1 = 0

문제 개요양의 정수로 이루어진 배열 A가 있다고 가정해 보겠습니다. 어떤 부분 배열(연속된 구간) 안에 포함된 서로 다른 정수의 개수가 정확히 K라면, 그 부분 배열을 좋은(good) 부분 배열이라고 부릅니다. 예를 들어 배열 [1,2,3,1,2]에는 1, 2, 3이라는 세 가지 서로 다른 정수가 존재합니다. 우리의 목표는 배열 A에서 좋은 부분 배열이 총 몇 개인지 구하는 것입니다.예를 들어 입력이 [1,2,3,1,4]이고 K = 3일 때 출력은 4가 됩니다. 정확히 세 개의 서로 다른 정수를 포함하는 부분 배열은 다음 네 가지이

0과 1로만 이루어진 배열 A가 주어졌다고 가정해 봅시다. 여기서 K-비트 반전(K-bit flip)이란 길이가 K인 연속된 부분 배열을 선택하여 그 안의 모든 비트를 한꺼번에 뒤집는(0↔1) 연산을 의미합니다.우리가 구해야 할 것은 배열 전체에 0이 하나도 남지 않도록 만들기 위해 필요한 최소 반전 횟수입니다. 만약 어떤 방법으로도 목표를 달성할 수 없다면 -1을 반환해야 합니다.문제 예시입력이 [0,0,0,1,0,1,1,0]이고 K = 3일 때, 정답은 3입니다. 세 번의 연산 과정은 다음과 같습니다.1차: 인덱스 0~2를 반전

문제 설명양의 정수로 이루어진 배열 A가 있다고 가정해 봅시다. 만약 배열 내 모든 인접한 원소 쌍의 합이 완전제곱수(perfect square)라면, 이 배열을 스퀘어풀(Squareful) 배열이라고 부릅니다. 우리가 구해야 하는 것은 배열 A의 순열 중에서 스퀘어풀 조건을 만족하는 순열의 개수입니다. 단, 두 순열 A1과 A2는 어떤 인덱스 i에서 A1[i]와 A2[i]의 값이 서로 다른 경우에만 다른 순열로 간주됩니다.예를 들어 입력이 [3, 30, 6]이라면 출력은 2가 됩니다. [3, 6, 30]과 [30, 6, 3], 이