인접 리스트(adjacency list) 형태로 표현된 방향 비순환 그래프(DAG, Directed Acyclic Graph)가 주어졌다고 가정해 봅시다. 이때 노드를 반복하지 않으면서 그래프에서 가장 긴 경로의 길이를 구하는 것이 목표입니다.예를 들어 아래와 같은 그래프가 입력으로 주어진 경우,경로 0 → 1 → 3 → 4 → 2의 길이가 4이므로 출력 결과는 4가 됩니다.해결 접근 방법이 문제는 깊이 우선 탐색(DFS)과 메모이제이션(Memoization)을 활용하면 효율적으로 해결할 수 있습니다. 각 노드에서 출발했을 때 도달

문자열 s가 주어지고, 이 문자열을 임의의 위치에서 정확히 한 번만 회전할 수 있다고 가정해 보겠습니다. 이때 이 연산을 통해 얻을 수 있는 가장 긴 회문(palindrome) 부분 문자열의 길이를 구하는 것이 목표입니다.예를 들어 입력이 s = elklev라고 해보겠습니다. el과 klev 사이에서 회전하면 levelk라는 문자열을 얻을 수 있으며, 여기서 가장 긴 회문 부분 문자열은 level이므로 결과는 5가 됩니다.풀이 접근 방법이 문제는 다음 단계를 따라 해결할 수 있습니다.s2 := 문자열 s를 두 번 이어 붙인 새로운

소문자로만 구성된 문자열 s가 주어졌을 때, 각 모음(a, e, i, o, u)이 모두 짝수 번 등장하는 가장 긴 부분 문자열(substring)의 길이를 찾는 문제를 풀어보겠습니다.예를 들어 입력이 s = anewcoffeepot이라면 결과는 10입니다. 부분 문자열 wcoffeepot에는 모음 o와 e만 포함되며, 두 모음이 각각 정확히 두 번씩 등장하기 때문입니다.접근 방법: 비트마스크(Bitmask) 활용모음은 총 5개이므로, 5비트짜리 비트마스크를 사용하면 각 모음의 등장 횟수 홀짝성(패리티)을 하나의 정수로 표현할 수 있

문자열 s와 숫자 k가 주어졌을 때, 서로 다른 문자가 최대 k개만 포함된 가장 긴 부분 문자열(substring)의 길이를 구하는 문제입니다.예를 들어, k = 3이고 s = kolkata라고 가정해 보겠습니다. 이 경우 정답은 4입니다. 서로 다른 3개의 문자를 포함하는 가장 긴 부분 문자열이 kolk와 kata 두 개이며, 둘 다 길이가 4이기 때문입니다.접근 방법: 슬라이딩 윈도우(Sliding Window)이 문제는 슬라이딩 윈도우 기법과 해시 맵(딕셔너리)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과

문제 개요1과 -1 두 값으로만 이루어진 리스트가 주어졌을 때, 원소들의 합이 정확히 0이 되는 가장 긴 연속 부분 목록(sublist)의 길이를 구하는 문제입니다.예를 들어 입력이 다음과 같다고 해보겠습니다.nums = [1, 1, -1, 1, 1, -1, 1, -1, 1, -1]이 경우 가장 긴 부분 목록은 [-1, 1, 1, -1, 1, -1, 1, -1]이며, 그 합은 0이므로 정답은 8이 됩니다.접근 방법: 누적 합(Prefix Sum)과 해시 맵모든 부분 목록을 일일이 확인하는 브루트포스 방식은 O(n²) 이상의 시간이

문제 소개리스트 nums와 정수 k가 주어졌을 때, 크기가 k인 모든 연속된 하위 리스트(부분 배열)에서 최댓값을 차례대로 구하는 프로그램을 만들어야 합니다. 이 유형은 흔히 슬라이딩 윈도우 최댓값(Sliding Window Maximum) 문제라고 불립니다.예를 들어 입력이 다음과 같다고 가정해 보겠습니다.nums = [12, 7, 3, 9, 10, 9], k = 3크기가 3인 하위 리스트는 [12, 7, 3], [7, 3, 9], [3, 9, 10], [9, 10, 9]로 총 네 개이며, 각각의 최댓값은 12, 9, 10, 10

문자열 s가 주어졌을 때, s의 뒤에 문자를 덧붙여 회문(palindrome)을 완성해야 한다고 가정해 보겠습니다. 이때 추가해야 하는 최소 문자 수를 구하는 것이 이 글의 목표입니다. 예를 들어 입력이 s = mad라면, 뒤에 am을 붙여 madam이라는 회문을 만들 수 있으므로 정답은 2가 됩니다. 반면 이미 회문인 madam이 입력되면 추가할 문자가 전혀 필요 없으므로 결과는 0입니다. 풀이 접근 방법 핵심 아이디어는 문자열에서 가장 긴 팰린드롬 접미사(suffix)를 찾는 것입니다. 팰린드롬 접미사가 시작되는 인덱스가

문제 설명서로 다른 단어로 이루어진 리스트가 주어졌을 때, 리스트에서 두 개의 서로 다른 단어를 골라 이어 붙였을 때 회문(palindrome), 즉 앞에서 읽으나 뒤에서 읽으나 같은 문자열이 되는 조합이 총 몇 가지인지 구하는 프로그램을 작성해 보겠습니다.예를 들어 입력이 words = [time, emit, mo, m]라고 한다면, 출력은 3이 됩니다. timeemit, emittime, mom의 세 가지 회문을 만들 수 있기 때문입니다.풀이 접근 방식이 문제는 다음과 같은 단계로 해결할 수 있습니다.결과를 저장할 변수 res를

문제 개요nums라는 숫자 리스트가 주어졌을 때, 숫자들 사이에 +(덧셈), -(뺄셈), *(곱셈)과 같은 이항 연산자를 자유롭게 삽입하고, 필요한 곳에 유효한 괄호를 추가하여 만들 수 있는 식 중에서 최댓값을 찾는 것이 목표입니다.예를 들어 nums = [-6, -4, -10]이 입력으로 주어진다면, 식을 ((-6) + (-4)) * -10처럼 구성할 수 있습니다. 이 식의 결과는 100이므로 출력값은 100이 됩니다.접근 방법: 동적 계획법(DP)이 문제는 동적 계획법(Dynamic Programming)을 활용해 효율적으로 해

문제 정의 길이가 모두 같은 세 개의 리스트가 있다고 가정해 보겠습니다. 바로 마감일(deadlines), 학점(credits), 소요 일수(durations)이며, 각 리스트는 과제 정보를 담고 있습니다. i번째 과제를 기준으로 각 리스트의 의미는 다음과 같습니다. deadlines[i] — 해당 과제의 마감일 credits[i] — 과제를 완료했을 때 받는 학점 durations[i] — 과제를 끝내는 데 필요한 일수 이때 지켜야 할 규칙은 다음과 같습니다. 한 과제를 완료하기 전에는 다른 과제를 시작할 수 없습니다. 마감

그래프가 인접 리스트(adjacency list) 형태로 주어져 있다고 가정해 보겠습니다. 이 그래프는 실제로 서로 연결되지 않은 여러 개의 트리, 즉 숲(forest)으로 구성되어 있습니다. 우리는 여기에 적절한 수의 간선을 추가해 전체를 하나의 트리로 만들어야 하며, 그때 임의의 두 노드 사이의 최장 경로 길이가 가능한 한 최소가 되도록 해야 합니다.예를 들어 위와 같은 입력이 주어지면 출력은 4가 됩니다.간선 0 → 5를 추가하면 최장 경로는 3 → 1 → 0 → 5 → 7 또는 4 → 1 → 0 → 5 → 7이 될 수 있으며

환율 정보가 담긴 N × N 표가 있다고 가정해 봅시다. 우리가 확인해야 할 것은 일련의 거래를 반복했을 때, 특정 통화로 시작한 금액 A보다 더 많은 금액을 같은 통화로 되돌려받을 수 있는 경로가 존재하는지 여부입니다. 이때 거래 수수료는 없으며, 소수점 단위의 거래도 가능하다고 가정합니다.문제 이해하기행렬에서 [i, j] 위치의 값은 통화 i 1단위로 구매할 수 있는 통화 j의 양을 의미합니다. 예를 들어 통화 0은 USD(미국 달러), 통화 1은 CAD(캐나다 달러), 통화 2는 EUR(유로)라고 해보겠습니다. 그러면 다음과

두 개의 양의 정수 n과 d가 주어졌다고 가정해 봅시다. 여기서 d는 0부터 9 사이의 한 자리 숫자입니다. 우리가 구해야 할 것은 1부터 n까지의 정수 안에 숫자 d가 총 몇 번 등장하는지입니다.문제 예시예를 들어 n = 45, d = 5가 입력으로 주어진다면, 출력 결과는 5가 됩니다.그 이유는 1부터 45 사이의 숫자 중 5라는 자릿수를 포함하는 숫자가 다음과 같기 때문입니다.[5, 15, 25, 35, 45]해결 접근 방법이 문제를 효율적으로 해결하기 위해 다음 단계를 따릅니다.solve() 함수를 정의합니다. 이 함수는 n

인접 리스트 형태로 표현된 무방향 그래프가 주어졌다고 가정해 보겠습니다. 여기서 graph[i]는 노드 i와 인접한 이웃 노드들의 목록을 의미합니다. 우리가 구해야 하는 것은 다음 조건을 만족하는 간선의 개수입니다. 조건: 해당 간선을 제거하면 그래프가 연결 상태를 잃고 분리되는 간선 그래프 이론에서 이런 간선은 브리지(bridge), 즉 절단 간선이라고 불립니다. 예를 들어 입력이 다음과 같다면, graph = [ [0, 2], [0, 4], [1, 2, 3], [0, 3, 4], [4],

문제 개요 숫자로 이루어진 리스트 nums가 주어졌다고 가정해 봅시다. 우리는 인덱스 조건 a < b < c < d를 만족하면서, 동시에 nums[a] < nums[b]이고 nums[c] > nums[d]인 사중조(quadruplet)의 개수를 구해야 합니다. 여기서 배열 nums는 1부터 N까지의 정수로 이루어진 순열(permutation)입니다. 예시로 이해하기 입력이 nums = [3, 4, 7, 6, 5]라면 출력은 5가 됩니다. 주어진 입력에서 찾을 수 있는 역전된 역전은 다음과 같습니다. (

두 개의 숫자 리스트 nums0과 nums1, 그리고 정수 k가 주어져 있다고 가정해 보겠습니다. 우리의 목표는 각 쌍이 nums0의 정수 하나와 nums1의 정수 하나로 구성되도록 하여, 합이 가장 큰 k개의 쌍을 찾는 것입니다. 그리고 선택된 모든 쌍의 합을 반환해야 합니다.예를 들어 입력이 nums0 = [8, 6, 12], nums1 = [4, 6, 8], k = 2라고 한다면, 출력은 38이 됩니다. 가장 큰 쌍은 [12, 8]과 [12, 6]이며, 각각의 합은 20과 18이므로 전체 합은 38입니다.문제 해결 접근 방식이

숫자로 이루어진 리스트와 정수 k가 주어졌을 때, 모든 인접한 요소 간의 절대 차이가 k 이하인 가장 긴 부분 수열(subsequence)의 길이를 구하는 프로그램을 만들어 보겠습니다. 예를 들어 입력이 nums = [5, 6, 2, 1, -6, 0, -1], k = 4라면 출력은 6이 됩니다. 실제로 [5, 6, 2, 1, 0, -1]처럼 인접 요소 간 차이(|5−6|=1, |6−2|=4, |2−1|=1, |1−0|=1, |0−(−1)|=1)가 모두 4 이하인 길이 6짜리 부분 수열을 만들 수 있기 때문입니다. 접근 방법: 세그먼

문제 개요음수가 아닌 숫자로 이루어진 리스트와 양의 정수 k가 주어졌을 때, 각 원소의 합이 k로 나누어떨어지는 부분 수열(subsequence) 중에서 가장 큰 합을 구하는 문제입니다.예를 들어 입력이 nums = [4, 6, 8, 2], k = 2라면 출력은 20이 됩니다. 리스트 전체의 합이 20이고, 20은 2로 나누어떨어지기 때문에 모든 원소를 포함한 부분 수열이 곧 정답이 됩니다.해결 접근 방법이 문제는 다음 단계를 따라 해결할 수 있습니다.입력 리스트 nums의 전체 합을 계산합니다. (numsSum)numsSum을 k

양의 정수로 이루어진 리스트가 주어졌다고 가정해 보겠습니다. 이때 우리는 값이 모두 같고 길이가 t인 연속된 부분 리스트를 제거할 수 있으며, 제거할 때마다 t × t점을 얻습니다. 이 작업은 리스트가 완전히 빌 때까지 원하는 만큼 반복할 수 있습니다. 목표는 이 과정에서 얻을 수 있는 최대 점수를 구하는 것입니다.문제 예시입력이 nums = [4, 4, 6, 4, 4]라고 한다면, 출력은 17이 됩니다.그 이유는 다음과 같습니다.먼저 가운데 있는 6(길이 1)을 제거하여 1 × 1 = 1점을 얻습니다.그러면 리스트가 [4, 4,

문제 개요이진 문자열 s와 두 개의 점수 값 zero_one, one_zero가 주어진다고 가정해 봅시다. 우리는 다음과 같은 연산을 수행할 수 있습니다.부분 문자열 01을 삭제하고 zero_one점을 획득부분 문자열 10을 삭제하고 one_zero점을 획득이때, 연산을 원하는 만큼 반복했을 때 얻을 수 있는 최대 점수를 구하는 것이 목표입니다.예를 들어, 입력이 s = 10100101, zero_one = 3, one_zero = 2라고 해보겠습니다. 이 경우 출력은 11이 됩니다. 그 이유는 다음과 같습니다.01을 세 번 제거하