네야의 IT 블로그

📘 문제: 가장 긴 팰린드롬 부분 문자열주어진 문자열 s에서, 가장 긴 팰린드롬(회문) 부분 문자열을 찾아서 반환하세요.팰린드롬이란 앞에서 읽든 뒤에서 읽든 동일한 문자열을 의미합니다.예: "aba", "racecar", "a"는 팰린드롬입니다. ✨ 예시예시 1입력: "babad"출력: "bab"(또는 "aba"도 정답으로 인정됩니다)예시 2입력: "cbbd"출력: "bb"⛓️ 제약 조건문자열 s의 길이는 최소 1, 최대 1000입니다.문자열 s는 영어 알파벳(az, AZ) 또는 숫자로만 구성됩니다.🔍 목표문자열 내에서 가장 긴 연속된 팰린드롬 부분 문자열을 찾아서 반환하는 프로그램을 작성하세요.🧠 핵심 아이디어문자열 s[i..j]가 팰린드롬인지 아닌지를 저장하는 DP 테이블을 만듭니다.dp[i][..

✅ 다이내믹 프로그래밍이란?복잡한 문제를 더 작은 문제로 나눠서 풀고,그 결과를 저장해두어 같은 계산을 반복하지 않는 방법이에요.📦 핵심 개념 2가지중복되는 하위 문제 (Overlapping Subproblems)👉 같은 계산을 여러 번 반복하는 문제최적 부분 구조 (Optimal Substructure)👉 큰 문제의 최적해가 작은 문제들의 최적해로 구성되는 경우이 두 가지가 있을 때 다이내믹 프로그래밍이 쓸 수 있어요.🎯 예시로 쉽게 이해해보자 (피보나치 수열)피보나치 수열은 다음과 같이 정의돼요:f(0) = 0 f(1) = 1 f(n) = f(n-1) + f(n-2) ❌ 나쁜 방법: 재귀만 쓰기 (중복 계산 많음)def fib(n): if n fib(5)를 계산하려면 fib(4)와 fib(..