이진 트리 반전이란?이진 트리의 루트(root)가 주어졌을 때, 트리 전체를 좌우로 뒤집는 문제를 생각해 볼 수 있습니다. 즉, 루트의 왼쪽 서브트리와 오른쪽 서브트리를 서로 교환하고, 그 하위 자식 노드들 역시 재귀적으로 같은 방식으로 교환하는 것입니다.예를 들어 아래와 같은 트리가 입력으로 주어지면,반전 후에는 다음과 같은 형태가 됩니다.문제 해결 접근 방법이 문제는 재귀(Recursion)를 활용하면 매우 간단하게 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.노드를 인자로 받는 solve() 메서드를 정의합니다.현재

문제 정의0은 빈 칸을, 1은 도형을 이루는 블록을 의미하는 이진 행렬(binary matrix)이 주어졌을 때, 이 도형의 둘레(perimeter)를 계산하는 것이 목표입니다. 단, 도형 내부에는 구멍이 없다고 가정합니다.예를 들어 입력 행렬이 다음과 같다면,0000000111001100111000000출력 결과는 14가 됩니다.접근 방법핵심 아이디어는 간단합니다. 모든 블록은 기본적으로 네 변을 가지므로, 처음에는 각 블록이 둘레에 4만큼 기여한다고 생각합니다. 그러나 상하좌우로 인접한 셀에도 블록이 있다면, 서로 맞닿아 있는

문제 개요숫자 리스트 nums와 정수 k가 주어졌을 때, 크기가 k인 각 윈도우(연속된 부분 구간)에 포함된 서로 다른 숫자의 개수를 순서대로 담은 리스트를 구하는 프로그램을 작성해 보겠습니다.예를 들어 입력이 nums = [2, 2, 3, 3, 4], k = 2라고 가정하면, 윈도우는 차례대로 [2, 2], [2, 3], [3, 3], [3, 4]이고 각 윈도우의 고유한 숫자 개수는 1, 2, 1, 2이므로 최종 출력은 [1, 2, 1, 2]가 됩니다.풀이 접근 방법: 슬라이딩 윈도우 기법이 문제는 슬라이딩 윈도우(Sliding

문제 개요 여러 개의 스택으로 구성된 목록과 정수 k가 주어졌을 때, 임의의 스택 조합에서 정확히 k개의 요소를 팝(pop)하여 만들 수 있는 최대 합을 구하는 프로그램을 작성해야 합니다. 스택은 LIFO(후입선출) 구조이므로, 각 스택에서는 반드시 맨 위 요소부터 순서대로 꺼내야 한다는 점이 핵심입니다. 예를 들어 입력이 다음과 같다고 가정해 보겠습니다. stacks = [[50, -4, -15], [2], [6, 7, 8]], k = 4 이 경우 출력은 39입니다. 첫 번째 스택의 세 요소(-15, -4, 50)를 모두 팝하고,

단일 연결 리스트(singly linked list)가 하나 주어졌다고 가정해 보겠습니다. 이때 뒤에서 k번째(0 인덱스 기준)에 있는 노드의 값을 찾아야 하며, 이 문제는 단 한 번의 순회(single pass)만으로 해결해야 합니다. 예를 들어 입력이 node = [5, 4, 6, 3, 4, 7]이고 k = 2라면, 출력은 3이 됩니다. 뒤에서 두 번째 노드는 전체 리스트에서 인덱스 3에 해당하며, 그 노드의 값이 3이기 때문입니다. 해결 접근 방법: 두 포인터(Two-Pointer) 기법 리스트 길이를 먼저 계산한 뒤 다시

문제 개요정렬된 고유한 숫자로 이루어진 목록 nums와 정수 k가 주어졌을 때, 목록의 첫 번째 요소를 기준으로 k번째로 누락된 숫자를 찾아야 합니다.예를 들어, nums = [5,6,8,10,11], k = 1이 입력으로 주어지면 출력은 9입니다. 이 목록에서 누락된 숫자는 7과 9이며, 9는 두 번째(인덱스 1)에 해당하는 누락된 숫자이기 때문입니다.해결 접근 방식핵심 아이디어는 인접한 두 숫자 사이에 몇 개의 숫자가 누락되었는지 계산하고, k를 순차적으로 차감하면서 답이 위치한 구간을 찾는 것입니다.인덱스 1부터 목록의 끝까지

이진 탐색 트리(Binary Search Tree)와 정수 k가 주어졌을 때, 트리 안에서 k번째로 작은 값을 찾아야 하는 문제입니다.예를 들어 아래와 같은 트리가 있다고 가정해 보겠습니다.이때 k = 3이라면, 세 번째로 작은 값인 7이 출력됩니다.문제 해결 접근 방식이 문제는 중위 순회(In-order Traversal)를 활용하면 효율적으로 해결할 수 있습니다. 이진 탐색 트리를 중위 순회하면 노드 값이 오름차순으로 방문되기 때문에, 순회 도중 k번째로 방문한 노드의 값이 곧 k번째로 작은 값이 됩니다.스택을 사용한 반복적(i

문제 개요소문자 알파벳으로 구성된 문자열 s와 정수 k가 주어졌을 때, 결과 문자열이 최대 k개의 서로 다른 고유 문자를 갖도록 만들기 위해 필요한 최소 변경 횟수를 구하는 것이 목표입니다. 여기서 변경이란 문자열 내의 한 문자를 임의의 다른 문자로 바꾸는 작업을 의미합니다.예를 들어 입력이 s = wxxyyzzxx, k = 3이라면 정답은 1입니다. 문자 w를 x, y, z 중 하나로 바꾸면 문자열에는 x, y, z 세 종류의 고유 문자만 남기 때문입니다.해결 접근 방식이 문제는 그리디(Greedy) 기법으로 효율적으로 해결할 수

문자열로 이루어진 리스트 words가 주어졌을 때, 서로 애너그램(Anagram) 관계에 있는 단어들을 하나의 그룹으로 묶고, 그중 가장 큰 그룹의 크기를 반환하는 프로그램을 만들어 보겠습니다.예를 들어 입력이 다음과 같다고 가정해 봅시다.words = [xy, yx, xyz, zyx, yzx, wwwww]여기서 xyz, zyx, yzx는 모두 같은 문자들로 이루어진 애너그램이므로 하나의 그룹이 되고, 이 그룹의 크기는 3입니다. 따라서 출력 결과는 3이 됩니다.문제 해결 접근 방법애너그램의 핵심 특징은 문자를 사전순(lexicog

문제 개요숫자로 이루어진 리스트 nums와 정수 k가 주어졌다고 가정해 봅시다. 이때 nums에서 요소들을 선택하여 크기가 k인 리스트를 만들어야 하며, 그 리스트 안에서 가장 큰 값과 가장 작은 값의 차이가 최소가 되도록 해야 합니다. 최종적으로 우리는 이 차이를 반환하면 됩니다.예시입력이 다음과 같다고 해보겠습니다.nums = [3, 11, 6, 2, 9]k = 3이 경우 최적의 리스트는 [2, 3, 6]이며, 가장 큰 값 6과 가장 작은 값 2의 차이는 4입니다. 따라서 출력 결과는 4가 됩니다.해결 접근 방법이 문제는 정렬을

문제 정의 숫자로 이루어진 리스트 nums가 주어졌다고 가정해 봅시다. 리스트의 시작과 끝이 서로 이어져 있다고 생각하면, 이 리스트를 하나의 원형(circular) 리스트로 볼 수 있습니다. 우리가 구해야 할 것은 이 원형 리스트에서 비어 있지 않은 부분 리스트(sublist) 중 합이 가장 큰 값을 찾는 것입니다. 예를 들어 입력이 nums = [2, 3, -7, 4, 5]라면 출력은 14가 됩니다. 원형 구조 덕분에 [4, 5, 2, 3]처럼 리스트 끝에서 시작 부분으로 넘어가는 부분 리스트를 선택할 수 있고, 그 합이 4

배열 A가 주어졌을 때, 합이 최대가 되는 연속된 부분 배열(contiguous subarray)을 찾고 그 합을 반환하는 문제입니다. 예를 들어 배열 A = [-2, 1, -3, 4, -1, 2, 1, -5, 4]라면, 최대 합은 6이며, 이때의 부분 배열은 [4, -1, 2, 1]입니다.이 문제는 동적 프로그래밍(Dynamic Programming) 기법으로 효율적으로 해결할 수 있으며, 널리 알려진 카데인 알고리즘(Kadanes Algorithm)이 바로 이 방식에 기반합니다.알고리즘 접근 방식핵심 아이디어는 각 위치에서 이전

숫자로 이루어진 리스트 nums가 주어졌다고 가정해 봅시다. 우리는 이 리스트에서 서로 인접하지 않은(바로 옆에 붙어 있지 않은) 숫자들을 선택하여 얻을 수 있는 최대 합을 반환하는 함수를 작성하려고 합니다. 이때 리스트에는 0이나 음수도 포함될 수 있습니다. 예를 들어 입력이 [3, 5, 7, 3, 6]이라면 출력은 16이 됩니다. 3, 7, 6을 선택하면 세 숫자가 서로 인접하지 않으면서 합이 16으로, 가능한 모든 조합 중 가장 크기 때문입니다. 문제 해결 접근 방법 이 문제는 동적 계획법(Dynamic Programming)

이진 트리가 주어졌을 때, 임의의 두 노드를 연결하는 경로 중 합이 가장 큰 경로의 값을 찾아야 합니다. 여기서 말하는 경로란 트리 내에서 어떤 노드에서 시작해 다른 노드로 끝나는 일련의 노드 연결을 의미하며, 반드시 루트를 지날 필요는 없습니다.예를 들어 다음과 같은 이진 트리가 있다고 가정해 보겠습니다.이 경우 최대 경로 합은 62이며, 해당 경로에 포함된 노드는 [12, 13, 14, 16, 7]입니다.문제 해결 접근 방법이 문제는 재귀적 후위 순회(post-order traversal)를 활용해 효율적으로 해결할 수 있습니다

n×n 크기의 행렬이 하나 주어지며, 행렬의 값은 0부터 n 사이입니다. 이때 0은 아직 채워지지 않은 빈 칸을 의미합니다. 우리가 해야 할 일은 빈 칸들을 적절히 채워 각 행과 각 열마다 1부터 n까지의 모든 숫자가 정확히 한 번씩 등장하도록 만들 수 있는지 확인하는 것입니다. 예를 들어, 입력이 다음과 같다고 가정해 보겠습니다. 002201123 이 경우 출력은 True가 됩니다. 다음과 같이 행렬을 완성할 수 있기 때문입니다. 312231123 해결 접근 방식: 백트래킹 이 문제는 스도쿠(Sudoku) 퍼즐과 매우

문제 개요이진 트리(binary tree)가 하나 주어졌을 때, 트리의 모든 리프(잎) 노드가 동일한 레벨(깊이)에 위치하는지 확인하는 프로그램을 작성해야 합니다.예를 들어 아래와 같은 이진 트리가 입력으로 주어진다면,모든 리프 노드가 같은 깊이에 있으므로 출력 결과는 True가 됩니다.해결 접근 방법이 문제는 DFS(깊이 우선 탐색)를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 리프 노드에 도달했을 때의 깊이를 기록하고, 기록된 깊이 값들이 모두 같은지 검사하는 것입니다.알고리즘의 단계는 다음과 같습니다.dfs(

문제 개요이진 트리(binary tree)가 주어졌을 때, 가장 깊은 레벨에 있는 노드의 값을 찾아야 합니다. 만약 가장 깊은 레벨에 노드가 두 개 이상 존재한다면, 그중 가장 왼쪽에 있는 노드의 값을 반환해야 합니다.예를 들어 다음과 같은 이진 트리가 있다고 가정해 보겠습니다.이 경우 노드 4와 7이 모두 가장 깊은 레벨에 있지만, 4가 더 왼쪽에 위치하므로 출력 결과는 4가 됩니다.접근 방법: 레벨 순회(BFS)이 문제는 너비 우선 탐색(BFS), 즉 레벨 순회 방식으로 해결할 수 있습니다. 각 레벨을 순회할 때마다 해당 레벨의

문제 설명여는 괄호 (와 닫는 괄호 )로만 이루어진 문자열 s가 주어졌을 때, 가장 긴 균형 잡힌(balanced) 부분 수열의 길이를 찾아야 합니다.예를 들어, 입력 문자열이 s = ())(()( 라면 출력은 4가 됩니다. 왜냐하면 ()()와 같은 균형 잡힌 부분 수열을 만들 수 있기 때문입니다.해결 접근 방법이 문제는 문자열을 오른쪽에서 왼쪽으로 탐색하면서 그리디(greedy) 방식으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.닫는 괄호 )를 먼저 세어둡니다(close 카운터).여는 괄호 (를 만났을 때, 아직 매칭

문제 소개이진 트리가 하나 주어졌다고 가정해 보겠습니다. 이때 각 레벨의 노드 값들을 첫 번째 레벨은 왼쪽에서 오른쪽, 다음 레벨은 오른쪽에서 왼쪽 방향으로 번갈아 가며 순회한 결과를 출력해야 합니다. 이러한 순회 방식은 지그재그(Zigzag) 레벨 순회 또는 나선형(Spiral) 순회라고도 불립니다.예를 들어 입력 트리가 다음과 같다면,출력 결과는 다음과 같습니다.[5, -10, 4, -2, -7, 15]해결 전략: 두 개의 스택 활용이 문제는 두 개의 스택(stack)을 사용하면 효율적으로 해결할 수 있습니다. 스택의 LIFO(

이진 탐색 트리(Binary Search Tree)가 주어졌을 때, 이를 레벨 순서(level order) 순회 방식으로 단일 연결 리스트(singly linked list)로 변환하는 문제를 파이썬으로 해결해 보겠습니다.예를 들어 다음과 같은 이진 트리가 입력으로 주어지면,출력 결과는 다음과 같습니다.[5, 4, 10, 2, 7, 15]문제 해결 접근 방법이 문제는 BFS(너비 우선 탐색) 방식의 큐(queue)를 활용하면 간단하게 해결할 수 있습니다. 알고리즘의 동작 순서는 다음과 같습니다.더미(dummy) 헤드 노드 하나를 생