문제 개요소문자 알파벳과 [, |, ] 같은 특수 문자로 이루어진 문자열 s가 있다고 가정해 보겠습니다. 여기서 [a|b|c]는 a, b, c 중 하나를 자유롭게 선택할 수 있음을 의미합니다. 우리의 목표는 문자열 s가 나타낼 수 있는 모든 가능한 값을 담은 리스트를 구하는 것입니다.단, 두 가지 제약 조건이 있습니다.대괄호 []는 서로 중첩될 수 없습니다.대괄호 안의 선택지 개수에는 제한이 없습니다.입력 예시s = [d|t|l]im[e|s]출력 예시[dime, dims, lime, lims, time, tims]첫 번째 대괄호에서

문제 개요하나의 문자열 s가 주어졌을 때, 분할된 각 부분 문자열이 모두 회문(palindrome)이 되도록 문자열을 나누는 방법이 몇 가지 있는지 구해야 합니다.예를 들어 입력이 s = xyyx라면 출력은 3이 됩니다. 가능한 분할 방법은 다음과 같습니다.[x, yy, x][x, y, y, x][xyyx]접근 방법: 동적 계획법(DP)이 문제는 동적 계획법을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.n := 문자열 s의 길이table := 크기가 n + 1인 리스트를 만들고 0으로 초기화table[

숫자 리스트 nums가 주어졌다고 가정해 보겠습니다. 이 리스트를 여러 개의 개별 하위 리스트(조각)로 나눈 뒤, 각 조각을 따로 정렬할 수 있습니다. 이때 구해야 하는 것은, 분할 후 각 조각을 정렬했을 때 nums 전체가 정렬된 상태가 되도록 만들 수 있는 하위 리스트의 최대 개수입니다.예시예를 들어 입력이 nums = [4, 3, 2, 1, 7, 5]라면 출력은 2가 됩니다. 리스트를 [4, 3, 2, 1]과 [7, 5] 두 개의 하위 리스트로 나누어 각각 정렬하면 [1, 2, 3, 4]와 [5, 7]이 되어, 이어 붙였을 때

숫자로 이루어진 리스트 nums와 정수 k가 주어졌을 때, 이 리스트를 서로 다른 두 요소끼리 짝지은 쌍(pair)들로 분할하되, 각 쌍의 합이 k로 나누어 떨어지도록 할 수 있는지 확인하는 문제입니다.예를 들어, 입력이 nums = [4, 7, 2, 5], k = 6이라면 결과는 True가 됩니다. 리스트를 (4, 2)와 (7, 5)로 분할하면 각 쌍의 합은 6과 12로, 모두 6으로 나누어 떨어지기 때문입니다.문제 해결 접근 방식이 문제는 나머지(remainder)의 성질을 이용하면 효율적으로 해결할 수 있습니다. 두 수의 합이

1과 0으로만 이루어진 리스트와 정수 k가 주어졌다고 가정해 봅시다. 리스트의 각 값은 감옥의 한 칸(cell) 상태를 나타내며, 1은 점유된 칸, 0은 비어 있는 칸을 의미합니다.매일 모든 칸은 다음 규칙에 따라 상태가 바뀝니다. 어떤 칸의 양옆에 인접한 두 칸이 서로 같은 상태(둘 다 점유 또는 둘 다 비어 있음)라면 해당 칸은 점유 상태(1)가 되고, 그렇지 않으면 빈 칸(0)이 됩니다. 우리가 구해야 하는 것은 k일이 지난 후 감옥 칸들의 최종 상태입니다.예를 들어 nums = [1, 0, 1, 0, 0, 0, 0, 0],

네 개의 숫자 리스트 A, B, C, D와 하나의 목표값(target)이 주어졌다고 가정해 봅시다. 이때 A[i] + B[j] + C[k] + D[l]의 합이 목표값과 같아지는 서로 다른 사중조(quadruple) (i, j, k, l)의 개수를 구하는 것이 문제입니다.예를 들어 입력이 다음과 같다면,A = [5, 4, 3]B = [8, 4]C = [6, 2]D = [4, 10]target = 23출력은 3이 됩니다. 조건을 만족하는 조합은 [5, 8, 6, 4], [3, 4, 6, 10], [3, 8, 2, 10] 세 가지이기 때

2차원 행렬이 하나 주어져 있고, 각 행에는 두 개의 값 [키, 카운트]가 담겨 있습니다. 여기서 키는 해당 사람의 신장을 의미하고, 카운트는 그 사람 앞에 서 있는 사람들 중 자신과 키가 같거나 더 큰 사람의 수를 뜻합니다. 이 대기열이 무작위로 섞여 있다고 가정할 때, 원래의 줄 서기 순서를 복원해야 합니다.문제 예시예를 들어 입력이 다음과 같다면,224050출력은 다음과 같습니다.405022해결 접근 방법이 문제를 해결하기 위해 다음 단계를 따릅니다.N := 행렬의 행 개수행렬의 행들을 키 오름차순, 같은 키라면 카운트 내림차

그레이 코드(Gray Code)는 이진수를 배열하는 특별한 방식으로, 연속된 두 숫자의 값이 정확히 한 비트만 차이 나도록 순서를 정하는 방법입니다. 그레이 코드의 예시는 [0, 1, 11, 10, 110, 111, ...]와 같습니다. 숫자 n이 주어졌을 때, 해당 숫자에 대한 그레이 코드(n번째 그레이 코드)를 구해야 한다고 가정해 봅시다. 예를 들어 입력이 n = 12라고 하면, 결과는 10이 됩니다. 12는 이진수로 (1100)이며, 여기에 대응하는 그레이 코드는 (1010)이고, 이 값의 십진수 표현은 10입니다. 문제

문자열 s와 정수 k가 주어졌을 때, 문자열에서 k개가 연속으로 이어진 중복 문자를 더 이상 찾을 수 없을 때까지 반복해서 삭제한 뒤, 최종 남은 문자열을 반환하는 문제입니다.문제 이해하기예를 들어 입력이 s = paaappmmmma, k = 3이라고 가정해 보겠습니다. 이때 기대되는 출력은 ma입니다.먼저 연속된 세 개의 a를 삭제하면 pppmmmma가 됩니다.다음으로 연속된 세 개의 p를 삭제하면 mmmma가 됩니다.마지막으로 네 개의 m 중 연속된 세 개를 삭제하면 ma가 됩니다.이처럼 각 단계에서 k개씩 묶어 중복 문자를 제

문제 개요 숫자로 구성된 리스트 target이 주어져 있다고 가정해 보겠습니다. 그리고 주어진 리스트와 길이가 같으며 모든 요소가 1로 채워진 리스트 X를 생각합니다. 우리는 다음과 같은 연산을 원하는 만큼 반복해서 수행할 수 있습니다. X에서 임의의 인덱스 i를 선택합니다. X[i]를 현재 X의 전체 합계 값으로 변경합니다. 목표는 이러한 연산을 반복하여 X를 target과 완전히 동일한 리스트로 만들 수 있는지 판별하는 것입니다. 예시로 이해하기 입력이 target = [5, 9, 3]이라면 출력은 True입니다. 변환

문제 개요 삼항식(ternary expression)을 담고 있는 문자열이 주어졌을 때, 이 식의 최종 결과를 평가하는 것이 목표입니다. 식은 참(True)과 거짓(False)을 나타내는 T, F와 함께 물음표 ?와 콜론 : 문자로 구성됩니다. 이 문제에는 다음과 같은 제약 조건이 적용됩니다. 주어진 문자열의 길이는 10,000 이하여야 합니다. 조건식은 오른쪽에서 왼쪽(right-to-left)으로 묶여 평가됩니다. 조건 부분은 항상 T 또는 F이며, 숫자 등 다른 값이 올 수 없습니다. 식의 최종 결과 역시 항상 T 또는 F입

연결 리스트가 하나 주어지고, 두 개의 인덱스 값 i와 j가 함께 주어진다고 가정해 보겠습니다. 이때 해야 할 일은 리스트의 i번째 노드부터 j번째 노드까지 해당하는 구간만 골라 순서를 거꾸로 뒤집고, 그 결과로 완성된 리스트를 반환하는 것입니다. (인덱스는 0부터 시작한다고 가정합니다.)예를 들어 입력이 [1,2,3,4,5,6,7,8,9]이고 i = 2, j = 6이라면, 인덱스 2부터 6까지의 노드들(값 3, 4, 5, 6, 7)이 뒤집혀 최종 출력은 [1, 2, 7, 6, 5, 4, 3, 8, 9]가 됩니다.문제 해결 접근 방

문자열 하나와 구분자(delimiter) 집합이 주어졌을 때, 구분자들의 상대적인 위치와 순서는 그대로 유지한 채 문자열 안의 단어들만 반대 순서로 뒤집는 문제를 생각해 볼 수 있습니다.예를 들어 입력이 s = Computer/Network:Internet|tutorialspoint, delims = [/, :, |] 라면, 출력은 다음과 같아야 합니다.tutorialspoint/Internet:Network|Computer해결 접근 방법이 문제는 파이썬의 itertools.groupby를 활용하면 깔끔하게 해결할 수 있습니다. 전

문제 소개두 개의 이진 트리(binary tree)가 주어졌을 때, 각 트리를 왼쪽에서 오른쪽 순서로 읽었을 때의 잎(leaf) 노드 시퀀스가 서로 동일한지 판별하는 프로그램을 작성해 보겠습니다. 여기서 잎 노드란 왼쪽과 오른쪽 자식을 모두 가지지 않는 노드를 의미합니다.예를 들어 아래와 같은 두 트리가 입력으로 주어진다고 가정해 봅시다.두 트리 모두 왼쪽에서 오른쪽으로 잎 노드를 읽으면 [2, 6]이 되므로, 결과는 True입니다.풀이 접근 방법이 문제는 중위 순회(inorder traversal)를 응용하면 깔끔하게 해결할 수

숫자로 이루어진 리스트 nums가 있고, 각 값은 해당 작업을 완료하는 데 걸리는 시간 단위를 나타낸다고 가정해 보겠습니다. 이때 연속되지 않은 작업은 자유롭게 건너뛸 수 있으며, 목표는 모든 작업을 마치는 데 필요한 최소 시간을 구하는 것입니다.예를 들어 입력이 nums = [11, 6, 8, 16]이라면 결과는 14가 됩니다. 첫 번째와 마지막 작업을 건너뛰면 되기 때문입니다.접근 방식: 동적 계획법(DP)이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각

이진 트리가 하나 주어졌을 때, 두 번째로 깊은 리프 노드의 깊이를 구하는 프로그램을 작성해 보겠습니다. 가장 깊은 리프 노드가 여러 개 존재하는 경우에는, 그다음으로 높은 깊이에 있는 노드가 두 번째로 깊은 노드가 됩니다. 참고로 루트 노드의 깊이는 0입니다.예를 들어 아래와 같은 트리가 입력으로 주어진다고 가정해 보겠습니다.이 경우 출력값은 1이 됩니다. 두 번째로 깊은 노드가 3이고, 그 깊이가 1이기 때문입니다.문제 해결 접근 방법이 문제는 트리를 레벨 단위(레벨 순서 순회)로 탐색하면서 각 레벨에서 처음 만나는 리프 노드의

숫자 리스트 items와 값 n이 주어졌다고 가정해 봅시다. 어떤 영업 사원이 무작위 ID를 가진 아이템들을 가방에 담고 있으며, 가방에서 최대 n개의 아이템을 제거(판매)할 수 있습니다. 우리의 목표는 n개를 제거한 후 가방에 남아 있는 서로 다른 ID의 최소 개수를 구하는 것입니다.예를 들어 입력이 items = [2, 2, 6, 6], n = 2라고 해봅시다. 이 경우 출력은 1이 됩니다. ID가 2인 아이템 두 개 또는 ID가 6인 아이템 두 개를 판매하면, 남은 아이템들은 하나의 ID만 가지게 되기 때문입니다.문제 해결 접

연결 리스트(linked list)가 하나 있다고 가정해 보겠습니다. 이 리스트를 오름차순으로 정렬해야 합니다.예를 들어 입력이 [5, 8, 4, 1, 5, 6, 3]이라면 출력은 [1, 3, 4, 5, 5, 6, 8]이 됩니다.문제 해결 접근 방법이 문제는 다음 단계를 따라 해결할 수 있습니다.values라는 새로운 빈 리스트를 생성합니다.head 변수에 현재 노드(node)를 저장합니다.node가 null이 아닐 때까지 반복합니다.노드의 값을 values 리스트의 끝에 추가합니다.node를 다음 노드로 이동시킵니다.values

2차원 행렬 mat이 주어졌을 때, 이 행렬의 요소들을 나선형(spiral) 형태로 출력하는 문제를 생각해 볼 수 있습니다. 먼저 첫 번째 행(mat[0][0])부터 시작하여 해당 행 전체를 출력하고, 이어서 마지막 열을 따라 내려간 후, 다시 마지막 행을 거꾸로 지나가고, 그다음 첫 번째 열을 위로 올라가는 식으로 안쪽으로 나선을 그리며 요소를 차례대로 출력합니다.예를 들어 다음과 같은 행렬이 입력으로 주어졌다고 가정해 보겠습니다.71092916239142759911그렇다면 출력 결과는 다음과 같습니다.[7, 10, 9, 1, 3

숫자로 이루어진 네 개의 리스트 A, B, C, D와 하나의 목표값(target)이 주어졌다고 가정해 봅시다. 이때 A[i] + B[j] + C[k] + D[l] ≤ target을 만족하는 서로 다른 고유 인덱스 조합 i, j, k, l의 개수를 구하는 것이 문제입니다.예를 들어 입력이 A = [3, 2], B = [5, 3], C = [1], D = [2, 3], target = 9라고 하면 출력은 3이 됩니다. 가능한 조합은 다음과 같습니다.[3, 3, 1, 2][3, 3, 1, 3][2, 3, 1, 3]문제 해결 접근 방식이