N개의 돌 무더기가 일렬로 놓여 있다고 가정해 봅시다. i번째 무더기에는 stones[i]개의 돌이 들어 있습니다. 한 번의 연산은 K개의 연속된 무더기를 하나로 합치는 것을 의미하며, 이때 발생하는 비용은 해당 K개 무더기에 들어 있는 돌의 총 개수입니다. 우리의 목표는 모든 돌 무더기를 하나로 합칠 때 드는 최소 비용을 구하는 것이며, 만약 합치는 방법이 존재하지 않는다면 -1을 반환해야 합니다.문제 예시입력이 [3, 2, 4, 1]이고 K = 2라고 가정하면, 출력은 20이 됩니다. 그 과정은 다음과 같습니다.[3, 2, 4,

문제 개요양의 정수 N이 주어졌을 때, 1부터 N 사이(양 끝값 포함)의 정수 중 최소 한 개 이상의 반복되는 자릿수를 가진 수의 개수를 구하는 것이 목표입니다.예를 들어 입력이 99라면 출력은 9가 됩니다. 11, 22, 33, 44, 55, 66, 77, 88, 99처럼 같은 숫자가 두 번 이상 등장하는 수가 정확히 9개이기 때문입니다.접근 방식반복되는 자릿수를 가진 수를 직접 세는 것보다, 그 반대인 모든 자릿수가 서로 다른 수의 개수를 먼저 계산한 뒤 N에서 빼는 방식이 훨씬 효율적입니다. 서로 다른 자릿수로 이루어진 k자리

이 글에서는 문자 스트림을 실시간으로 처리하는 StreamChecker 클래스를 C++로 구현하는 방법을 알아보겠습니다. 문제 정의 StreamChecker 클래스는 다음 두 가지 기능을 제공해야 합니다. StreamChecker(words) — 생성자입니다. 주어진 단어 목록으로 자료구조를 초기화합니다. query(letter) — 지금까지 질의한 문자 중 마지막 k개(가장 오래된 것부터 최신 것까지 순서대로, 방금 질의한 문자 포함)를 이어 붙였을 때 단어 목록 속 단어 하나와 일치하는 k ≥ 1이

문제 소개문자열 S가 주어졌을 때, 두 번 이상 등장하는 모든 연속된 부분 문자열을 고려해 봅시다. 이때 각 등장 위치는 서로 겹쳐도 무방합니다. 우리의 목표는 이 중에서 가장 길이가 긴 중복 부분 문자열을 찾는 것이며, 만약 중복되는 부분 문자열이 하나도 존재하지 않는다면 빈 문자열을 반환하면 됩니다.해시 계산 과정에서 값이 매우 커질 수 있기 때문에, 모든 해시 연산은 10^9 + 7로 나눈 나머지(mod)를 기준으로 처리합니다.예를 들어 입력이 ababbaba라면, 출력은 bab가 됩니다.풀이 접근 방식이 문제는 이진 탐색(B

하나의 행렬(matrix)과 목표값(target)이 주어졌을 때, 합이 목표값과 같은 비어 있지 않은 부분 행렬(submatrix)의 개수를 구하는 문제입니다. 여기서 부분 행렬 [(x1, y1), (x2, y2)]는 x가 x1부터 x2 범위에 있고, y가 y1부터 y2 범위에 있는 모든 셀 matrix[x][y]의 집합을 의미합니다.두 부분 행렬 [(x1, y1), (x2, y2)]와 [(x1, y1), (x2, y2)]는 좌표 중 하나라도 다르면 서로 다른 것으로 간주합니다. 예를 들어 x1과 x1이 같지 않다면 두 부분 행렬은

문제 개요두 문자열 str1과 str2가 주어졌을 때, 두 문자열을 모두 부분 수열(subsequence)로 포함하는 가장 짧은 문자열을 찾는 것이 이번 글의 목표입니다. 정답이 여러 개 존재할 수 있으므로 그중 하나만 반환하면 됩니다.여기서 문자열 S가 문자열 T의 부분 수열이라는 것은, T에서 임의의 위치에 있는 일부 문자(0개일 수도 있음)를 삭제했을 때 S가 된다는 의미입니다.예를 들어 입력이 acab과 bac라면 출력은 bacab이 됩니다. 두 문자열 모두 bacab의 부분 수열이기 때문입니다.해결 접근 방법이 문제는 최장

문자열 s가 주어졌을 때, 사전순(lexicographic order)으로 가장 뒤에 오는 부분 문자열을 찾는 문제입니다.예를 들어 입력 문자열이 abbbcabbc라면, 정답은 cabbc가 됩니다.접근 방법이 문제는 두 개의 포인터를 활용한 비교 기법으로 선형 시간(O(n)) 안에 해결할 수 있습니다. 알고리즘에서는 세 개의 변수를 사용합니다.i: 현재까지 발견된 최적 후보의 시작 인덱스j: 새로 비교할 후보의 시작 인덱스k: 두 후보 구간이 일치하는 길이알고리즘 단계i = 0, j = 1, k = 0으로 초기화합니다.j + k가

문제 이해하기 정수를 저장하는 두 개의 배열 arr1과 arr2가 있다고 가정해 봅시다. 우리의 목표는 arr1을 엄격하게 증가(strictly increasing)하는 배열, 즉 모든 원소가 바로 앞 원소보다 큰 배열로 만드는 데 필요한 최소 연산 횟수를 구하는 것입니다. 여기서 허용되는 연산은 하나뿐입니다. 두 개의 인덱스 0 <= i < n과 0 <= j < m을 선택한 뒤, arr1[i] = arr2[j]와 같이 값을 대입하는 것입니다. 여기서 n과 m은 각각 arr1과 arr2의 크기를 의미합니다. 만

문제 개요n개의 서버가 있다고 가정해 보겠습니다. 서버는 0부터 n-1까지 번호가 매겨져 있으며, 서버 간의 무방향 연결로 하나의 네트워크를 이룹니다. 여기서 connections[i] = [a, b]는 서버 a와 서버 b 사이의 연결을 의미합니다. 모든 서버는 직접적으로 또는 다른 서버를 경유하여 서로 연결되어 있습니다.이때 중요 연결(critical connection)이란 해당 연결을 제거했을 때 특정 서버가 다른 서버에 도달할 수 없게 되는 연결을 말합니다. 우리의 목표는 네트워크에서 모든 중요 연결을 찾아내는 것입니다.예를

문제 개요숫자 n이 하나 주어졌을 때, 아래 규칙을 모두 만족하는 길이 n의 문자열이 총 몇 개 만들어질 수 있는지 구하는 문제입니다.모든 문자는 영어 소문자 모음(a, e, i, o, u)이어야 합니다.모음 a 뒤에는 오직 e만 올 수 있습니다.모음 e 뒤에는 a 또는 i만 올 수 있습니다.모음 i 바로 뒤에 또 다른 i는 올 수 없습니다.모음 o 뒤에는 i 또는 u만 올 수 있습니다.모음 u 뒤에는 오직 a만 올 수 있습니다.답이 매우 커질 수 있으므로, 최종 결과는 109 + 7로 나눈 나머지를 구합니다.예를 들어 입력이 2라

문제 소개 양의 정수로 이루어진 배열 nums가 주어졌을 때, 배열의 접두사(prefix) 중에서 정확히 한 개의 요소를 삭제했을 때 등장한 모든 숫자의 빈도가 서로 같아지는 가장 긴 접두사의 길이를 반환해야 합니다. 단, 요소를 하나 삭제한 후 남은 요소가 없는 경우에도 모든 숫자가 동일한 빈도(0)를 가진 것으로 간주합니다. 예를 들어 입력 배열이 [3, 3, 2, 2, 6, 4, 4, 6]이라면 결과는 7입니다. 인덱스 4에 있는 값 6을 제거하면 [3, 3, 2, 2, 4, 4]가 되는데, 이때 모든 숫자가 정확히 두 번씩

문제 개요서로 다른 n개의 작업이 있다고 가정해 봅시다. 각 작업은 startTime[i]부터 endTime[i]까지 수행되며, 해당 작업을 완료하면 profit[i]만큼의 이익을 얻습니다. startTime, endTime, profit 배열이 주어졌을 때, 두 작업의 실행 시간이 서로 겹치지 않도록 작업 부분 집합을 구성해 얻을 수 있는 최대 이익을 구하는 것이 이 문제의 목표입니다. 단, 한 작업이 시간 X에 종료된다면 시간 X에 시작하는 다른 작업을 바로 수행할 수 있다는 점에 유의하세요.입력 예시예를 들어 입력이 다음과 같

크기가 n × m인 직사각형이 있다고 가정해 보겠습니다. 이때 변의 길이가 정수인 정사각형 조각들을 사용해 직사각형을 빈틈없이 채울 때 필요한 정사각형의 최소 개수를 구하는 것이 문제입니다.예를 들어 입력이 n = 2, m = 3이라면 다음과 같습니다.세 개의 정사각형 블록으로 직사각형을 완전히 덮을 수 있으므로 출력값은 3이 됩니다.해결 접근 방식이 문제는 DFS(깊이 우선 탐색)와 메모이제이션을 결합하여 해결할 수 있습니다. 핵심 아이디어는 각 열의 현재 채워진 높이를 추적하고, 항상 가장 낮은 위치부터 정사각형을 배치하면서 가

문제 개요양의 정수로 이루어진 배열 nums가 주어졌다고 가정해 봅시다. 배열에서 몇 개의 원소를 골라 부분 집합을 만들고, 선택된 각 원소에 임의의 정수를 곱한 뒤 모두 더했을 때 그 합이 1이 될 수 있다면, 이 배열을 좋은 배열(good array)이라고 부릅니다. 우리가 할 일은 주어진 배열이 좋은 배열인지 아닌지를 판별하는 것입니다.예를 들어 입력이 [12, 23, 7, 5]라면 결과는 True입니다. 5와 7을 선택해 5×3 + 7×(−2) = 1을 만들 수 있기 때문입니다.접근 방법: 베주 항등식과 GCD이 문제의 핵심

이번 문제는 단어 목록, 사용 가능한 개별 문자 목록, 그리고 각 문자별 점수가 주어졌을 때, 주어진 문자들로 만들 수 있는 유효한 단어 집합의 최대 점수를 구하는 것입니다.문제 이해하기문제의 핵심 조건은 다음과 같습니다.주어진 문자를 모두 사용할 필요는 없습니다.각 문자는 한 번만 사용할 수 있습니다.문자 a, b, c, ..., z의 점수는 각각 score[0], score[1], ..., score[25]에 해당합니다.예를 들어, 입력이 다음과 같다고 가정해 보겠습니다.words = [god, good, toc, cat]let

문제 소개유전자 문자열(gene string)은 길이가 8인 문자열로, A, C, G, T 네 가지 문자로만 구성됩니다. 여기서 하나의 돌연변이(mutation)란 유전자 문자열에서 단 한 글자를 다른 문자로 바꾸는 것을 의미합니다. 예를 들어 AACCGGTT에서 마지막 문자를 바꾼 AACCGGTA는 1회 돌연변이에 해당합니다.또한 유효한 유전자 변이들이 담긴 유전자 뱅크(bank)가 주어집니다. 어떤 유전자가 유효하려면 반드시 이 뱅크 안에 존재해야 합니다.세 가지 입력 — start(시작 유전자), end(목표 유전자), ban

숫자 리스트가 주어졌을 때, 주어진 모든 숫자 쌍(pair)에 대한 해밍 거리의 합계를 구해야 합니다. 여기서 해밍 거리(Hamming Distance)란 두 정수를 이진수로 표현했을 때, 서로 대응되는 비트 값이 다른 위치의 개수를 의미합니다.예를 들어 입력이 [4, 14, 17, 2]라면 출력은 17이 됩니다.문제 해결 접근 방법모든 쌍을 일일이 비교하면 O(n²)의 시간이 걸리므로 비효율적입니다. 대신 비트 자리별 카운팅 기법을 사용하면 훨씬 효율적으로 해결할 수 있습니다.핵심 아이디어는 다음과 같습니다. 특정 비트 자리에서

이 글에서는 무방향 그래프(Undirected Graph)에 존재하는 간선의 개수를 구하는 방법을 C++ 코드와 함께 알아보겠습니다.무방향 그래프란 여러 개의 정점(Vertex)이 서로 연결되어 하나의 그래프를 이루는 구조로, 모든 간선이 양방향으로 통행 가능한 그래프를 의미합니다. 즉, 어느 노드에서든 연결된 다른 노드로 자유롭게 이동할 수 있습니다.다음은 무방향 그래프의 시각적인 예시입니다.문제 정의그래프에서 간선(Edge)이란 두 정점을 잇는 선을 말합니다. 주어진 무방향 그래프에 간선이 총 몇 개 있는지 계산하는 것이 목표입

이번 문제의 목표는 중복된 요소를 포함하는 주어진 연결 리스트에서 최소 빈도(minimum frequency)를 가지는 요소의 개수를 세는 것입니다. 연결 리스트(Linked List)는 데이터를 순차적인 순서로 저장하는 자료구조로, 마치 목록처럼 각 요소가 다음 요소와 연결된 형태를 띱니다. 여기서 요소의 빈도(frequency)란 해당 요소가 연결 리스트 안에 등장하는 횟수를 의미합니다. 즉, 이 문제에서는 리스트 전체에서 가장 낮은 빈도를 찾고, 그 빈도에 해당하는 요소들의 개수를 계산해야 합니다. 예를 들어 1, 1, 3,

C++ STL에는 다양한 연관 컨테이너(Associative Container)가 존재하는데, 그중 가장 많이 사용되는 것이 바로 set과 unordered_set입니다. 두 컨테이너는 이름이 비슷해 헷갈리기 쉽지만, 내부 동작 방식과 성능 특성이 크게 다릅니다. 이번 글에서는 set과 unordered_set의 개념을 살펴보고, 각각을 언제 사용해야 하는지 그 차이점까지 자세히 알아보겠습니다.set이란 무엇인가?set은 정렬된(sorted) 고유한(unique) Key 타입 객체들을 저장하는 연관 컨테이너입니다. 각 요소는 오직