문제 링크 1. 문제 풀이 라이언 인형과 어피치 인형으로 주어진 수열에서 라이언 인형이 $K$ 인 구간 중 최소 길이를 출력하고 해당 구간이 없으면 $-1$ 을 출력하는 문제다. 해당 문제는 투 포인터를 활용해 구간 내 라이언 인형의 수를 구하는 방식과 슬라이딩 윈도우를 활용해 구간 내 라이언 인형의 수를 구하는 방식 두 가지 방식으로 풀이...

문제 링크 1. 문제 풀이 주어진 $a$, $b$ 에 대해 $a$ 초과 $b$ 이하인 구간에서 약수의 개수가 홀수인 수의 개수를 구하고 이를 구간의 크기로 나눈 후 기약 분수로 출력해야 하는 문제다. 약수의 개수는 짝을 이뤄서 나오게 되는데 완전제곱수의 경우는 자기 자신과 짝이 되는 약수가 존재해서 약수의 개수가 홀수가 됨을 활용해야 하며 ...

문제 링크 1. 문제 풀이 $N$ 개의 수 중에 어떤 수가 다른 두 수의 합으로 나타낼 수 있으면 좋은 수가 되며 좋은 수의 개수를 찾아야 하는 문제다. 이분 탐색이나 투 포인터를 활용하면 해결할 수 있다. 이분 탐색의 경우 2중 for문과 탐색 구간 분할을 활용하여 해결했다. $i$, $j$, $k$ 가 주어진 수일 때 $i = j + ...

문제 링크 1. 문제 풀이 얼음 양동이들의 좌표와 얼음의 양이 주어져 있고 백곰이 좌우로 $K$ 만큼 떨어진 양동이에 닿을 수 있을 때 최적의 자리에서 얼음의 합의 최댓값을 구해야 하는 문제다. 누적 합, 슬라이딩 윈도우, 투 포인터 3가지 방식으로 모두 풀이가 가능하다. 백곰은 양동이가 있는 좌표에도 있을 수 있으며 좌우로 $K$ 만큼 떨...

문제 링크 1. 문제 풀이 주어진 좌표들을 모두 포함하는 가장 작은 직사각형의 넓이를 구하는 문제다. 주어진 좌표들을 모두 포함하려면 좌표들의 $x$, $y$ 좌표의 최솟값과 최댓값에 해당하는 위치에 직사각형의 각 변을 두면 된다. 이를 위해 각 변의 위치 좌표에 대한 변수를 선언하고 각각 최솟값, 최댓값으로 갱신해줬다. 2. 코드 ...

문제 링크 1. 문제 풀이 주어진 수열에서 두 수의 합이 $x$ 인 쌍의 개수를 구하는 문제다. 주어진 수열을 정렬한 후 양 끝에 포인터를 두는 투 포인터를 활용하면 해결할 수 있다. 포인터가 가리키는 두 수의 합이 $x$ 보다 작으면 왼쪽 포인터를 이동시켜 두 수의 합이 커지게 하면 되고, 두 수의 합이 $x$ 보다 크면 오른쪽 포인터를 ...

문제 링크 1. 문제 풀이 주어진 $N$ 개의 나무를 적절한 높이에서 잘라서 잘라낸 나무의 길이의 합이 $M$ 이상이 되게 만들어야 하는 문제다. 자를 높이를 길이 $0$ 부터 쭉 브루트 포스로 접근하면 탐색 범위가 너무 넓어서 시간 초과가 발생하기 때문에 효율적인 접근이 필요한데 매개 변수 이분 탐색을 활용하면 해결할 수 있다. $M$ ...

문제 링크 1. 문제 풀이 BaekJoon 2292번 - 벌집 문제에서 시간 제한이 더 타이트하고 $N$ 의 범위가 커진 문제로 이전처럼 1씩 증가시켜보며 해결할 수 없다. 여기선 보다 효율적인 탐색인 이분 탐색과 매개 변수 탐색을 활용하면 해결할 수 있다. 매개 변수 탐색은 주어진 $N$ 의 범위에서 가능한 정답의 하한과 상한을 정하고 ...

문제 링크 1. 문제 풀이 주어진 날짜들에 대해 연속적인 $K$ 일의 온도의 합 중 가장 큰 값을 구해야 하는 문제다. $N$ 이 최대 $100,000$ 이어서 $O(N^2)$ 풀이로는 해결할 수 없다. 구간의 합을 빠르게 계산할 수 있는 누적 합을 활용하거나 슬라이딩 윈도우를 활용하면 효율적으로 해결할 수 있다. 2. 코드 1....

문제 링크 1. 문제 풀이 블롭이 $N$ 개의 애플파이 중 연속된 $K$ 개를 먹을 때 맛의 합의 최댓값을 구해야 하는 문제다. 이때 애플파이는 원형으로 배치되어 있어 처음과 끝이 이어져 있다. 연속으로 먹으며 $K$ 개를 먹는다는 조건에서 슬라이딩 윈도우를 활용하면 해결할 수 있다. 이때 원형으로 탐색해야 해서 모듈러 연산을 활용해주면 ...