문제 링크 1. 문제 풀이 듣도 못한 사람의 명단과 보도 못한 사람의 명단에 모두 포함된 사람의 명단을 사전 순으로 출력하는 문제로 두 집합의 교집합을 구하면 되는 간단한 문제다. 2. 코드 1. 풀이 [Java] 듣도 못한 사람은 TreeSet으로 보도 못한 사람은 HashSet으로 저장한 후 retainAll 메서드로 두 집...

문제 링크 1. 문제 풀이 각각의 작업들에 대해 머신 $A$ 에서 작업하는 경우랑 머신 $B$ 에서 작업하는 경우랑 완료 시간이 다른데 전체 작업의 완료에 걸리는 최소 시간을 구해야 하는 문제다. 배낭 문제를 활용하면 이 문제를 해결할 수 있는데 배낭의 용량을 머신 $A$ 가 작업을 수행하는데 쓸 수 있는 최대 시간으로 했을 때, 배낭의 가...

문제 링크 1. 문제 풀이 짝수 $N$ 에 대해 두 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 문제로 에라토스테네스의 체를 활용해서 $N$ 보다 작은 소수들을 미리 판정해놓으면 간단하게 해결할 수 있다. $2$ 부터 $N / 2$ 까지 탐색하면 순서가 뒤집힌 경우를 세지 않으면서 탐색량도 줄일 수 있다. 2. 코드 1. 풀...

문제 링크 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.io.*; i...

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

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

문제 링크 1. 문제 풀이 문자열 $S$ 의 서로 다른 부분 문자열의 개수를 구하는 문제로 중복을 제거할 수 있는 집합 자료구조와 부분 문자열을 생성할 수 있는 함수나 메서드를 활용하면 간단하게 해결할 수 있다. 2. 코드 1. 풀이 [Java] import java.io.*; import java.util.*; public ...

문제 링크 1. 문제 풀이 BaekJoon 17528번 - Two Machines 문제와 거의 동일한 문제로 각각의 반죽들에 대해 오븐 1에서 굽는 경우랑 오븐 2에서 굽는 경우랑 걸리는 시간이 다른데 전체 반죽을 굽는데 걸리는 최소 시간을 구해야 하는 문제다. 배낭 문제를 활용하면 이 문제를 해결할 수 있는데 배낭의 용량을 오븐 1에서 굽...