문제 소개 각 요소가 닫힌 구간 [start, end]를 나타내는 구간 목록이 주어졌다고 가정해 보겠습니다. 여기서 목표는 이 구간들이 중복 없이 실제로 덮는 총 고유 지속 시간(total unique duration), 즉 커버되는 전체 길이를 구하는 것입니다. 예를 들어 입력이 [[2, 11], [13, 31], [41, 61]]이라면 결과는 50입니다. 각 구간의 길이는 각각 (11 − 2 + 1) = 10, (31 − 13 + 1) = 19, (61 − 41 + 1) = 21이고, 세 구간이 서로 겹치지 않으므로 전체 합은

닫힌 구간(closed interval)으로 이루어진 두 개의 리스트가 있다고 가정해 보겠습니다. 각 리스트는 내부적으로 서로 겹치는 구간이 없으며, 시작 지점을 기준으로 비내림차순(오름차순과 유사하되 같은 값을 허용)으로 정렬되어 있습니다. 이때 해야 할 작업은 두 구간 리스트에서 서로 겹치는 부분을 모두 찾아, 비내림차순으로 정렬된 형태로 반환하는 것입니다.예를 들어 입력이 다음과 같다면,inv1 = [[50, 100], [190, 270], [310, 330]]inv2 = [[40, 120], [180, 190]]출력 결과는

문제 개요구간(interval) 목록이 주어졌을 때, 서로 겹치는 구간을 하나로 병합하여 정렬된 순서의 합집합을 구하는 문제입니다.예를 들어 입력이 inv = [[2, 5], [4, 10], [20, 25]]라면, [2, 5]와 [4, 10]이 서로 겹치므로 [2, 10]으로 병합되고, [20, 25]는 겹치지 않아 그대로 유지됩니다. 따라서 최종 출력은 [[2, 10], [20, 25]]가 됩니다.해결 접근 방법이 문제는 다음 단계를 통해 해결할 수 있습니다.구간 목록을 먼저 오름차순으로 정렬합니다.결과를 저장할 새로운 리스트(a

문제 이해하기서로 다른 숫자들로 구성된 리스트 nums가 주어졌다고 가정해 보겠습니다. 이때 두 가지 종류의 반전(inversion)을 정의할 수 있습니다.전역 반전(Global Inversion): 인덱스 i < j를 만족하면서 nums[i] > nums[j]인 경우지역 반전(Local Inversion): 인덱스 i에 대해 nums[i] > nums[i + 1], 즉 바로 인접한 두 원소의 순서가 뒤바뀐 경우우리가 확인해야 할 것은 전역 반전의 총개수와 지역 반전의 총개수가 서로 같은지 여부입니다.예를 들어 입력

두 개의 숫자 리스트 A와 B, 그리고 값 k가 주어졌을 때, A의 요소 중 B의 최소 k개 요소보다 엄격하게 작은 요소의 개수를 구하는 문제입니다.예를 들어 입력이 A = [6, -2, 100, 11], B = [33, 6, 30, 8, 14], k = 3이라면 결과는 3이 됩니다. 그 이유는 -2, 6, 11이 각각 B의 최소 3개 요소보다 작기 때문입니다.해결 접근 방법이 문제는 다음 단계를 통해 해결할 수 있습니다.k가 0이면 조건이 자동으로 만족되므로 A의 크기를 그대로 반환합니다.B를 내림차순으로 정렬합니다.카운터 변수

문제 개요음수가 아닌 정수로 구성된 리스트 nums와 양의 정수 k가 주어졌을 때, 길이가 2 이상이면서 원소들의 합이 k의 배수가 되는 연속된 부분 리스트(sublist)가 존재하는지 판별하는 프로그램을 작성해 보겠습니다.예를 들어 입력이 nums = [12, 6, 3, 4], k = 5라면 결과는 True입니다. 부분 리스트 [12, 3]의 합이 15이고, 15는 5로 나누어 떨어지기 때문입니다.접근 방법: 누적 합과 나머지 활용모든 부분 리스트를 일일이 확인하는 완전 탐색은 O(n²) 이상의 시간이 걸립니다. 하지만 누적 합(

문제 소개숫자로 이루어진 리스트 nums와 정수 k가 주어졌을 때, 합이 가장 큰 k개의 연속된 부분 리스트를 찾아 그 합들을 오름차순(비내림차순)으로 반환하는 프로그램을 작성해 보겠습니다.예를 들어 입력이 nums = [2, 4, 5, -100, 12, -30, 6, -2, 6], k = 3이라면 결과는 [10, 11, 12]가 됩니다. 합이 가장 큰 세 개의 부분 리스트는 각각 다음과 같습니다.[6, -2, 6] → 합 10[2, 4, 5] → 합 11[12] → 합 12해결 전략: 누적 합과 최소 힙이 문제는 누적 합(pref

두 값 r과 c가 주어졌다고 가정해 봅시다. 무한히 큰 체스판의 좌표 (0, 0)에 체스 나이트가 처음 놓여 있을 때, 목표 위치 (r, c)에 도달하기 위해 필요한 최소 이동 횟수를 구하는 것이 이번 문제의 목표입니다.나이트는 체스 규칙과 동일하게 움직입니다. 즉, 가로로 두 칸 그리고 세로로 한 칸 이동하거나, 반대로 세로로 두 칸 그리고 가로로 한 칸 이동합니다.예를 들어 입력이 r = 6, c = 1이라면 출력은 3이 됩니다. 아래 그림에서 빨간색은 시작 위치, 초록색은 최종 목적지, 노란색은 중간 경유 지점을 나타냅니다.문

문제 소개 네 개의 값 n, x, y, k가 주어졌다고 가정해 봅시다. 여기서 n은 n×n 크기의 체스판을 의미하고, 좌표 (x, y)는 나이트(knight)가 놓여 있는 위치를 나타냅니다. 나이트는 정확히 k번 이동해야 하며, 매 단계마다 8가지 방향 중 하나를 균등한 확률로 무작위 선택해 움직입니다. 우리가 구해야 할 값은 k번 이동을 마친 후 나이트가 여전히 체스판 위에 남아 있을 확률(가장 가까운 정수로 반올림한 백분율)입니다. 단, 나이트가 한 번이라도 체스판을 벗어나면 다시는 판에 들어올 수 없다는 조건이 붙습니다. 핵

문제 소개이진 트리가 하나 주어졌을 때, 임의의 노드와 그 자손(descendant) 노드 사이의 최대 절대 차이를 구하는 것이 목표입니다.예를 들어 아래와 같은 이진 트리가 입력으로 주어진다면,출력은 7이 됩니다. 루트 노드 1과 자손 노드 8 사이의 절대 차이 |8 − 1| = 7이 트리 전체에서 가장 크기 때문입니다.풀이 아이디어: 깊이 우선 탐색(DFS)핵심 아이디어는 간단합니다. 각 노드를 기준으로 그 서브트리(subtree) 안에 있는 값들의 최솟값과 최댓값을 재귀적으로 수집하면, 현재 노드와 자손들 사이의 차이는 다음

길이가 같은 두 개의 숫자 리스트 A와 B가 있다고 가정해 봅시다. 우리가 구해야 하는 것은 모든 0 ≤ i < j < n에 대해 다음 식의 최댓값입니다. |a[i] − a[j]| + |b[i] − b[j]| + |i − j| 예를 들어 입력이 A = [2, 4, 10, 6], B = [3, 4, 7, 5]라면 출력은 14가 됩니다. i = 0, j = 2일 때 |2 − 10| + |3 − 7| + |1 − 3| = 8 + 4 + 2 = 14이기 때문입니다. 접근 방법 절댓값이 포함된 식을 그대로 모든 쌍 (i, j)에

2차원 이진 행렬(binary matrix)이 주어졌다고 가정해 보겠습니다. 여기서 1은 육지를, 0은 물을 나타냅니다. 섬(island)이란 물에 둘러싸인 인접한 1들의 그룹을 의미하며, 행렬의 가장자리 역시 모두 물로 둘러싸여 있다고 가정할 수 있습니다. 우리가 구해야 하는 것은 이 행렬에서 가장 큰 섬의 면적, 즉 연결된 육지 칸(cell)의 최대 개수입니다.입력 예시예를 들어 입력이 다음과 같다면,001111100000000111100001100000000110000010첫 번째 줄의 육지 5칸과 세 번째·네 번째 줄에 걸쳐

숫자 리스트 nums와 정수 k가 주어졌다고 가정해 봅시다. 여기서 k는 nums를 k번 이어 붙여 만든 긴 리스트를 의미하며, 우리는 그 안에서 합이 가장 큰 연속된 부분 리스트(연속 부분 배열)의 합을 구해야 합니다. 예를 들어 입력이 nums = [2, 4, 5, -4], k = 1이라면 출력은 11이 됩니다. [2, 4, 5]처럼 앞의 세 원소를 선택했을 때 합이 11로 가장 크기 때문입니다. 접근 방법 이 문제는 유명한 카데인 알고리즘(Kadanes Algorithm)을 확장한 형태로 해결할 수 있습니다. 핵심 아이디어는

문제 소개 숫자 목록 nums가 원형으로 연결된 순환 리스트(circular list)를 나타낸다고 가정해 봅시다. 이때 서로 인접하지 않은 숫자들을 골라 만들 수 있는 최대 합을 구하는 것이 목표입니다. 예를 들어 입력이 nums = [10, 3, 4, 8]이라면 결과는 14가 됩니다. 10과 4를 선택하면 되는데, 10과 8은 순환 구조상 서로 인접해 있기 때문에 함께 선택할 수 없습니다. 해결 접근 방법 순환 리스트의 핵심 특징은 첫 번째 요소와 마지막 요소가 서로 인접한다는 점입니다. 따라서 이 문제를 다음 두 가지 독립적

문제 이해하기 타워들의 높이가 담긴 리스트와 양의 정수 k가 주어집니다. 우리는 k개의 타워를 선택한 뒤, 벽돌을 추가하여 선택한 타워들의 높이를 모두 동일하게 만들어야 하며, 이때 사용하는 벽돌의 개수를 최소화하는 것이 목표입니다. 즉, k개의 타워를 골라 같은 높이로 만들 때 필요한 최소 벽돌 수를 구하는 프로그램을 작성해야 합니다. 예를 들어, 입력이 heights = [5, 8, 32, 15, 41]이고 k = 3이라면 출력은 17이 됩니다. 높이가 5, 8, 15인 세 개의 타워를 선택하면, 모두 높이 15로 맞추는 데 (

문제 개요같은 길이를 가진 두 문자열 s와 t가 주어졌을 때, s의 어떤 순열 s1과 t의 어떤 순열 t1이 다음 조건 중 하나를 만족하는지 확인해야 합니다.모든 인덱스 i(0 ≤ i < n)에 대해 s1[i] ≤ t1[i]또는 모든 인덱스 i(0 ≤ i < n)에 대해 t1[i] ≤ s1[i]예를 들어 입력이 s = vyx, t = wzx라면 결과는 True입니다. s1 = vxy, t1 = wxz로 재배열하면 모든 위치에서 s1[i] ≤ t1[i]가 성립하기 때문입니다.해결 접근 방법이 문제는 정렬을 활용하면 간단하게

문자열 s가 회문(palindrome)이라고 가정해 봅시다. 우리는 단 한 글자만 변경하여 s가 더 이상 회문이 아니도록 만들어야 하며, 동시에 결과 문자열은 사전순(lexicographically)으로 가장 작아야 합니다.예를 들어 입력이 s = level이라면 출력은 aevel이 됩니다. 첫 번째 l을 a로 바꾸면 회문이 아닌 문자열 중에서 사전순으로 가장 앞서는 결과를 얻을 수 있기 때문입니다.접근 방법사전순으로 가장 작은 문자열을 만들려면 가능한 한 앞쪽 위치의 문자를 a로 바꾸는 것이 유리합니다. 다음 단계를 따릅니다.i를

데카르트 좌표평면 위의 점(좌표) 목록이 주어졌을 때, 이 점들이 하나의 직선 위에 놓여 있는지 판별하는 문제를 생각해 볼 수 있습니다.예를 들어 입력이 coordinates = [(5, 5), (8, 8), (9, 9)]라면, 세 점 모두 기울기가 1인 직선 위에 있으므로 결과는 True가 됩니다.문제 해결 접근 방법두 점만 있으면 항상 직선을 이루므로, 세 번째 점부터 나머지 모든 점이 앞의 두 점과 같은 직선 위에 있는지만 검사하면 됩니다. 기울기를 직접 나누어 계산하면 분모가 0이 되는 경우(수직선)를 따로 처리해야 하므로,

문제 개요단일 연결 리스트(singly linked list)와 하나의 값 target이 주어졌을 때, 리스트에서 target이 마지막으로 등장하는 노드만 제거하는 것이 목표입니다.예를 들어 입력 리스트가 [5,4,2,6,5,2,3,2,4,5,4,7]이고 target = 5라고 하겠습니다. 5는 총 세 번(앞에서 세 번째, 여섯 번째, 열 번째 위치) 등장하는데, 이 중 마지막 등장 하나만 제거하므로 결과는 다음과 같습니다.[5, 4, 2, 6, 5, 2, 3, 2, 4, 4, 7]해결 접근 방식이 문제는 리스트를 딱 한 번만 순회

연결 리스트(Linked List)가 하나 있다고 가정해 보겠습니다. 이 문제에서는 리스트의 앞쪽 절반을 뒤쪽 절반 위로 접어 올린 다음, 서로 겹치게 되는 노드들의 값은 합산하여 병합하고, 최종적으로 결과 연결 리스트의 헤드(head)를 반환해야 합니다.예를 들어 입력이 [5,8,1,2,4,7,5]라면 출력은 [2, 5, 15, 10]이 됩니다.문제 해결 접근 방식이 문제는 다음 단계를 따라 해결할 수 있습니다.노드 개수를 셀 변수 temp를 0으로 초기화합니다.포인터 ptr을 시작 노드로 설정한 뒤, 리스트 끝까지 이동하며 전체