02

문제 설명 Maximum Subarray - LeetCode 주어진 정수 배열 nums에서 연속된 서브어레이(subarray) 중 합이 가장 큰 값을 찾는 문제입니다. ✅ 제약 조건 1 ≤ nums.length ≤ 10⁵ -10⁴ ≤ nums[i] ≤ 10⁴ O(N) 이하의 시간 복잡도로 해결하는 것이 바람직 해설 1️⃣ 브루트포스 (O(N²)) → 비효율적 모든 가능한 부분 배열을 확인하며 최대 합을 찾음 시간 복잡도 O(N²) → 입력 크기가 크면 비효율적 2️⃣ 동적 계획법 (DP, O(N)) 점화식: dp[i] = max(dp[i-1] + nums[i], nums[i]) 즉, 현재 값을 새로운 서브어레이로 시작할지, 기존 서브어레이에 추가할지를 결정 시간 복잡도: O(N) 공간 복잡도: O(N) (배열 dp를 저장) 3️⃣ 카데인 알고리즘 (Kadane’s Algorithm, O(N)) [추천] DP에서 배열 저장 없이 최적화한 방법 현재 서브어레이 합이 음수라면 새로운 서브어레이 시작 시간 복잡도: O(N) 공간 복잡도: O(1) (배열 사용 없이 변수 2개만 사용) 코드 풀이 Python 1 2 3 4 5 6 7 8 9 def maxSubArray(nums): max_sum = nums[0] # 최대 합 current_sum = nums[0] # 현재 부분 배열의 합 for i in range(1, len(nums)): current_sum = max(nums[i], current_sum + nums[i]) # 현재 값 포함 여부 결정 max_sum = max(max_sum, current_sum) # 최댓값 갱신 return max_sum Javascript 1 2 3 4 5 6 7 8 9 10 11 var maxSubArray = function(nums) { let maxSum = nums[0]; let currentSum = nums[0]; for (let i = 1; i < nums.length; i++) { currentSum = Math.max(nums[i], currentSum + nums[i]); maxSum = Math.max(maxSum, currentSum); } return maxSum; }; 참고 및 출처 programmers Coding Test LeetCode - The World’s Leading Online Programming Learning Platform ...

문제 설명 Valid Palindrome - LeetCode 해설 코드 풀이 Python Javascript 참고 및 출처 programmers Coding Test LeetCode - The World’s Leading Online Programming Learning Platform

문제 설명 Search a 2D Matrix II - LeetCode 해설 코드 풀이 Python Javascript 참고 및 출처 programmers Coding Test LeetCode - The World’s Leading Online Programming Learning Platform

문제 설명 Broken Calculator - LeetCode 해설 코드 풀이 Python Javascript 참고 및 출처 programmers Coding Test LeetCode - The World’s Leading Online Programming Learning Platform

문제 설명 Lowest Common Ancestor of a Binary Tree - LeetCode 해설 코드 풀이 Python Javascript 참고 및 출처 programmers Coding Test LeetCode - The World’s Leading Online Programming Learning Platform

문제 설명 Find All Anagrams in a String - LeetCode 해설 코드 풀이 Python Javascript 참고 및 출처 programmers Coding Test LeetCode - The World’s Leading Online Programming Learning Platform

문제 설명 Longest Substring Without Repeating Characters - LeetCode 주어진 문자열 s에서 중복 문자가 없는 가장 긴 부분 문자열(substring) 의 길이를 반환하는 문제입니다. ✅ 부분 문자열(Substring) 조건: 연속된 문자만 포함해야 함 (순서를 바꾸면 안 됨) 중복 문자가 없어야 함 최대 길이를 반환 해설 1️⃣ 브루트포스 (O(N²)) - 비효율적 모든 가능한 부분 문자열을 생성하여 중복이 없는지 검사 → O(N²) 비효율적이므로 사용하지 않음 2️⃣ 투 포인터 + 해시셋 (슬라이딩 윈도우, O(N)) [추천] 해시셋(Set) 을 사용하여 중복 여부를 빠르게 검사 두 개의 포인터 (left, right) 를 사용하여 윈도우 크기를 조절 시간 복잡도: O(N) (각 문자를 한 번씩만 처리) 코드 풀이 Python 1 2 3 4 5 6 7 8 9 10 11 12 13 14 def lengthOfLongestSubstring(s: str) -> int: char_set = set() # 중복 문자를 빠르게 찾기 위한 해시셋 left = 0 # 윈도우의 왼쪽 포인터 max_length = 0 # 최대 길이 저장 for right in range(len(s)): # 오른쪽 포인터 이동 while s[right] in char_set: # 중복 문자가 있으면 왼쪽 포인터 이동 char_set.remove(s[left]) left += 1 char_set.add(s[right]) # 새로운 문자 추가 max_length = max(max_length, right - left + 1) # 최대 길이 갱신 return max_length Javascript 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 var lengthOfLongestSubstring = function(s) { let charSet = new Set(); // 중복 확인을 위한 해시셋 let left = 0; // 윈도우의 왼쪽 포인터 let maxLength = 0; // 최대 길이 저장 for (let right = 0; right < s.length; right++) { // 오른쪽 포인터 이동 while (charSet.has(s[right])) { // 중복 발생 시 왼쪽 포인터 이동 charSet.delete(s[left]); left++; } charSet.add(s[right]); // 새로운 문자 추가 maxLength = Math.max(maxLength, right - left + 1); // 최대 길이 갱신 } return maxLength; }; 참고 및 출처 programmers Coding Test LeetCode - The World’s Leading Online Programming Learning Platform ...

문제 설명 N-Queens II - LeetCode N × N 체스판에 N개의 퀸(Queen) 을 배치하는 유효한 방법의 개수를 찾는 문제입니다. ✅ 제약 조건 퀸은 서로 공격할 수 없음 (같은 행, 같은 열, 같은 대각선 배치 불가) 1 ≤ N ≤ 9 가능한 배치 방법의 개수만 반환하면 됨 ✅ 출력 형식 int 값으로 가능한 배치의 개수를 반환 해설 1️⃣ 브루트포스 (O(N!)) → 비효율적 모든 경우를 완전 탐색하며 배치 가능 여부를 확인 N! 개의 경우의 수 발생 비효율적이므로 사용하지 않음 2️⃣ 백트래킹 (Backtracking, O(N!)) [추천] DFS(깊이 우선 탐색) + 가지치기(Pruning) 사용 퀸을 하나씩 배치하며, 유망하지 않은 경우 즉시 백트래킹 O(N!)으로 해결 가능하며, N이 작을 경우 빠르게 동작 ✔ 배열을 사용하여 퀸 배치 유효성 검사 ...

문제 설명 N-Queens - LeetCode N × N 체스판에 N개의 퀸(Queen) 을 배치하는 문제입니다. 단, 퀸들은 서로 공격할 수 없어야 함 (즉, 같은 행, 같은 열, 같은 대각선에 배치되지 않아야 함). ✅ 출력 형식 가능한 모든 배치를 2D 리스트 형태로 출력 각 리스트는 N개의 문자열로 구성되며, Q는 퀸의 위치 .는 빈 칸을 의미 ✅ 제약 조건 1 ≤ N ≤ 9 백트래킹(Backtracking)을 사용하여 최적의 해를 탐색해야 함 해설 1️⃣ 브루트포스 (O(N!)) → 비효율적 모든 가능한 배치를 완전 탐색하여 조건을 확인 N! 개의 경우의 수 발생 비효율적이므로 사용하지 않음 2️⃣ 백트래킹 (Backtracking, O(N!)) [추천] DFS(깊이 우선 탐색) + 가지치기(Pruning) 사용 퀸을 하나씩 배치하며, 유망하지 않은 경우 즉시 백트래킹 O(N!)로 해결 가능하며, N이 작을 경우 빠르게 동작 ✔ 배열을 사용하여 퀸 배치 유효성 검사 ...

문제 설명 Minimum Path Sum - LeetCode 2D 격자(grid)에서 좌측 상단(0,0) → 우측 하단(m-1, n-1)으로 이동하는 최소 비용 경로를 찾는 문제입니다. 오른쪽 또는 아래쪽으로만 이동 가능 각 칸의 값은 해당 칸을 방문할 때 드는 비용 최소 비용 경로의 합을 반환 ✅ 제약 조건 1 ≤ m, n ≤ 200 (격자 크기) 0 ≤ grid[i][j] ≤ 100 (비용 값) O(m × n) 이하의 시간 복잡도로 해결하는 것이 바람직 해설 1️⃣ DFS + 백트래킹 (O(2^(m+n))) → 비효율적 모든 가능한 경로 탐색 → 시간 초과 O(2^(m+n)) → 너무 비효율적이므로 사용 불가 2️⃣ 동적 계획법 (DP, O(m × n)) [추천] 최적 부분 구조를 가지므로 DP를 활용 가능 점화식: dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] 즉, 위쪽 또는 왼쪽에서 오는 최소 비용 + 현재 위치 비용 시간 복잡도: O(m × n) 공간 복잡도: O(1) (grid를 직접 수정하여 사용 가능) 코드 풀이 Python 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 def minPathSum(grid): m, n = len(grid), len(grid[0]) # 첫 번째 행 초기화 (왼쪽에서 오는 값 누적) for j in range(1, n): grid[0][j] += grid[0][j - 1] # 첫 번째 열 초기화 (위쪽에서 오는 값 누적) for i in range(1, m): grid[i][0] += grid[i - 1][0] # DP 점화식 적용 for i in range(1, m): for j in range(1, n): grid[i][j] += min(grid[i - 1][j], grid[i][j - 1]) return grid[m - 1][n - 1] # 우측 하단 값 반환 Javascript 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 var minPathSum = function(grid) { let m = grid.length, n = grid[0].length; // 첫 번째 행 초기화 for (let j = 1; j < n; j++) { grid[0][j] += grid[0][j - 1]; } // 첫 번째 열 초기화 for (let i = 1; i < m; i++) { grid[i][0] += grid[i - 1][0]; } // DP 점화식 적용 for (let i = 1; i < m; i++) { for (let j = 1; j < n; j++) { grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]); } } return grid[m - 1][n - 1]; // 우측 하단 값 반환 }; 참고 및 출처 programmers Coding Test LeetCode - The World’s Leading Online Programming Learning Platform ...