ImJay

[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부터..