소문자로만 이루어진 문자열 s가 주어졌다고 가정해 봅시다. 이 문제의 목표는 모든 알파벳이 최대 한 개의 조각에만 등장하도록 문자열을 최대한 많은 조각으로 분할한 뒤, 각 파티션(partition)의 크기를 리스트 형태로 반환하는 것입니다. 예를 들어 입력이 s = momoplaykae라면, 문자열은 [momo, p, l, ayka, e]처럼 다섯 개의 조각으로 나뉩니다. 모든 문자가 자신이 속한 조각 안에서만 등장하므로 조건을 만족하며, 따라서 출력은 [4, 1, 1, 4, 1]이 됩니다. 문제 해결 접근 방식 이 문제의 핵심은

문제 개요2차원 행렬(matrix)과 여러 값들이 주어집니다: row, col, erow0, ecol0, erow1, ecol1. 현재 우리의 위치는 matrix[row, col]이며, 이곳에서 출발해 matrix[erow0, ecol0]와 matrix[erow1, ecol1] 두 곳에 있는 금을 모두 줍고자 합니다.이동은 상하좌우 네 방향으로 자유롭게 할 수 있지만, 셀(r, c)에 도착할 때마다 해당 셀의 비용인 matrix[r, c]를 지불해야 합니다. 단, 같은 셀을 여러 번 방문하더라도 비용은 한 번만 지불합니다. 목표는

문제 설명 좌표 목록이 주어져 있다고 가정해 보겠습니다. 각 좌표는 x와 y 두 값을 가지며, 데카르트 좌표평면 위의 한 점을 나타냅니다. 우리가 구해야 하는 것은 하나의 직선 위에 동시에 놓여 있는 점들의 최대 개수입니다. 예를 들어 입력이 coordinates = [[6, 2], [8, 3], [10, 4], [1, 1], [2, 2], [6, 6], [7, 7]]이라면, [1, 1], [2, 2], [6, 6], [7, 7] 네 점이 하나의 직선(y = x) 위에 위치하고 있으므로 출력은 4가 됩니다. 접근 방법 핵심 아이디

문제 설명 (u, v) 형태의 간선 목록이 주어지며, 이 간선들은 하나의 트리를 구성한다고 가정해 보겠습니다. 이때 각 간선마다 해당 간선을 지나는 고유한 경로의 총 개수를 구하고, 결과를 입력된 순서 그대로 반환해야 합니다. 예를 들어 edges = [[0, 1], [0, 2], [1, 3], [1, 4]]가 입력으로 주어진다면, 출력은 [6, 4, 4, 4]가 됩니다. 알고리즘 접근 방법 이 문제를 해결하기 위해 다음 단계를 따릅니다 − 주어진 간선들로부터 인접 리스트(adj)를 생성합니다. count := 빈 맵(딕셔너리

문제 개요문자열 s와 정규 표현식 패턴 p가 주어졌을 때, 주어진 패턴이 문자열 전체와 일치하는지 확인하는 프로그램을 작성해야 합니다. 이 문제에서 정규 표현식은 다음 두 가지 규칙만 지원합니다.. (마침표) — 임의의 단일 문자 하나와 일치합니다.* (별표) — 바로 앞의 요소가 0번 이상 반복되는 경우와 일치합니다.예를 들어 입력이 pattern = h.l*o, s = hello라면 결과는 True입니다. h는 h와, .은 e와, l*은 연속된 ll과, 마지막 o는 o와 각각 일치하기 때문입니다.해결 접근 방법이 문제는 재귀(백

S-표현식(S-expression)이란?문자열 s가 S-표현식(S-expression)으로 주어졌을 때, 이를 평가하여 그 결과를 정수로 반환하는 프로그램을 작성해 보겠습니다.S-표현식은 하나의 숫자이거나, 괄호로 감싸진 재귀적인 표현식입니다. 예를 들어 (+ (- 3 2) (* 3 3))은 일반적인 수학 표기법으로 (3 - 2) + (3 * 3)과 같으며, 그 결과는 10이 됩니다. 사용할 수 있는 유효한 연산자는 +, -, *, / 네 가지입니다.예를 들어 입력이 s = (- (+ 3 2) 2)라면, 이는 ((3 + 2) - 2

0은 물을, 1은 육지를 나타내는 이진 행렬(binary matrix)이 주어졌다고 가정해 봅시다. 여기서 섬(island)이란 상하좌우 4방향으로 서로 연결된 1들의 묶음을 의미하며, 모든 섬은 물(0) 또는 행렬의 가장자리에 의해 둘러싸여 있습니다. 우리가 구해야 할 것은 두 섬을 연결하는 가장 짧은 다리의 길이입니다.문제 예시예를 들어 다음과 같은 입력이 주어진다고 해보겠습니다.001101100이 경우 출력 결과는 1이 됩니다. 즉, 좌표 (1,0)에 있는 섬과 좌표 (1,2)에 있는 섬을 다리 하나로 연결할 수 있다는 뜻입니

두 개의 문자열 s와 t가 주어졌을 때, 두 문자열을 모두 부분 수열(subsequence)로 포함하는 가장 짧은 문자열, 즉 최단 공통 초수열(Shortest Common Supersequence)의 길이를 구하는 문제입니다.예를 들어 입력이 s = pipe, t = people이라면 출력은 7이 됩니다. 이 경우 가능한 초수열 중 하나는 pieople입니다.해결 접근 방법이 문제는 최장 공통 부분 수열(LCS, Longest Common Subsequence)을 활용하면 효율적으로 해결할 수 있습니다. 두 문자열 길이의 합에서

문제 정의이진 행렬(binary matrix)이 주어졌을 때, 1은 육지(land), 0은 물(water)을 나타냅니다. 여기서 섬(island)이란 상하좌우로 인접한 1들의 그룹을 의미하며, 이 그룹은 물 또는 행렬의 가장자리에 의해 둘러싸여 있습니다.우리가 찾아야 할 대상은 물로 완전히 둘러싸인 섬, 즉 행렬의 가장자리와 맞닿아 있지 않은 섬입니다. 이런 섬을 모두 찾아내어 0으로 변경하는 것이 목표입니다. 단, 이웃 판정 시 대각선 방향은 제외하고 수평·수직 방향만 고려합니다.예시로 이해하기다음과 같은 입력이 주어졌다고 가정해

문제 설명숫자로 이루어진 리스트 nums와 정수 target이 주어졌을 때, 원소들의 합이 target과 같거나 그보다 큰 가장 짧은 연속 부분 리스트의 길이를 찾아야 합니다. 만약 조건을 만족하는 부분 리스트가 존재하지 않는다면 -1을 반환합니다.예를 들어 nums = [2, 11, -4, 17, 4], target = 19가 입력으로 주어지면 결과는 2가 됩니다. [17, 4]를 선택하면 합이 21이 되어 19 이상이라는 조건을 충족하기 때문입니다.접근 방법이 문제는 누적 합(prefix sum)과 단조 큐(monotonic d

0과 1로만 이루어진 이진 행렬(binary matrix)이 하나 주어졌다고 가정해 보겠습니다. 여기서 0은 빈 칸을, 1은 사람이 있는 칸을 의미합니다. 두 칸 사이의 거리는 x 좌표 차이와 y 좌표 차이 중 더 큰 값, 즉 체비셰프 거리(Chebyshev distance)로 정의됩니다. 만약 어떤 빈 칸이 존재하여 그 칸에서 행렬 안의 모든 사람까지의 거리와 행렬의 네 변(경계)까지의 거리가 모두 k 이상이라면, 이 행렬을 안전 인자(safety factor) k에 대해 안전하다고 말합니다. 우리가 구해야 하는 것은 바로 이

문제 소개 식물의 높이를 담은 숫자 리스트 heights와, 각 식물의 높이를 1만큼 올릴 때 드는 비용을 담은 리스트 costs가 주어집니다. 이때 인접한 식물끼리는 서로 다른 높이를 갖도록 만들어야 하며, 그렇게 하기 위해 필요한 최소 비용을 구하는 것이 목표입니다. 예를 들어 heights = [3, 2, 2], costs = [2, 5, 3]라고 한다면 정답은 3입니다. 세 번째 나무의 높이를 1만큼 올리면 비용이 3이 들고, 그 결과 높이는 [3, 2, 3]이 되어 인접한 나무들의 높이가 모두 달라지기 때문입니다. 풀이

문제 소개문자열 s가 주어졌다고 가정해 봅시다. 이 문자열은 어떤 더 긴 원본 문자열을 인코딩한 결과입니다. 인코딩 규칙은 다음과 같습니다.n(t)는 문자열 t를 n번 반복하여 이어 붙인 결과를 의미합니다.t는 일반 문자열일 수도 있고, 또 다른 인코딩된 문자열이 재귀적으로 포함될 수도 있습니다.예를 들어 입력이 s = 3(pi)2(3(am))0(f)1(u)라면, 디코딩된 출력은 pipipiamamamamamamu가 됩니다. 각 부분을 살펴보면 다음과 같습니다.3(pi) → pipipi2(3(am)) → amamamamamam (내

문제 개요 숫자로 구성된 목록 nums와 인덱스 값 pos가 주어졌을 때, 인덱스 pos를 반드시 포함하는 연속된 부분 리스트 A를 찾아 (A의 최솟값) × (A의 크기)가 최대가 되는 값을 구해 반환해야 합니다. 예를 들어 입력이 nums = [-2, 2, 5, 4], pos = 3이라면 결과는 8입니다. 가장 좋은 부분 리스트는 [5, 4]이며, 최솟값은 4, 크기는 2이므로 4 × 2 = 8이 되기 때문입니다. 접근 방법: 탐욕(Greedy) 알고리즘 이 문제는 탐욕 기법으로 효율적으로 해결할 수 있습니다. 시작 지점 pos

숫자로 이루어진 리스트 nums가 주어지고, 이 리스트에서 최대 한 개의 요소를 삭제할 수 있다고 가정해 보겠습니다. 이때 구해야 할 것은, 삭제가 끝난 뒤의 리스트에서 최댓값과 최솟값을 동시에 포함하는 연속 부분 리스트(sublist)의 최대 개수입니다. 예를 들어 입력이 nums = [3, 2, 6, 2, 4, 10]이라면 출력은 8이 됩니다. 값 10을 제거하면 리스트는 [3, 2, 6, 2, 4]가 되는데, 이때 최댓값 6과 최솟값 2를 모두 담고 있는 부분 리스트는 다음과 같이 여덟 개입니다. [2, 6] [6, 2]

문제 개요숫자 리스트 nums가 주어졌을 때, 하나의 수열 너비(width)는 그 수열 안에서 최댓값과 최솟값의 차이로 정의합니다. 이때 nums로 만들 수 있는 모든 부분 수열(subsequence)의 너비를 각각 구한 뒤, 그 합을 계산하는 것이 목표입니다. 단, 결과 값이 매우 커질 수 있으므로 109+7로 나눈 나머지를 반환해야 합니다.예를 들어 입력이 nums = [7, 4, 9]라고 해보겠습니다. 만들 수 있는 부분 수열은 [7], [4], [9], [7, 4], [7, 9], [4, 9], [7, 4, 9]이고, 각 수

문제 개요2차원 행렬과 정수 k가 주어졌을 때, 행렬 안에 존재하는 모든 k × k 부분 행렬(sub-matrix) 각각의 최솟값들을 모아 새로운 행렬로 반환하는 것이 이번 문제의 목표입니다.예를 들어, 다음과 같은 3×3 행렬이 입력으로 주어진다고 가정해 보겠습니다.3568654312여기서 k = 2라고 하면, 출력은 [[3, 5], [3, 3]]이 됩니다.부분 행렬별 최솟값 확인왼쪽 위 부분 행렬의 최솟값은 3입니다.3 5 8 6오른쪽 위 부분 행렬의 최솟값은 5입니다.5 6 6 5왼쪽 아래 부분 행렬의 최솟값은 3입니다.8 6

2차원 리스트 edges가 하나의 무방향 그래프를 나타낸다고 가정해 봅시다. 이 리스트의 각 항목은 (u, v, w) 형태의 간선 정보를 담고 있으며, 이는 노드 u와 v가 가중치 w를 가지는 간선으로 연결되어 있음을 의미합니다. 여기에 정수 a와 b가 추가로 주어지는데, 이 값들은 간선 (a, b)를 나타냅니다. 우리가 확인해야 할 것은 바로 이 간선 (a, b)가 최소 신장 트리(Minimum Spanning Tree, MST)의 일부에 해당하는지 여부입니다.참고: 그래프는 반드시 연결 그래프여야 하며, 간선 (a, b)는 그래

문제 정의단어 목록이 주어졌다고 가정해 보겠습니다. 이때 주어진 단어들을 서로 연결하여 하나의 원(circle) 형태로 만들 수 있는지 확인해야 합니다. 단어 A가 다른 단어 B 앞에 배치될 수 있는 유일한 조건은 A의 마지막 문자가 B의 첫 번째 문자와 동일할 때입니다. 또한 모든 단어를 빠짐없이 사용해야 하며, 각 단어는 정확히 한 번만 사용할 수 있습니다.예를 들어 입력이 다음과 같다면,[ant, dog, tamarind, nausea, gun]출력 결과는 True가 됩니다.알고리즘 접근 방식이 문제는 그래프 이론의 오일러 회

n개의 노드로 구성된 n-ary 트리가 인접 리스트 형태의 2차원 리스트 tree로 주어지고, 각 노드의 색상 정보는 리스트 color에 담겨 있습니다. 트리의 루트는 tree[0]에 해당합니다.문제 정의i번째 노드의 특성은 다음과 같습니다.tree[i]: i번째 노드의 자식 노드와 부모 노드 정보color[i]: i번째 노드의 색상어떤 노드 N을 루트로 하는 서브트리에 속한 모든 노드의 색상이 중복 없이 고유할 때, 이 노드 N을 특수(special) 노드라고 부릅니다. 즉, 주어진 트리에서 특수 노드가 총 몇 개인지 구하는 것이