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

[BOJ/Java] 2531. 회전 초밥https://www.acmicpc.net/problem/2531문제 해석회전 초밥 문제는 주어진 회전 초밥 벨트에서 연속된 K개의 초밥을 선택했을 때, 이때의 다양한 초밥의 종류를 최대화하는 문제이다. 또한, 초밥의 선택은 하나의 쿠폰을 이용하여 원하는 초밥 한 종류를 추가할 수 있어, 이를 고려한 최적의 초밥 선택 전략을 요구한다.풀이 과정 초기 설정: 입력을 받아 전역 변수로 N(총 초밥의 개수), D(초밥의 종류 수), K(연속해서 먹을 초밥의 개수), C(쿠폰으로 먹을 수 있는 초밥 번호)를 설정하고, 초밥의 번호를 저장할 배열 arr을 선언한다.슬라이딩 윈도우 및 초밥 종류 카운팅: 첫 K개의 초밥을 선택하여 종류를 카운팅한다. 이를 기반으로 슬라이딩 윈..

[BOJ/Java] 2565. 전깃줄https://www.acmicpc.net/problem/2565문제 해석문제는 주어진 전깃줄이 교차하지 않도록 최소 몇 개의 전깃줄을 제거해야 하는지를 묻고 있다. 이 문제는 동적 계획법을 이용한 최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 문제의 변형으로 볼 수 있다. A와 B 두 전봇대에 연결된 전깃줄의 위치가 주어지며, 각 전깃줄은 A전봇대의 특정 위치에서 B전봇대의 특정 위치로 연결된다.풀이 과정주어진 입력으로부터 전깃줄 정보를 배열에 저장하고, A 전봇대에 대해 오름차순 정렬을 실시한다. 이후, B 전봇대의 위치를 기준으로 LIS를 계산하여, 교차하지 않는 최대 전깃줄 수를 찾는다. LIS의 길이가 교차하지 않는 최..

[BOJ/Java] 12015. 가장 긴 증가하는 부분 수열 2 12015번: 가장 긴 증가하는 부분 수열 2첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)www.acmicpc.net문제 해석주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 찾는 고전적인 문제의 확장판이다. 이 문제는 수열의 길이가 매우 클 수 있기 때문에 𝑂(𝑁^2)의 시간 복잡도를 갖는 기본적인 동적 프로그래밍 방법으로는 효율적으로 해결할 수 없다. 대신, 이진 탐색을 활용한 𝑂(𝑁log⁡𝑁) 시간 복잡도의 풀이가 필요하다.풀이 과정입력 받기: 수열의 크기 N과 수열 A를 입력 받는다.DP 배열 초기화..

[BOJ/Java] 11055. 가장 큰 증가 부분 수열 11055번: 가장 큰 증가하는 부분 수열수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는www.acmicpc.net문제 해석주어진 수열에서 증가 부분 수열을 찾아 그 합이 최대가 되는 값을 구하는 문제이다. 이는 '가장 긴 증가하는 부분 수열' 문제의 변형으로, 길이가 아닌 수열의 합을 최대화하는 것이 목표이다.풀이 과정입력 받기: 수열의 크기 N과 수열 A를 입력 받는다.동적 프로그래밍(DP) 배열 초기화: DP 배열을 사용하여 각 위치에서 가능한 최대 합을 저장..