https://www.acmicpc.net/problem/10942 🔁 자바로 푸는 펠린드롬? 문제 풀이 (백준 10942) 📌 문제 개요 수열이 주어졌을 때, 특정 구간이 펠린드롬(회문)인지 빠르게 판별해야 하는 문제입니다.질의가 최대 100만 번까지 주어지므로, 단순한 비교로는 시간 초과가 발생합니다. 💡 예제 입력71 2 1 3 1 2 141 32 53 35 7 예제 출력1 0 1 1 🛠 알고리즘 접근 방식 이 문제는 DP(Dynamic Programming) 을 활용해모든 가능한 구간에 대해 펠린드롬 여부를 미리 계산한 뒤,질의에 대해 빠르게 응답하는 구조로 풀 수 있습니다. ✅ 핵심 아이디어 isAns[s][e] = true if arr[s] == arr[e] and i..

https://www.acmicpc.net/problem/2618 📌 자바(Java)로 푸는 경찰차 - 백준 2618 🚓🚓두 경찰차의 최소 이동 거리 + 이동 경로까지 구하는 DP 문제 🔎 문제 개요 백준 2618 - 경찰차 문제는N × N 크기의 도시에 경찰차 2대가 배치되어 있고,여러 사건이 순차적으로 발생할 때두 경찰차가 어떻게 사건을 분담해서총 이동거리를 최소화할 수 있는지를 구하는 문제입니다. 경찰차 1: 항상 (1,1) 위치에서 시작경찰차 2: 항상 (N,N) 위치에서 시작각 사건은 정확히 한 번만 처리해야 하며,각 사건은 경찰차 1 또는 경찰차 2가 처리해야 합니다.💡 예제 입력633 55 52 3 💡 예제 출력9121 총 이동거리: 9각 사건을 처리한 경찰차 번호 출력 🛠..

https://www.acmicpc.net/problem/14003 📌 자바(Java)로 푸는 가장 긴 증가하는 부분 수열 5 - 백준 14003 🔼LIS + 경로 추적을 O(N log N)으로 해결하는 대표 문제 🔎 문제 개요백준 14003번 - 가장 긴 증가하는 부분 수열 5 문제는수열이 주어졌을 때, 가장 긴 증가하는 부분 수열의 길이해당 부분 수열 자체 를 구하는 문제입니다.단, 수열의 길이가 최대 100만 개이므로 O(N²) 풀이 불가능합니다. 💡 예제 입력610 20 10 30 20 50 💡 예제 출력4 10 20 30 50 🛠 알고리즘 접근 방식 ✅ 핵심 전략: 이진 탐색 기반 LIS + 경로 추적 list[]: 현재까지 만든 LIS 수열 (값만 추적)dp[i]: arr..

https://www.acmicpc.net/problem/12852 📌 자바(Java)로 푸는 1로 만들기 2 - 백준 12852 🔢최소 연산 횟수 + 경로 추적까지 하는 DP 문제! 🔎 문제 개요 백준 12852번 - 1로 만들기 2 문제는정수 N이 주어졌을 때,1로 만들기 위해 사용할 수 있는 연산은 다음 세 가지입니다: X → X / 3 (3으로 나누어떨어질 때만)X → X / 2 (2로 나누어떨어질 때만)X → X - 1 최소 연산 횟수를 출력하고그 경로에 해당하는 숫자 순서도 출력해야 합니다. 💡 예제 입력10 💡 예제 출력310 9 3 1 🛠 알고리즘 접근 방식: Dynamic Programming (DP) ✏️ 핵심 전략 dp[i]: i를 1로 만들기 위한 최소 연산 횟수c..

https://school.programmers.co.kr/learn/courses/30/lessons/389479 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr   📌 자바(Java)로 푸는 서버 증설 횟수 문제 풀이 🚀 🔎 문제 개요 이 문제는 프로그래머스 - 서버 증설 횟수 문제입니다.주어진 시간별 플레이어 수(players[]) 를 기준으로한 대의 서버가 감당할 수 있는 최대 인원(m)과증설 시 적용되는 지속 시간(k)을 고려하여필요한 최소 서버 증설 횟수를 구하는 문제입니다. 💡 예제 입력int[] players = {10, 20, 30, 40, 50, 60, 70, 80, 90, 10..

https://school.programmers.co.kr/learn/courses/30/lessons/1832 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr   📌 자바(Java)로 푸는 보행자 천국 문제 풀이 🚦🔎 문제 개요이 문제는 프로그래머스 - 보행자 천국 문제입니다.주어진 도시 지도(cityMap[][]) 에서 출발점(0,0)에서 도착점(m-1, n-1)까지 가는 경로의 개수를 구하는 문제입니다.특정한 규칙(통행 불가 지역, 직진만 가능한 도로 등)이 존재하며,경로의 개수를 MOD(20170805)로 나눈 나머지를 출력해야 합니다.💡 예제 입력int m = 3;int n = 6;int..

https://www.acmicpc.net/problem/2293   이 문제는 dp를 활용하여 N가짓 수의 동전이 주어졌을때K의 값을 몇가지 방법으로 나타낼 수 있는지 즉 몇가지 조합으로K값을 나타낼 수 있는지에 대한 경우의수를 묻는 문제다. k가 3이면 2,1 과 1,2 가 있는데 이는 순서만 다르기에 같은경우의 수로 취급한다. 이문제를 보자 2차원 DP 배열을 생각해 낼 수 있었다.dp [i][j] 는 i까지 동전을 사용했을 때 나타낼 수 있는 경우의 수로 정의하고dp[0][j]에서 0은 coins[0]이므로 0까지의 동전이아니라 coins[0] 동전만 사용했을때경우의 수가 된다. 이를 통해 점화식을 세워 봤을 때,  dp[i][j] = dp[i-1][j];if (j >= coins[i]) { ..

https://school.programmers.co.kr/learn/courses/30/lessons/42897 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr   이전에 한번 풀어본 유형의 DP 유형이었기에 쉽게풀이할 수 있었다.  첫집과 끝집은 연결되어 있기 때문에dp 배열을 2가지 종류로 나누어야했는데, dp1은 첫집을 포함하는 경우로서 마지막 집의 포함경우를 제외하였고dp2는 첫집을 포함하는 경우를 제외하는경우로서 마지막집의 돈을 포함한 결과이다. 결국 dp[0]은 0으로 설정해 주고 Math.max 함수를 통해dp[i] = Math.max(dp[i-1],dp[i-2]+dp[i]) 라는 점화식을..

https://www.acmicpc.net/problem/1520   DFS와 메모이제이션을 활용하여 격자에서 시작점에서 도착점까지 내리막길만 따라가는 경로의 개수를 계산하는 문제다. 입력으로 주어진 N×M 크기의 격자는 각 칸에 고도 값이 저장되어 있으며, 이동은 인접한 칸으로만 가능하고 반드시 현재 위치보다 고도가 낮은 곳으로만 갈 수 있다.프로그램은 먼저 dpdpdp라는 메모이제이션 배열을 -1로 초기화한다.이는 특정 위치에서 출발해 도착점까지 갈 수 있는 경로의 개수를 저장하는 역할을 한다.그리고 value라는 2차원 배열에 고도 정보를 저장한다.dir 배열은 상하좌우 네 방향으로 이동하기 위한 도구로 사용된다.DFS는 시작점에서 출발해 가능한 모든 경로를 탐색한다.경로를 탐색하는 도중, 만약 이..

https://www.acmicpc.net/problem/11066   이 문제는 파일을 합치는 문제로써 주어진 파일들을 순서대로 합치면서최소 비용을 계산하는 것이다. 처음에는 이 문제를 보고 그리디 알고리즘으로 풀어야겠다는 생각이 들었다.그래서 최소힙(Min-Heap)을 사용해 가장 작은 두 파일을 계속 합치는 방식으로 접근했다.그러나 결과적으로 이 방식은 문제를 제대로 해결하지 못했다.파일의 순서를 고려하지 않았기 때문이다.Heap을 활용한 방식은 각 단계에서 비용을 최소화하려고 하지만,이는 부분적으로만 최적화될 뿐,전체 비용이 최소가 되는 것을 보장하지 않는다.또한, 문제의 조건에서 "파일은 주어진 순서대로 합쳐야 한다"는 점을 간과했다.이 제약을 무시하면 잘못된 결과를 도출할 수밖에 없다.직접 예..