ImJay

[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)를 관리한다.시간 계산: 각 건물을 짓는 데 걸리는 시간을 누적한다. 이때, 의존 관계에 있는 건물들이 모두 완성된 후에야 현재..