문제 링크 1. 문제 풀이 $M$ 개의 챕터가 있고 각 챕터는 읽는데 소요되는 일 수와 페이지 수가 주어졌을 때, $N$ 일 동안 읽을 수 있는 최대 페이지 수를 구하는 문제다. $M$ 이 최대 $20$ 이라서 완전 탐색($2^{20} = 1,048,576$ 가지)으로도 풀 수 있고, 0／1 배낭 문제를 활용하여 각 챕터를 읽을지 안 읽을지 선...

문제 링크 1. 문제 풀이 수열의 크기 $N$ 이 최대 $100,000$, 특정 원소의 값을 변경하거나 구간 내 최솟값의 인덱스를 구하는 쿼리의 수 $M$ 이 최대 $100,000$ 인 문제로 구간 쿼리와 점 갱신을 효율적으로 처리할 수 있는 세그먼트 트리를 활용하면 해결할 수 있다. 다만 구간 내 최솟값이 아니라 최솟값의 인덱스를 구해야 하는...

문제 링크 1. 문제 풀이 집합 $S$ 에 대해 집합 $S$ 에 포함됐는지 여부를 구하는 문제로 집합에 포함됐는지 확인할 수 있는 함수나 메서드를 활용하면 간단하게 해결할 수 있다. 2. 코드 1. 해시를 사용한 집합과 맵 [Java] conatins 메서드로 집합에 포함됐는지 여부를 간단하게 확인할 수 있다. import java....

문제 링크 1. 문제 풀이 데이터베이스 $S$ 에 특정 자연수 $X$ 를 추가하거나 $X$ 번째로 작은 수를 응답하고 그 수를 삭제하는 쿼리를 처리하는 문제로 숫자별 등장 횟수를 저장한 세그먼트 트리를 활용하면 해결할 수 있다. 이때 같은 수가 여러 번 추가될 수 있음에 주의해야 한다. $k$ 번째 수를 구하는 전형적인 세그먼트 트리 유형의 ...

문제 링크 1. 문제 풀이 $N$ 이 최대 $100,000$ 인 상황에서 요세푸스 순열을 구하는 문제로 큐를 활용한 풀이는 시간 초과가 발생한다. $1$ 부터 $N$ 까지 각 수의 등장 횟수를 $1$ 로 초기화한 세그먼트 트리를 활용하면 해결할 수 있는데 $k$ 번째 수를 반환하는 함수와 $k$ 번째 수를 제거하는 함수를 통해 $O(\log{N...

문제 링크 1. 문제 풀이 문자열 $S$ 의 서로 다른 부분 문자열의 개수를 구하는 문제로 중복을 제거할 수 있는 집합 자료구조와 부분 문자열을 생성할 수 있는 함수나 메서드를 활용하면 간단하게 해결할 수 있다. 2. 코드 1. 해시를 사용한 집합과 맵 [Java] substring 메서드로 시작 인덱스와 끝 인덱스를 넣어서 부분 문자...

문제 링크 1. 문제 풀이 각각의 반죽들에 대해 오븐 1에서 굽는 경우랑 오븐 2에서 굽는 경우랑 걸리는 시간이 다른데 전체 반죽을 굽는데 걸리는 최소 시간을 구해야 하는 문제다. 배낭 문제를 활용하면 이 문제를 해결할 수 있는데 배낭의 용량을 오븐 1에서 굽는 데 쓸 수 있는 최대 시간으로 했을 때, 배낭의 가치를 오븐 2에서 굽는 데 걸리는...

문제 링크 1. 문제 풀이 나이와 이름이 주어진 회원들에 대해 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 문제로 언어별 정렬을 활용하면 간단하게 해결할 수 있다. 2. 코드 1. 정렬 [Java] User 클래스를 만들어서 나이와 이름 정보를 저장하고 Array.sort 메서드에서 람다식을 활...

문제 링크 1. 문제 풀이 평균과 중앙값을 구하는 문제로 평균은 다섯 수의 합을 $5$ 로 나누면 되고 중앙값은 다섯 수를 정렬한 후 세 번째 값을 찾으면 된다. 2. 코드 1. 구현 [Java] import java.io.*; import java.util.*; public class Main { public static v...

문제 링크 1. 문제 풀이 커트라인을 구하는 문제로 정렬을 활용하면 간단하게 해결할 수 있다. 오름차순으로 정렬할 경우 맨 끝 값이 가장 높은 점수인 점에 주의해야 한다. 2. 코드 1. 정렬 [Java] import java.io.*; import java.util.*; public class Main { public sta...