문제 링크 1. 문제 풀이 최대 $K$ 만큼의 무게를 담을 수 있는 배낭에 주어진 물건들을 담을 때 물건의 가치의 합이 최대가 되게 하는 문제다. 물건의 수가 최대 $100$ 개로 각 물건을 담거나 안담는 브루트 포스로는 경우의 수가 $2^{100}$ 으로 시간 초과가 발생한다. 문제 설명부터 힌트가 있는데 각 물건을 담거나 안담는 두 가지...

문제 링크 1. 문제 풀이 주어진 동전들을 적절히 사용해서 가치의 합이 $K$ 가 될 때 필요한 동전 개수의 최솟값을 구하는 문제다. 각 동전을 여러 번 사용할 수 있으며 동전의 가치가 오름차순으로 주어지고 서로 배수 관계에 있으므로 최대한 가치가 큰 동전부터 많이 사용하면 된다. 사용한 동전의 개수는 가치로 나눈 몫이 되며 나머지에 대해 ...

1. 이진 거듭제곱 이진 거듭제곱(Binary Exponentiation, Exponentiation by Squaring)은 $a^n$ 연산의 결과를 $O(\log{n})$ 의 시간복잡도로 해결하는 알고리즘이다. $a^n$ 은 $a$ 를 $n$ 번 곱한 수이므로 반복문을 활용해 $a \times a \times \cdots \times a$ ...

문제 링크 1. 문제 풀이 $A$ 의 각 원소에 대해 $B$ 에서 해당 원소보다 작은 원소의 수를 구해서 전부 합한 결과를 출력하는 문제다. 이분 탐색 또는 투 포인터를 활용하면 간단하게 해결할 수 있다. 1. 이분 탐색 이분 탐색을 활용할 경우 $A$ 의 각 원소에 대해 $B$ 에서 해당 원소 미만인 원소를 찾아야 한다. 이를 위해...

문제 링크 1. 문제 풀이 BaekJoon 2467번 - 용액 문제에서 세 용액의 합으로 바뀐 문제로 이분 탐색으로 해결할 경우 두 개의 용액을 2중 반복문으로 선택한 후 남은 하나를 이분 탐색으로 찾으면 되며, 투 포인터로 해결할 경우 한 용액을 선택한 후 투 포인터로 남은 두 용액을 탐색하면 된다. 2. 코드 1. 이분 탐색 [J...

문제 링크 1. 문제 풀이 BaekJoon 2467번 - 용액 문제에서 용액들이 오름차순으로 주어지지 않은 문제로 입력을 받은 후 정렬만 한번 해주면 된다. 2. 코드 1. 이분 탐색 [Java] import java.io.*; import java.util.*; public class Main { public stat...

문제 링크 1. 문제 풀이 주어진 정수 값의 용액들에 대해 두 용액의 합이 $0$ 에 최대한 가까운 조합을 찾아서 출력해야 하는 문제다. $N$ 이 최대 $100,000$ 이라서 2중 반복문을 활용한 브루트 포스로는 해결할 수 없는데, 이분 탐색 또는 투 포인터 알고리즘을 활용하면 해결할 수 있다. 1. 이분 탐색 이분 탐색을 활용할...

문제 링크 1. 문제 풀이 주어진 수열에서 같은 정수를 $K$ 개 이하로 포함하는 가장 긴 구간의 길이를 구하는 문제로 투 포인터를 활용하면 해결할 수 있다. 카운팅 배열을 통해 구간 내 각 수의 개수를 세며 오른쪽 포인터를 이동할 때 $K$ 개 미만으로 포함하고 있으면 이동하며 최대 길이를 갱신하고, $K$ 개 이상 포함하고 있으면 왼쪽 ...

문제 링크 1. 문제 풀이 주어진 $N$ 개의 정수에 대해 이 안에 $X$ 가 존재하는지 여부를 찾는 문제다. 주어진 수의 범위가 너무 커서 방문 체크 배열을 활용해서는 풀 수 없다. 주어진 수를 정렬한 후 이분 탐색을 통해 찾던가 집합을 활용해서 포함 여부를 판단하는 방식으로 해결할 수 있다. 2. 코드 1. 이분 탐색 [Jav...

문제 링크 1. 문제 풀이 $10,000$ 이하의 자연수로 이루어진 길이 $N$ 짜리 수열에 대해 연속된 수들의 부분합 중 합이 $S$ 이상인 가장 짧은 구간의 길이를 구하는 문제다. 단순한 브루트 포스로는 시간 내에 해결할 수 없는데 투 포인터를 활용하면 해결할 수 있다. 투 포인터는 두 포인터를 수열의 맨 앞부터 출발시키고 두 포인터의...