이 문제에서는 n개의 범위(L, R)로 이루어진 2차원 배열 arr[][2]와 각각 정수 값을 담고 있는 Q개의 쿼리가 주어집니다. 우리의 목표는 각 쿼리의 숫자가 주어진 N개의 L-R 범위 중 하나에 속하는지 판별하는 프로그램을 작성하는 것입니다.문제 설명각 쿼리에 대해 해당 정수가 주어진 범위 중 적어도 하나에 포함되는지 확인해야 합니다. 만약 어느 하나의 범위에라도 속한다면 참(true)을 반환하고, 그렇지 않다면 거짓(false)을 반환합니다.단, 주어진 범위들은 서로 겹치지 않는다는 조건이 있습니다.예제로 문제 이해하기입력

이 문제에서는 원의 가장자리에 배치된 n개의 상자가 주어지고, 두 개의 정수 a와 b로 구성된 Q개의 쿼리가 제공됩니다. 우리의 과제는 각 쿼리에 대해 원 위의 상자들을 서로 연결할 수 있는지 확인하는 프로그램을 작성하는 것입니다. 문제 설명 각 쿼리를 처리할 때, 이전 쿼리에서 이미 연결된 막대들의 교차 상태를 방해하지 않으면서 상자 a와 상자 b를 막대로 연결할 수 있는지 판단해야 합니다. 조건을 만족하면 possible(가능), 만족하지 않으면 not possible(불가능)을 출력합니다. 예시로 문제 이해하기 입력 n = 6

문제 개요2차원 이진 행렬(0과 1로만 구성된 행렬)이 주어졌을 때, 모든 요소가 1인 부분 행렬(submatrix)의 총 개수를 구하는 것이 이번 문제의 목표입니다.예를 들어 입력 행렬이 다음과 같다고 가정해 보겠습니다.110110001이때 출력은 10이 됩니다. 그 이유를 살펴보면, 1×1 행렬 5개, 2×1 행렬 2개, 1×2 행렬 2개, 그리고 2×2 행렬 1개가 존재하기 때문입니다.접근 방법이 알고리즘의 핵심 아이디어는 각 행을 히스토그램의 바닥으로 보는 것입니다. 배열 temp의 j번째 원소는 현재 행에서 위 방향으로 연

문자열 str과, 각각 두 값 L과 R로 구성된 Q개의 쿼리가 주어졌을 때, 부분 문자열 [L…R]이 회문(palindrome)인지 판별하는 프로그램을 작성하는 것이 이번 문제의 목표입니다. 문제 설명 각 쿼리에 대해 주어진 범위 L~R에 해당하는 부분 문자열을 만들고, 앞으로 읽으나 뒤로 읽으나 같은 회문인지 아닌지를 확인해야 합니다. 예제로 이해하기 입력 str = abccbeba, Q = 3 Query[][] = {{1, 4}, {0, 6}, {4, 6}} 출력 Palindrome Not Palindrome Palindrome

이 문제에서는 크기가 n인 배열 arr[]와 각각 두 값 L, R로 이루어진 Q개의 쿼리가 주어집니다. 우리가 만들어야 할 프로그램은 각 쿼리에 대해 L번째로 작은 숫자와 R번째로 작은 숫자 사이의 절대 차이를 반환하는 것입니다.문제 설명각 쿼리를 해결하려면 먼저 L번째로 작은 원소와 R번째로 작은 원소가 원본 배열에서 어느 인덱스에 위치하는지 찾아야 합니다. 그런 다음 두 인덱스의 차이(절댓값)를 계산하면 됩니다.예제로 문제 이해하기입력arr[] = {8, 4, 1, 5, 2} Q = 2 Queries[][] = {{2, 4},

문제 개요 숫자 배열 nums가 주어졌을 때, 회문(palindrome) 형태의 부분 리스트(sublist)를 한 번의 연산으로 삭제할 수 있다고 가정해 봅시다. 이때 배열 전체를 비우기 위해 필요한 최소 연산 횟수를 구하는 것이 목표입니다. 예를 들어 입력이 nums = [6, 2, 4, 4, 2, 10, 6]이라면 정답은 2입니다. 먼저 가운데의 부분 리스트 [2, 4, 4, 2]를 제거하면 [6, 10, 6]이 남습니다. 이 배열 역시 회문이므로 한 번 더 제거하면 배열이 완전히 비워집니다. 접근 방식: 구간 DP와 메모이제이

두 개의 소문자 문자열 s와 t가 주어졌다고 가정해 보겠습니다. 여기서 수행할 수 있는 연산은, 문자열 s에 등장하는 특정 문자의 모든 위치를 다른 문자로 한꺼번에 바꾸는 것입니다. 이 연산은 원하는 만큼 몇 번이든 반복할 수 있으며, 우리는 이 과정을 거쳐 s를 t로 변환할 수 있는지 판별해야 합니다. 예를 들어 입력이 s = eye, t = pip라고 해보겠습니다. 이 경우 출력은 True가 됩니다. 문자 e가 등장하는 모든 자리를 p로 바꾼 뒤, y를 i로 바꾸면 pip를 얻을 수 있기 때문입니다. 문제 해결 접근 방식 핵심

문제 개요 이 문제에서는 크기가 N인 배열 arr[]와 두 가지 유형으로 나뉘는 Q개의 쿼리가 주어집니다. 우리가 작성해야 할 프로그램은 주어진 인덱스의 값을 갱신하거나 특정 범위 내 요소들의 최대공약수(GCD)를 구하는 쿼리를 처리해야 합니다. 쿼리는 다음과 같은 형식으로 구성됩니다. 유형 1 − {1, index, value} : 주어진 인덱스에 있는 요소의 값을 value만큼 증가시킵니다. 유형 2 − {2, L, R} : 인덱스 범위 [L, R]에 포함된 요소들의 GCD를 구합니다. 문제 설명 − 범위 [L, R]에 속한 요

이 문제에서는 N개의 정점으로 이루어진 트리와, 두 개의 값 i와 j로 구성된 Q개의 쿼리가 주어집니다. 우리가 작성해야 하는 프로그램은 트리 안에서 두 노드 사이의 조상-후손(ancestor-descendant) 관계를 판별하는 쿼리를 처리하는 것입니다.즉, 각 쿼리마다 노드 i가 노드 j의 조상인지 여부를 확인해야 합니다.문제 이해를 돕는 예시입력Q = 2, query[][] = {{3, 5}, {1, 6}}출력No Yes설명i = 3, j = 5 : 노드 3은 노드 5의 조상이 아니므로 NO를 출력합니다. i = 1, j =

문제 개요숫자 목록 nums가 주어졌을 때, 인덱스 순서가 i < j < k를 만족하면서 동시에 nums[i] < nums[k] < nums[j]가 성립하는 삼중항 (i, j, k)이 존재하는지 확인해야 합니다.예를 들어 입력이 nums = [2, 12, 1, 4, 4]라면 결과는 참(True)입니다. 인덱스 (0, 1, 3)에 해당하는 값들 [2, 12, 4]가 2 < 4 < 12 조건을 충족하기 때문입니다.풀이 전략이 문제는 흔히 “132 패턴” 문제로 알려져 있으며, 세 겹의 반복문을 사용하는

문제 개요여러 개의 리스트가 주어졌을 때, 각 리스트에서 하나의 값을 선택한 뒤 그 값들 중 최댓값과 최솟값의 차이를 계산합니다. 이렇게 만들 수 있는 차이 중 가장 작은 값을 찾는 것이 이 문제의 목표입니다.예를 들어 입력이 다음과 같다고 가정해 보겠습니다.lists = [[30, 50, 90], [85], [35, 70]]첫 번째 리스트에서 90, 두 번째 리스트에서 85, 세 번째 리스트에서 70을 선택하면 최댓값 90과 최솟값 70의 차이는 20이 됩니다. 따라서 출력은 20입니다.해결 접근 방법이 문제는 우선순위 큐(pri

문제 소개 숫자로 이루어진 리스트 nums와 정수 k가 주어졌다고 가정해 봅시다. 이 리스트를 비어 있지 않은 k개의 부분 리스트(sublist)로 나누려고 할 때, 각 부분 리스트의 원소 합 중 최댓값이 최소가 되도록 분할해야 합니다. 예를 들어 입력이 nums = [2, 4, 3, 5, 12], k = 2라면, 리스트를 [2, 4, 3, 5]와 [12]로 나눌 수 있습니다. 두 구간의 합은 각각 14와 12이므로, 이때 최댓값인 14가 정답이 됩니다. 풀이 전략: 이분 탐색과 탐욕적 검증 이 문제는 이분 탐색(Binary Se

문제 개요소문자로만 이루어진 문자열 s가 주어졌을 때, 각 부분 문자열이 모두 회문(palindrome)이 되도록 문자열을 최소한의 조각으로 분할하고, 그 결과 얻어지는 문자열의 개수를 구하는 프로그램을 작성해야 합니다.예를 들어 입력이 s = levelracecar라면, level과 racecar라는 두 개의 회문으로 나눌 수 있으므로 출력은 2가 됩니다.해결 접근 방법이 문제는 동적 계획법(Dynamic Programming)을 활용하여 해결할 수 있습니다. 문자열의 끝에서부터 앞쪽으로 탐색하면서, 각 위치 i에서 시작했을 때

문제 개요2차원 행렬이 주어졌을 때, 모든 원소가 동일한 값으로 이루어진 가장 큰 k×k 정사각형 부분 행렬을 찾아 그 크기 k를 구하는 것이 이번 글의 목표입니다.예를 들어 입력 행렬이 다음과 같다고 가정해 보겠습니다.1183155525554555위 행렬에는 값 5로만 이루어진 3×3 정사각형이 존재하므로, 정답은 3이 됩니다.풀이 접근 방법이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.dp[i][j]는 (i, j) 위치를 좌상단 꼭짓점으로

문제 설명 문자열의 위치를 나타내는 브레이크포인트(breakpoints)라고 불리는, 중복 없이 정렬된 숫자 목록이 있다고 가정해 보겠습니다. 이 값들을 사용해 아래 규칙에 따라 하나의 트리를 만들려고 합니다. (a, b) 형태의 값을 가지는 노드가 존재하며, a와 b는 브레이크포인트입니다. 즉, 해당 노드는 문자열에서 [a, b] 구간을 담당합니다. 루트 노드는 전체 문자열, 즉 모든 브레이크포인트 범위를 포괄합니다. 노드의 왼쪽 자식과 오른쪽 자식의 구간은 순서대로 배치되고 서로 연속적이며, 두 구간을 합치면 부모 노드의 구

2차원 행렬이 하나 주어지고, 행렬의 각 원소는 지형의 높이를 나타낸다고 가정해 보겠습니다. 비가 내려서 계곡의 모든 움푹 들어간 공간이 물로 차오르는 상황을 상상할 수 있습니다. 이때 우리가 구해야 할 것은 계곡 사이에 고이게 되는 빗물의 총량입니다. 예를 들어 입력이 다음과 같다면, 666864586666 출력은 3이 됩니다. 높이가 4와 5인 칸 사이에 물 3단위를 담을 수 있기 때문입니다. 문제 해결 접근 방법 이 문제는 행렬의 바깥쪽 경계부터 시작해 안쪽으로 탐색을 넓혀가는 방식으로 해결할 수 있습니다. 경계에 있는 칸은

문제 설명문자열 s와 정수 k가 주어졌다고 가정해 봅시다. 우리는 s에서 몇 개의 부분 수열(subsequence)을 선택하여 서로 다른 부분 수열 k개를 확보해야 합니다. 이때 하나의 부분 수열을 선택하는 비용은 (s의 길이) − (부분 수열의 길이)로 정의됩니다. 따라서 k개의 고유한 부분 수열을 선택했을 때 가능한 최소 총비용을 구해야 하며, 조건을 만족하는 집합을 찾을 수 없다면 -1을 반환합니다. 참고로 빈 문자열도 유효한 부분 수열로 간주합니다.예를 들어 입력이 s = pqrs, k = 4라면 출력은 3이 됩니다.접근 방

문제 개요각 원소가 [x, y] 형태의 유클리드 좌표를 나타내는 좌표 목록이 주어졌다고 가정해 봅시다. 이때 우리가 구해야 하는 것은 주어진 좌표들 중 임의의 두 점에 대한 가장 작은 제곱 거리, 즉 (x1 - x2)2 + (y1 - y2)2의 최솟값입니다.예를 들어 입력이 coordinates = {{1, 2}, {1, 4}, {3, 5}}라면, 점 (1, 2)와 (1, 4) 사이의 제곱 거리가 4로 가장 작으므로 출력은 4가 됩니다.해결 접근 방법모든 점 쌍을 일일이 비교하는 O(n²) 완전 탐색 대신, 배열을 정렬한 뒤 map

숫자로 이루어진 리스트 nums가 주어졌을 때, 이 리스트에서 만들 수 있는 모든 홀수 길이 부분 배열(sublist)의 중앙값들을 모두 더한 합계를 구하는 문제입니다.예를 들어 입력이 nums = [2, 4, 6, 3]이라면 출력은 23이 됩니다. 홀수 길이 부분 배열은 다음과 같습니다.길이 1: [2], [4], [6], [3]길이 3: [2, 4, 6], [4, 6, 3]각 부분 배열의 중앙값은 순서대로 2, 4, 6, 3, 4, 4이므로, 이들의 합은 2 + 4 + 6 + 3 + 4 + 4 = 23입니다.문제 해결 접근 방식

문제 소개 숫자 목록 row가 주어졌다고 가정해 보겠습니다. 이 목록은 일렬로 놓여 있는 양말들을 나타내며, 현재는 정렬되어 있지 않습니다. 우리의 목표는 각 양말 쌍이 (0, 1), (2, 3), (4, 5)처럼 서로 나란히 위치하도록 재배열하는 것이고, 이때 필요한 최소 스왑(교환) 횟수를 구해야 합니다. 예를 들어 입력이 row = [0, 5, 6, 2, 1, 3, 7, 4]라면 출력은 2가 됩니다. 실제 정렬 과정은 다음과 같습니다. [0, 5, 6, 2, 1, 3, 7, 4] [0, 1, 6, 2, 5, 3, 7, 4]