ImJay

[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/..

[BOJ/Java] 10830. 행렬 제곱https://www.acmicpc.net/problem/10830문제 해석행렬 제곱 문제는 주어진 정사각 행렬 \(A\)를 \(B\)번 거듭제곱한 결과를 구하는 문제이다. 단, 각 원소는 \(1,000\)으로 나눈 나머지를 출력해야 한다. 이 문제는 행렬의 거듭제곱을 효율적으로 계산하기 위해 **분할 정복(Divide and Conquer)**과 **행렬 곱셈**을 활용해야 한다.풀이 과정 행렬 곱셈 구현: 두 행렬을 곱하는 함수를 구현한다. 이때, 곱셈 결과의 각 원소는 \(1,000\)으로 나눈 나머지를 저장한다. 분할 정복을 이용한 거듭제곱: 행렬 \(A\)를 \(B\)번 거듭제곱할 때, \(B\)가 짝수인 경우와 홀수인 경우로 나누어 재귀적으로..

[BOJ/Java] 11401. 이항 계수 3https://www.acmicpc.net/problem/11401문제 해석이항 계수 3 문제는 주어진 자연수 \(N\)과 \(K\)에 대해 이항 계수 \(\binom{N}{K}\)를 \(1,000,000,007\)로 나눈 나머지를 구하는 문제이다. 이항 계수는 다음과 같이 정의된다:\[\binom{N}{K} = \frac{N!}{K!(N-K)!}\]이 문제는 \(N\)과 \(K\)가 매우 크기 때문에(\(1 \leq N \leq 4,000,000\), \(0 \leq K \leq N\)), 직접 계산하는 대신 **페르마의 소정리**와 **모듈로 연산**을 활용하여 효율적으로 해결해야 한다.풀이 과정 페르마의 소정리 적용: 페르마의 소정리에 따르면, 소수..

[BOJ/Java] 1655. 가운데를 말해요https://www.acmicpc.net/problem/1655문제 해석가운데를 말해요 문제는 수열이 주어졌을 때, 각 수를 하나씩 읽어가며 현재까지의 수열에서 중간값을 출력하는 문제이다. 중간값은 수열을 정렬했을 때 가운데에 위치한 값으로, 수열의 길이가 짝수인 경우 더 작은 값을 선택한다. 이 문제는 동적으로 수열이 추가될 때마다 중간값을 효율적으로 찾아야 하므로, 우선순위 큐를 활용하여 해결할 수 있다.풀이 과정초기 설정: 두 개의 우선순위 큐를 사용한다. 하나는 최대 힙(max heap), 다른 하나는 최소 힙(min heap)으로 구성한다. 최대 힙은 중간값보다 작은 수를 저장하고, 최소 힙은 중간값보다 큰 수를 저장한다.수열 처리: 수열의 각 수를..

[BOJ/Java] 12865. 평범한 배낭https://www.acmicpc.net/problem/12865문제 해석평범한 배낭 문제는 주어진 물건들의 무게와 가치를 고려하여 배낭의 최대 용량 내에서 가치의 합이 최대가 되도록 물건을 선택하는 문제이다. 이 문제는 전형적인 **배낭 문제(Knapsack Problem)**로, 동적 프로그래밍을 활용하여 해결할 수 있다.풀이 과정초기 설정: 물건의 개수(N)와 배낭의 최대 용량(K)을 입력받는다. 각 물건의 무게와 가치를 저장할 배열을 선언한다.동적 프로그래밍 테이블 구성: `dp[i][j]`는 배낭의 용량이 `j`일 때, 처음 `i`개의 물건 중에서 선택한 최대 가치를 의미한다. 이 테이블을 초기화한다.점화식 적용: 각 물건에 대해 배낭의 용량을 1부터..

[BOJ/Java] 3197. 백조의 호수https://www.acmicpc.net/problem/3197문제 해석백조의 호수 문제는 두 마리의 백조가 있는 호수에서 얼음이 녹아 백조들이 만날 수 있는 최소 시간을 구하는 문제이다. 호수는 2차원 격자로 표현되며, 각 칸은 물('.') 또는 얼음('X')으로 구성된다. 백조는 물 위에서만 이동할 수 있으며, 매일 얼음이 물과 인접한 부분부터 녹는다. 두 백조가 만날 수 있는 최소 일수를 계산해야 한다.풀이 과정초기 설정: 호수의 상태를 입력받고, 두 백조의 위치를 찾는다. 또한, 얼음이 녹는 과정을 시뮬레이션하기 위해 BFS를 사용한다.얼음 녹이기: 물과 인접한 얼음을 녹이는 과정을 BFS로 구현한다. 이때, 얼음이 녹는 순서를 큐에 저장하여 매일 얼음이..

[BOJ/Java] 1005. ACM Crafthttps://www.acmicpc.net/problem/1005문제 해석ACM Craft는 건물을 짓는 순서와 각 건물을 짓는 데 걸리는 시간이 주어졌을 때, 특정 건물을 완성하는 데 걸리는 최소 시간을 구하는 문제이다. 각 건물은 다른 건물이 먼저 지어져야만 지을 수 있으며, 이러한 의존 관계가 주어진다.풀이 과정그래프 구성: 건물과 의존 관계를 그래프로 표현한다. 각 건물은 노드이며, 의존 관계는 방향성 간선이다.위상 정렬: 건물을 짓는 순서를 결정하기 위해 위상 정렬을 수행한다. 이때, 각 노드의 진입 차수(In-degree)를 관리한다.시간 계산: 각 건물을 짓는 데 걸리는 시간을 누적한다. 이때, 의존 관계에 있는 건물들이 모두 완성된 후에야 현재..

[CodeTree/Java] 나무박멸 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai문제 해석이 문제에서는 n*n 격자 위에서 나무가 번식하고 제초제를 통해 그 성장을 억제하는 시뮬레이션을 진행한다. 주어진 입력은 격자의 크기 n, 시뮬레이션을 진행할 년 수 m, 제초제의 확산 범위 k, 제초제의 지속 시간 c로 구성된다. 각 격자 칸은 나무의 수, 빈 칸, 또는 벽으로 표시된다. 나무는 인접한 칸으로 성장하고 번식할 수 있으며, 제초제는 대각선 방향으로 k칸 만큼 확산되어 나무를 박멸한다. 제초제는 벽을 만나면 확산이 중단된다.풀이 과정성장: 모든 나무..