https://www.acmicpc.net/problem/11048백준 11048번: 이동하기 문제 풀이 (Java)안녕하세요! 이번에는 백준 11048번 '이동하기' 문제를 Java로 해결하는 과정을 공유하려고 합니다. 이 문제는 주어진 미로에서 가장 많은 사탕을 얻는 경로를 찾는 동적 계획법(Dynamic Programming) 문제입니다.문제 분석(1, 1) 위치에서 시작하여 (N, M) 위치까지 이동하면서 사탕을 줍는 문제입니다. 이동은 오른쪽, 아래, 또는 오른쪽 아래 대각선으로만 가능합니다. 각 칸에 놓인 사탕의 개수가 주어졌을 때, 얻을 수 있는 사탕의 최대 개수를 구해야 합니다.해결 아이디어: 동적 계획법 (DP)이 문제는 DP를 사용하기에 아주 적합합니다. dp[i][j]를 '(i, j)..

# 백준 1309번: 동물원 문제 풀이 (Java) 안녕하세요! 오늘은 백준 알고리즘 1309번 '동물원' 문제를 Java로 해결하는 방법에 대해 알아보겠습니다. 이 문제는 동적 계획법(Dynamic Programming)을 활용하는 대표적인 문제입니다. ## 문제 이해 문제는 2xN 크기의 우리에 사자를 배치하는 경우의 수를 찾는 것입니다. 단, 사자들은 가로로도, 세로로도 붙어있을 수 없습니다. ## 해결 전략: 동적 계획법 이 문제는 N번째 줄에 사자를 어떻게 배치하는지에 따라 경우의 수가 달라집니다. N번째 줄의 상태는 다음 세 가지로 나눌 수 있습니다. 1. 사자를 배치하지 않는 경우2. 왼쪽 칸에만 사자를 배치하는 경우3. 오른쪽 칸에만 사자를 배치하는 경우 하지만 제공된 코드는 더 간결한 점..

✨ 자바로 푸는 타일 채우기 문제 풀이 📌 문제 개요 3×N 크기의 벽을 2×1, 1×2 타일로 채우는 경우의 수를 구하는 문제입니다.단, 타일은 겹치지 않고 벽을 완전히 채워야 합니다. 입력: 정수 N (1 ≤ N ≤ 30, N은 짝수만 의미 있음)출력: 벽을 채우는 모든 경우의 수 💡 예제 입력8 💡 예제 출력153 🛠 알고리즘 접근 방식 이 문제는 단순한 피보나치나 일반적인 dp[i] = dp[i-1] + dp[i-2] 형태로 해결되지 않습니다.특수 패턴이 반복적으로 등장하기 때문에 이에 맞는 점화식을 구성해야 합니다. ✅ 핵심 아이디어 홀수 크기(N % 2 == 1)인 경우 절대 채울 수 없습니다 → 경우의 수 0기본적으로는 dp[i] = dp[i - 2] * 3여기에 특수 타일 패..

✨ 자바로 푸는 합분해 문제 풀이 📌 문제 개요 정수 N과 정수 K가 주어졌을 때,정수 N을 K개의 정수의 합으로 나타내는 경우의 수를 구하는 문제입니다. 단, 0도 정수에 포함되며, 순서가 다른 것은 다른 경우로 칩니다. 💡 예제 입력20 2 💡 예제 출력21 🛠 알고리즘 접근 방식 이 문제는 전형적인 DP(동적 계획법) 문제입니다. dp[n][k] = 정수 n을 k개의 정수 합으로 표현하는 경우의 수 🔸 점화식 아이디어 dp[n][k] = dp[n-1][k] + dp[n][k-1] dp[n-1][k]: 마지막 수가 1 이상일 때, 전체 합에서 1을 빼고 다시 나누는 경우dp[n][k-1]: K-1개의 정수로 n을 만들고 마지막에 0을 더하는 경우 ✅ 핵심 초기값 dp[1][i] = ..

✨ 자바로 푸는 제곱수의 합 문제 풀이 📌 문제 개요 숫자 N이 주어졌을 때,N을 제곱수들의 합으로 표현하는 최소 항의 수를 구하는 문제입니다. 예를 들어 11 = 3² + 1² + 1² → 3개가능한 조합 중에서 가장 적은 수의 항으로 표현해야 합니다. 💡 예제 입력11 💡 예제 출력3 🛠 알고리즘 접근 방식 이 문제는 **DP(동적 계획법)**을 활용하여,N 이하의 제곱수들을 조합해서 가장 적은 개수로 N을 만드는 방법을 찾는 방식입니다. 🔸 점화식 dp[i] = min(dp[i - j*j] + 1)(단, j*j ≤ i인 모든 j에 대해) 즉, i에서 가능한 모든 제곱수(j²)를 뺀 후,그 나머지를 만드는 최소 개수(dp[i - j*j])에 1을 더해 최소를 구합니다. ✅ 핵심 아이..

✨ 자바로 푸는 가장 긴 감소하는 부분 수열 문제 풀이 📌 문제 개요 수열이 하나 주어졌을 때, 해당 수열에서 가장 긴 감소하는 부분 수열의 길이를 구하는 문제입니다. 예를 들어, 수열이 10 30 10 20 20 10이라면가장 긴 감소하는 부분 수열은 30 20 10 → 길이 3 👉 이 문제는 **Longest Decreasing Subsequence (LDS)**를 찾는 전형적인 DP 문제입니다. 💡 예제 입력6 10 30 10 20 20 10 💡 예제 출력3 🛠 알고리즘 접근 방식 **가장 긴 증가하는 부분 수열(LIS)**과 동일한 접근 방식이며,조건만 arr[j] > arr[i]로 바뀝니다. 🔸 DP 정의 dp[i]: i번째 원소를 마지막으로 하는 가장 긴 감소 수열의 길이 ..

✅ 문제 요약 STATION 테이블에서CITY 컬럼이 모음(a, e, i, o, u)으로 끝나는 도시만 선택중복 없이(DISTINCT) 출력 ✅ 정답 SQLSELECT DISTINCT CITYFROM STATIONWHERE CITY LIKE '%a' OR CITY LIKE '%e' OR CITY LIKE '%i' OR CITY LIKE '%o' OR CITY LIKE '%u'; SELECT DISTINCT CITYFROM STATIONWHERE LOWER(SUBSTRING(CITY,1,1)) IN ('a','e','i','o','u') AND LOWER(SUBSTRING(CITY,-1,1)) IN ('a','e','i','o','u');

✅ 문제 요약 STATION 테이블에서가장 짧은 CITY 이름가장 긴 CITY 이름 이름 길이가 같을 경우 알파벳순으로 가장 빠른 도시를 선택각각의 문자 길이도 함께 출력 ✅ 정답 쿼리 1. 최단 도시 이름SELECT CITY, LENGTH(CITY)FROM STATION ORDER BY LENGTH(CITY), CITY ASCLIMIT 1; LENGTH(CITY)로 문자 길이 정렬같은 길이일 경우 CITY 오름차순가장 위에 오는 한 건 출력 2. 최장 도시 이름SELECT CITY, LENGTH(CITY)FROM STATION ORDER BY LENGTH(CITY) DESC, CITY ASCLIMIT 1; LENGTH(CITY) 내림차순길이가 같을 경우 CITY 알파벳순최장 도시 1건 출력

✨ 자바로 푸는 가장 큰 증가하는 부분 수열 문제 풀이 📌 문제 개요 “가장 큰 증가하는 부분 수열” 문제는 다음과 같은 조건을 만족하는 부분 수열을 찾는 문제입니다. 수열 A에서 증가하는 부분 수열 중, 합이 가장 큰 부분 수열의 합을 구하라! 즉, 단순히 길이가 아니라 합이 최대인 증가 수열을 구하는 문제입니다. 💡 예제 입력10 1 100 2 50 60 3 5 6 7 8 💡 예제 출력113→ 부분 수열: 1 + 2 + 50 + 60 = 113 (또는 1 + 100) 🛠 알고리즘 접근 방식 이 문제는 **DP(동적 계획법)**을 통해 해결할 수 있습니다. 우리는 아래와 같은 배열을 정의합니다. dp[i]: i번째 수를 마지막으로 하는 증가 수열의 최대 합 이후, 앞의 원소들과 비교하며 ..

✨ 자바로 푸는 오르막 수 문제 풀이 📌 문제 개요 오르막 수란, 각 자릿수가 비내림차순(내림하지 않는 순서)으로 구성된 수를 말합니다.예를 들어 1234, 1123, 5555는 오르막 수입니다.321, 201과 같이 감소하는 수가 있는 경우는 오르막 수가 아닙니다. 문제 목표는길이가 N인 오르막 수의 개수를 구하는 것이며,정답은 10007로 나눈 나머지를 출력합니다. 💡 예제 입력1 💡 예제 출력10 🛠 알고리즘 접근 방식 이 문제는 DP(동적 프로그래밍) 을 사용해 해결할 수 있습니다.우리는 다음 조건을 만족하는 점화식을 세울 수 있습니다. dp[i][j] : 길이가 i이고, 마지막 자릿수가 j인 오르막 수의 개수dp[i][j] = dp[i][j+1] + dp[i-1][j]끝자리가 j 이..