✨ 자바로 푸는 가장 큰 증가하는 부분 수열 문제 풀이 📌 문제 개요 “가장 큰 증가하는 부분 수열” 문제는 다음과 같은 조건을 만족하는 부분 수열을 찾는 문제입니다. 수열 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 이..

✨ 자바로 푸는 전력난 문제 풀이 📌 문제 개요 “전력난” 문제는 모든 집(노드)을 전깃줄(간선)로 잇되,기존 모든 전선 설치 비용에서 최소한의 유지 비용만 남기기 위한 문제입니다. 즉, 모든 집이 연결되어야 하고최소한의 전기선만 남겨절약 가능한 비용을 구하는 것이 목표입니다. 이 구조는 전형적인 최소 신장 트리(MST) 문제입니다. 💡 예제 입력7 110 1 70 3 51 2 81 3 91 4 72 4 53 4 153 5 64 5 84 6 95 6 110 0 🛠 알고리즘 접근 방식 전체 간선 비용 합계를 구하고크루스칼 알고리즘으로 최소 신장 트리를 구성전체 비용 - MST 비용 = 절약된 전기 요금 ✅ 핵심 아이디어 간선을 비용 순으로 정렬하고,Union-Find(서로소 집합)을 통해 사이..

https://www.acmicpc.net/problem/11052 ✨ 자바로 푸는 카드 구매하기 문제 풀이 📌 문제 개요 N개의 카드를 구매해야 할 때, 각 카드팩은 카드 개수와 가격이 다르다.카드 N개를 구매하는 최대 금액을 구해야 한다.전형적인 완전 탐색 기반의 DP 최적화 문제. 💡 예제 입력4 1 5 6 7설명:카드 1개짜리 팩은 1원, 2개짜리 팩은 5원, …4개를 구매할 때 최대 금액을 구하는 문제. 🛠 알고리즘 접근 방식 dp[i]는 카드 i개를 구매할 수 있는 최대 비용을 의미.i장을 구매하려면:j장을 먼저 사고, 나머지 i-j장을 다시 구입할 수 있다.즉, dp[i] = max(dp[i], dp[i-j] + price[j]) 이때 모든 j에 대해 반복하면서 최대값 갱신...

https://www.acmicpc.net/problem/2193 ✨ 자바로 푸는 이친수 문제 풀이 📌 문제 개요 백준 2193번 “이친수” 문제는 특별한 조건을 가진 이진수의 개수를 세는 문제입니다. N자리 이친수란?0으로 시작하지 않음1이 두 번 연속으로 나올 수 없음 N자리 이친수가 총 몇 개 있는지 구하는 문제로, **DP(동적 계획법)**을 이용해 해결할 수 있습니다. 💡 예제 입력3 예제 출력2가능한 이친수: 100, 101 🛠 알고리즘 접근 방식 이 문제는 피보나치 수열과 유사한 점화식을 갖습니다. dp[i] = i자리 이친수의 개수N자리 이친수는N-1자리 이친수에 0 추가N-2자리 이친수에 10 추가 단, 연속된 1이 안 되도록 조건이 자연스럽게 반영됩니다. ✅ 핵심 아이..

https://www.acmicpc.net/problem/14501 ✨ 자바로 푸는 퇴사 문제 풀이 📌 문제 개요 백준 14501번 “퇴사” 문제는 퇴사를 앞둔 상담원이 남은 N일 동안 최대한 많은 수익을 올릴 수 있도록 상담 일정을 최적으로 조정하는 DP(동적 계획법) 문제입니다. 각 날짜별로 상담을 진행할 경우 소요되는 일수와 받을 수 있는 보상이 주어지며, 퇴사 전까지 끝나는 상담만 수행할 수 있습니다. 💡 예제 입력73 105 201 101 202 154 402 200 예제 출력45 🛠 알고리즘 접근 방식 dp[i]는 i일에 얻을 수 있는 최대 수익을 의미합니다.각 날짜 i에서 상담을 할 수 있다면, i + days[i]일에 dp[i] + pays[i]를 반영합니다.매일 상담을 하지..

https://www.acmicpc.net/problem/11062 ✨ 자바로 푸는 카드 게임 문제 풀이 📌 문제 개요 백준 11062번 “카드 게임” 문제는양 끝에서 카드를 번갈아 가져가는 두 플레이어가 있을 때, 첫 번째 플레이어가 얻을 수 있는 최대 점수를 계산하는 문제입니다. 이 문제는 두 사람 모두 최선의 선택을 할 때, 나의 점수를 최대화할 수 있는 방법을 찾아야 하므로,전형적인 DP(다이나믹 프로그래밍) 문제입니다. 💡 예제 입력144 7 2 9 ✅ 예제 출력13 🛠 알고리즘 접근 방식 구간 [s, e]에서 플레이어가 차례일 때,최적의 선택을 했을 때 얻을 수 있는 점수를 dp[s][e]로 정의합니다.합계 - 상대방 점수 방식으로 현재 플레이어 점수를 계산합니다.prefix[..

https://www.acmicpc.net/problem/1002 🎯 자바로 푸는 터렛 📌 문제 개요 두 터렛이 각각의 위치에서 일정한 반지름만큼의 범위를 감지한다.두 터렛이 동시에 감지할 수 있는 적의 위치 좌표 수를 구하는 문제이다. 터렛의 감지 범위는 원이 되고,두 원이 만나는 지점의 개수를 구하는 기하학적 문제이다. 🧪 예제 입력/출력 예제 입력30 0 13 40 0 370 0 3 0 7 41 1 1 1 1 5 예제 출력210 💡 핵심 아이디어 두 원이 만나거나, 만나지 않는 경우를 기하학적으로 분류하면 된다. 두 원의 중심 거리 = d반지름 각각 r1, r2조건설명결과d == 0 && r1 == r2원이 완전히 겹침 (무한히 많은 점)-1d > r1 + r2원이 서로 멀리 떨어..

https://www.acmicpc.net/problem/17413 🔄 자바로 푸는 단어뒤집기 2 📌 문제 개요 HTML 태그와 단어가 섞여 있는 문자열이 주어진다. 로 감싸진 부분은 그대로 출력하고나머지 단어들은 뒤집어서 출력해야 한다.단, 공백 단위로만 단어를 나누며, 태그 안에서는 문자를 뒤집지 않는다. 💡 예제 입력 & 출력 입력baekjoon online judge 출력noojkeab enilno egduj 입력tag 출력gat 🧠 알고리즘 접근 방식 문자열을 한 글자씩 순회하며,가 나오면 태그 시작 → isTag = true>가 나오면 태그 끝 → isTag = false태그 바깥에서는 단어를 StringBuilder에 저장하고, 공백이나 태그 시작 시 뒤집어서 출력마지막에 남..

https://www.acmicpc.net/problem/2644 👨‍👩‍👧 자바로 푸는 촌수 계산 (백준 2644) 📌 문제 개요 사람 수 n과 두 사람 x, y가 주어짐l개의 부모-자식 관계도 입력됨두 사람 간의 촌수를 계산하는 문제 촌수란? 부모와 자식은 1촌, 형제는 2촌부모-자식 관계만 주어지므로 그래프는 무방향 연결 그래프 💡 예제 입력97 371 21 32 72 82 94 54 6→ 7과 3의 관계는 다음과 같음:7 → 2 → 1 → 3 → 총 3촌 예제 출력3 🧠 알고리즘 접근 방식 각 사람을 정점으로 생각하고 양방향 그래프 구성DFS로 x부터 시작해서 y에 도달하는 경우를 탐색탐색 중 방문한 깊이 cnt를 통해 촌수를 구함 🔁 전체 코드import java.io..