ImJay

📌 [BOJ/Java] 10942. 팰린드롬?🔗 문제 링크: 백준 10942번 - 팰린드롬?📖 문제 해석🔢 주어진 수열에서 특정 구간이 팰린드롬인지 판별하는 문제이다.🛠️ 팰린드롬(Palindrome): 앞에서 읽어도 뒤에서 읽어도 같은 문자열 or 수열❓ 여러 개의 질문(구간)이 주어지며, 각 구간이 팰린드롬인지 빠르게 판단해야 한다.✅ 핵심 개념단순하게 매번 확인하면 O(N) 연산이 필요하므로 비효율적DP(동적 계획법) 활용하여 중복 계산 최소화구간 판별 문제이므로 "구간 DP"로 접근🛠️ 풀이 과정1️⃣ 입력 처리 및 초기화N개의 숫자를 입력받아 배열에 저장dp[i][j]를 사용하여 i부터 j까지의 구간이 팰린드롬인지 저장2️⃣ DP 테이블 채우기dp[i][i] = true (길이 1짜리..

📌 [BOJ/Java] 7579. 앱🔗 문제 링크: 백준 7579번 - 앱📖 문제 해석📱 여러 개의 앱이 실행 중이며, 이를 종료하거나 일부 비활성화하여 M 바이트 이상의 메모리를 확보하는 최소 비용을 구하는 문제이다.💰 앱을 비활성화할 때 **비활성화 비용(추가 배터리 소비 등)**이 존재하며,🛠️ 최소한의 비용으로 M 바이트 이상 확보해야 한다.✅ 핵심 개념**부분 배낭 문제(0/1 Knapsack)**과 유사최적의 앱 비활성화 조합을 찾는 DP 활용비용(cost)을 기준으로 최소 비용으로 M 바이트 확보하도록 최적화🛠️ 풀이 과정1️⃣ 입력 처리 및 초기화N개의 앱의 **메모리 사용량(memory[])**과 **비활성화 비용(cost[])**을 입력받는다.dp[c]를 사용하여 비활성화 ..

📌 [BOJ/Java] 4991. 로봇 청소기🔗 문제 링크: 백준 4991번 - 로봇 청소기📖 문제 해석🧹 W × H 크기의 방에서 로봇 청소기가 모든 먼지(*)를 청소해야 한다.🚧 장애물(x)을 피하면서 최소 이동 거리를 찾아야 한다.🎯 모든 먼지를 최단 거리로 방문하는 최소 이동 횟수를 구하는 문제✅ 핵심 개념BFS로 각 지점 간 최단 거리 계산비트마스킹 DP로 최적의 방문 순서 찾기 (TSP 응용)🛠️ 풀이 과정1️⃣ 입력 처리 및 초기화W × H 크기의 맵 입력받기로봇(o)과 먼지(*) 좌표 저장모든 먼지 간 최단 거리 계산(BFS)2️⃣ 모든 지점 간 최단 거리 계산 (BFS)dist[i][j]: i번 먼지에서 j번 먼지까지의 최단 거리도달할 수 없는 경우 -1 반환3️⃣ 비트마스킹..

📌 [BOJ/Java] 11049. 행렬 곱셈 순서🔗 문제 링크: 백준 11049번 - 행렬 곱셈 순서📖 문제 해석📌 N개의 행렬이 주어질 때, 모든 행렬을 곱하는 최소 연산 횟수를 구하는 문제이다.💰 행렬 곱셈 연산 횟수는 A(p×q) × B(q×r) = p × q × r로 계산된다.🛠️ 행렬을 곱하는 순서에 따라 연산 횟수가 달라지므로 최적의 곱셈 순서를 찾아야 한다.🎯 핵심 개념dp[i][j] = i번째 행렬부터 j번째 행렬까지 곱하는 최소 연산 횟수dp[i][j] = min(dp[i][k] + dp[k+1][j] + cost(A[i] ~ A[k], A[k+1] ~ A[j]))(i부터 j까지 곱하는 최적의 k를 찾는다.)🛠️ 풀이 과정1️⃣ 입력 처리 및 초기화행렬 개수 N을 입력받고..

📌 [BOJ/Java] 11066. 파일 합치기🔗 문제 링크: 백준 11066번 - 파일 합치기📖 문제 해석📂 여러 개의 파일이 연속으로 놓여 있고, 이를 하나의 파일로 합치는 최소 비용을 구하는 문제이다.💰 파일을 합치는 비용은 두 파일 크기의 합이며, 여러 번 합칠 경우 누적 비용이 증가한다.🛠️ 파일을 합치는 순서를 잘 정해야 최소 비용이 된다.🎯 핵심 개념:파일을 어떤 순서로 합치는지가 중요하며, 최적의 순서를 찾기 위해 동적 계획법(DP)을 활용한다.🛠️ 풀이 과정1️⃣ 입력 처리 및 초기화K개의 파일 크기를 입력받고, **누적 합 배열(sum[])**을 만든다.dp[i][j]는 i번째 파일부터 j번째 파일까지 합치는 최소 비용을 의미한다.2️⃣ DP 테이블 채우기부분 파일들을 합..

📌 [BOJ/Java] 6087. 레이저 통신🔗 문제 링크: 백준 6087번 - 레이저 통신📖 문제 해석2차원 맵에서 두 개의 레이저 🔦가 주어진다.레이저는 **.(빈 공간)**에서 이동할 수 있으며, ***(벽)**을 통과할 수 없다.이동할 때는 상하좌우 방향으로만 가능하며,거울 (/ 또는 \)을 설치하여 빛의 방향을 변경할 수 있다.✅ 목표는 시작 레이저에서 도착 레이저까지 최소한의 거울을 설치하는 것이다.🛠️ 풀이 과정이 문제는 BFS + 다익스트라 알고리즘을 응용하여 해결할 수 있다.즉, **우선순위 큐(최소 힙)**를 사용하여 거울 설치 횟수가 적은 경로부터 탐색하는 방식이다.1️⃣ 입력 처리 및 초기화W x H 크기의 맵 정보를 입력받고, 레이저의 시작점(C1)과 도착점(C2)을 찾는..

[BOJ/Java] 6549. 히스토그램에서 가장 큰 직사각형https://www.acmicpc.net/problem/6549🔍 문제 분석백준 6549번 "히스토그램에서 가장 큰 직사각형" 문제는 주어진 히스토그램에서 가장 넓은 직사각형을 찾는 문제이다.주어진 히스토그램은 N개의 막대기로 이루어져 있으며, 각 막대기는 서로 너비가 1이고 높이가 주어진다.🚀 풀이 과정이 문제는 스택을 이용한 최적화된 방법을 사용해야 한다.💡 핵심 아이디어각 막대의 높이를 기준으로 최대 직사각형을 계산해야 한다.스택을 활용하면 O(N) 시간에 해결할 수 있다.1. 스택을 활용한 접근 방법막대를 왼쪽부터 확인하면서 스택에 저장한다.스택에는 막대의 인덱스를 저장한다.현재 막대의 높이가 스택의 top보다 작다면, 스택에서 ..

[BOJ/Java] 9376. 탈옥https://www.acmicpc.net/problem/9376🔍 문제 분석백준 9376번 "탈옥" 문제는 2명의 죄수를 탈출시키기 위한 최단 경로를 찾는 문제이다.벽('*')을 부수면서 이동할 수 있으며, 문의 개수가 최소인 경로를 찾아야 한다.🚀 풀이 과정이 문제는 BFS(너비 우선 탐색) + 다익스트라 유형의 접근을 해야 한다.맵의 바깥쪽에서 시작할 수 있도록 패딩을 추가한다.죄수가 문을 열고 탈출할 수도 있지만, 밖에서 열어주는 경우도 가능하기 때문.BFS를 3번 수행한다.1회차: 바깥에서 BFS 수행 (외부에서 문을 여는 경우 고려)2회차: 첫 번째 죄수의 위치에서 BFS 수행3회차: 두 번째 죄수의 위치에서 BFS 수행각 BFS에서 문의 개수를 누적하여 ..

[BOJ/Java] 2749. 피보나치 수 3https://www.acmicpc.net/problem/2749문제 해석피보나치 수 3 문제는 \(n\)번째 피보나치 수를 \(1,000,000\)으로 나눈 나머지를 구하는 문제이다. 단, \(n\)은 \(1,000,000,000,000,000,000\)까지 가능하므로, 일반적인 재귀나 반복문으로는 해결할 수 없다. 이 문제는 **피사노 주기(Pisano Period)**를 활용하여 해결할 수 있다.풀이 과정 피사노 주기 이해: 피보나치 수를 \(m\)으로 나눈 나머지는 주기를 가진다. 이 주기를 피사노 주기라고 하며, \(m = 1,000,000\)일 때 피사노 주기는 \(1,500,000\)이다. 피사노 주기 활용: \(n\)을 피사노 주기로 ..

[BOJ/Java] 2933. 미네랄https://www.acmicpc.net/problem/2933🔍 문제 분석백준 2933번 "미네랄" 문제는 2차원 격자 형태의 동굴에서 막대를 던져 미네랄을 부수고, 이후 클러스터(공중에 떠 있는 미네랄 조각들)의 중력을 적용하는 시뮬레이션 문제이다.문제를 단계별로 분석하면 다음과 같다:입력동굴의 크기 R×C (최대 100×100)동굴 내 미네랄('x')과 빈 공간('.') 정보막대를 던지는 횟수 N각 막대를 던지는 높이 정보막대가 부딪히는 미네랄 제거왼쪽에서 던지는 경우는 왼쪽부터 탐색하며 'x'를 제거오른쪽에서 던지는 경우는 오른쪽부터 탐색하며 'x'를 제거클러스터 검출 및 중력 적용미네랄이 부서진 후, 공중에 떠 있는 클러스터를 찾아 중력을 적용한다.BFS/..