02

문제 설명 Longest Palindromic Substring - LeetCode 주어진 문자열 s에서 가장 긴 팰린드롬 부분 문자열을 찾는 문제입니다. ✅ 팰린드롬(Palindrome)이란? 앞에서 읽어도, 뒤에서 읽어도 동일한 문자열 예: "racecar", "madam", "a" ✅ 제약 조건 1 ≤ s.length ≤ 1000 반환값: 가장 긴 팰린드롬 부분 문자열 해설 1️⃣ 다이나믹 프로그래밍 (DP, O(N²)) DP 테이블을 사용하여 s[i:j+1]이 팰린드롬인지 저장 dp[i][j] = True → s[i:j+1]이 팰린드롬 점화식: s[i] == s[j]이고, j - i <= 2 (길이 2 이하) 또는 dp[i+1][j-1] == True 이면, dp[i][j] = True 시간 복잡도: O(N²) → 테이블 갱신이 O(N²) 2️⃣ 확장 중심 접근법 (Expand Around Center, O(N²)) 각 문자를 중심으로 팰린드롬 확장 (중심 확장) 홀수 길이 팰린드롬: "racecar" → 중심 e 짝수 길이 팰린드롬: "abba" → 중심 bb 시간 복잡도: O(N²) → 각 문자를 중심으로 O(N) 확장 코드 풀이 Python 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 def longestPalindrome(s: str) -> str: n = len(s) if n < 2: return s dp = [[False] * n for _ in range(n)] start, max_length = 0, 1 # 가장 긴 팰린드롬의 시작 위치와 길이 # 길이 1짜리 문자열은 항상 팰린드롬 for i in range(n): dp[i][i] = True # 길이 2 이상 문자열 검사 for j in range(1, n): for i in range(j): if s[i] == s[j] and (j - i <= 2 or dp[i+1][j-1]): dp[i][j] = True if j - i + 1 > max_length: # 더 긴 팰린드롬이면 갱신 start, max_length = i, j - i + 1 return s[start:start + max_length] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 def longestPalindrome(s: str) -> str: if len(s) < 2: return s def expand_around_center(left: int, right: int) -> str: while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 return s[left + 1:right] # 범위를 넘어간 부분을 제외 longest = "" for i in range(len(s)): odd_palindrome = expand_around_center(i, i) # 홀수 길이 even_palindrome = expand_around_center(i, i + 1) # 짝수 길이 longest = max(longest, odd_palindrome, even_palindrome, key=len) return longest Javascript 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 var longestPalindrome = function(s) { if (s.length < 2) return s; const expandAroundCenter = (left, right) => { while (left >= 0 && right < s.length && s[left] === s[right]) { left--; right++; } return s.slice(left + 1, right); }; let longest = ""; for (let i = 0; i < s.length; i++) { let oddPalindrome = expandAroundCenter(i, i); // 홀수 길이 let evenPalindrome = expandAroundCenter(i, i+1); // 짝수 길이 longest = oddPalindrome.length > longest.length ? oddPalindrome : longest; longest = evenPalindrome.length > longest.length ? evenPalindrome : longest; } return longest; }; 참고 및 출처 programmers Coding Test LeetCode - The World’s Leading Online Programming Learning Platform ...

문제 설명 Two Sum - LeetCode 정수 배열 nums와 목표 값 target이 주어졌을 때, 배열에서 두 수의 합이 target이 되는 두 개의 인덱스를 반환하는 문제입니다. ✅ 조건: 각 입력에 정확히 하나의 정답이 존재하며, 같은 요소를 두 번 사용할 수 없음. 정답은 어떤 순서로든 반환 가능함. 해설 1️⃣ 브루트포스 (Brute-force, O(N²)) 모든 가능한 두 수의 조합을 탐색하여 target과 비교 시간 복잡도: O(N²) → 비효율적 (배열 크기가 크면 실행 속도가 느림) 2️⃣ 해시맵(HashMap, O(N)) [추천] 한 번의 순회로 해결 target - nums[i] 값을 해시맵(dictionary)에 저장하여 빠르게 조회 시간 복잡도: O(N) → 매우 효율적 (빠른 검색 가능) 코드 풀이 Python 1 2 3 4 5 6 7 8 9 10 11 12 def twoSum(nums, target): num_map = {} # 딕셔너리 (해시맵) 선언 for i, num in enumerate(nums): complement = target - num # 목표 값에서 현재 숫자를 뺀 값 if complement in num_map: # 해시맵에서 찾기 return [num_map[complement], i] num_map[num] = i # 현재 숫자 저장 return [] # 결과가 없을 경우 (문제에서 항상 정답이 존재한다고 가정) Javascript 1 2 3 4 5 6 7 8 9 10 11 12 13 14 var twoSum = function(nums, target) { let numMap = new Map(); // 해시맵 선언 for (let i = 0; i < nums.length; i++) { let complement = target - nums[i]; if (numMap.has(complement)) { return [numMap.get(complement), i]; } numMap.set(nums[i], i); } return []; }; 참고 및 출처 programmers Coding Test LeetCode - The World’s Leading Online Programming Learning Platform ...

문제 설명 Edit Distance - LeetCode 두 개의 문자열 word1과 word2가 주어질 때, 첫 번째 문자열을 두 번째 문자열로 변환하기 위한 최소 편집 횟수를 구하는 문제입니다. ✅ 편집 연산 (Operations) 삽입 (Insert) → 문자를 추가 삭제 (Delete) → 문자를 제거 변경 (Replace) → 문자를 다른 문자로 변경 ✅ 제약 조건 0 ≤ word1.length, word2.length ≤ 500 최적화된 O(m × n) 알고리즘이 필요 해설 1️⃣ 재귀 (O(3^N)) → 비효율적 모든 가능한 연산을 수행하여 최소 값을 찾음 시간 복잡도 O(3^N) → 매우 비효율적 사용하지 않음 2️⃣ 동적 계획법 (DP, O(m × n)) [추천] ✔ DP 테이블을 사용하여 중복 연산을 제거 ✔ 점화식: ...

문제 설명 Valid Parentheses - LeetCode 해설 문제 설명 주어진 문자열 s가 유효한 괄호 문자열인지 확인하는 문제입니다. 문자열에는 다음과 같은 괄호만 포함될 수 있습니다. () (소괄호) {} (중괄호) [] (대괄호) ✅ 유효한 괄호 문자열의 조건: 열린 괄호는 반드시 닫힌 괄호와 짝을 이뤄야 함 닫힌 괄호가 열린 괄호보다 먼저 나오면 안 됨 괄호의 순서가 올바르게 짝을 이뤄야 함 예제 예제 1 1 s = "()" 🔹 출력: True (괄호가 올바르게 닫힘) 예제 2 1 s = "()[]{}" 🔹 출력: True (괄호 쌍이 모두 유효함) ...

문제 설명 Rotate Image - LeetCode 주어진 N × N 크기의 정사각형 행렬(matrix) 을 시계방향으로 90도 회전하는 문제입니다. ✅ 제약 조건 N × N (정사각형 행렬) 추가 행렬 없이(in-place) 변환해야 함 해설 1️⃣ 브루트포스 (새로운 행렬 사용) 새로운 행렬 rotated를 만들어 회전 후 복사 추가 메모리 사용 → 비효율적 (O(N²) 공간) 문제에서 추가 공간 없이 해결해야 하므로 사용 불가능 2️⃣ 최적화된 O(N²) 풀이 (전치 행렬 + 반전) [추천] ✔ 2단계 접근법으로 해결 가능 ...

문제 설명 Merge Sorted Array - LeetCode 해설 문제의 핵심 요구사항: 정렬된 두 배열 nums1과 nums2를 병합해야 합니다. nums1 배열의 길이는 m + n이며, 처음 m개의 요소만 유효한 값이고 나머지는 0으로 채워져 있습니다. 결과는 새로운 배열을 반환하는 것이 아니라 nums1 배열 자체를 수정해야 합니다. 최종 결과는 오름차순으로 정렬되어야 합니다. 이 문제를 해결하기 위한 가장 효율적인 접근 방법은 뒤에서부터 배열을 채워나가는 것입니다. 그 이유는: nums1의 뒷부분은 0으로 채워져 있어서 덮어쓸 수 있습니다. 두 배열이 이미 정렬되어 있으므로, 각 배열의 가장 큰 값부터 비교하여 더 큰 값을 nums1의 뒤에서부터 채워넣을 수 있습니다. 이 방식을 사용하면 추가적인 공간이 필요하지 않습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 Step 1: 마지막 위치(5)부터 시작 비교: 3 vs 6 → 6이 더 큼 nums1 = [1,2,3,0,0,6] Step 2: 다음 위치(4) 비교: 3 vs 5 → 5가 더 큼 nums1 = [1,2,3,0,5,6] Step 3: 다음 위치(3) 비교: 3 vs 2 → 3이 더 큼 nums1 = [1,2,3,3,5,6] Step 4: 다음 위치(2) 비교: 2 vs 2 → 같음 nums1 = [1,2,2,3,5,6] …계속 코드 풀이 Python 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: """ Do not return anything, modify nums1 in-place instead. """ # 포인터 초기화: p1은 nums1의 마지막 실제 요소, p2는 nums2의 마지막 요소 p1 = m - 1 p2 = n - 1 # p는 nums1의 마지막 위치 p = m + n - 1 # 뒤에서부터 큰 값을 채워넣기 while p2 >= 0: # nums2의 모든 요소를 처리할 때까지 # nums1의 현재 요소가 더 크고, 아직 처리할 요소가 남아있다면 if p1 >= 0 and nums1[p1] > nums2[p2]: nums1[p] = nums1[p1] p1 -= 1 # nums2의 현재 요소가 더 크거나, nums1의 처리할 요소가 없다면 else: nums1[p] = nums2[p2] p2 -= 1 p -= 1 Javascript 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 /** * @param {number[]} nums1 * @param {number} m * @param {number[]} nums2 * @param {number} n * @return {void} Do not return anything, modify nums1 in-place instead. */ function merge(nums1, m, nums2, n) { // 각 배열의 마지막 요소부터 시작하는 포인터 설정 let p1 = m - 1; // nums1의 실제 마지막 요소 위치 let p2 = n - 1; // nums2의 마지막 요소 위치 let p = m + n - 1; // nums1의 마지막 위치 // nums2의 모든 요소가 처리될 때까지 반복 while (p2 >= 0) { // nums1의 현재 요소가 더 크고, 아직 처리할 요소가 남아있다면 if (p1 >= 0 && nums1[p1] > nums2[p2]) { nums1[p] = nums1[p1]; p1--; } // nums2의 현재 요소가 더 크거나, nums1의 처리할 요소가 없다면 else { nums1[p] = nums2[p2]; p2--; } p--; } } 참고 및 출처 programmers Coding Test LeetCode - The World’s Leading Online Programming Learning Platform ...