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

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

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

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

문제 링크 1. 문제 풀이 각 방마다 규칙적인 숫자가 부여되어 있는데 특정 방까지 최소 개수의 방을 지나서 갈 때, 몇 개의 방을 지나가면 도착할 수 있는지 구하는 문제다. $1$ 개의 방을 지나면 갈 수 있는 방은 1번 방 하나뿐이며, $2$ 개의 방을 지나면 갈 수 있는 방은 2 ~ 7번 방, $3$ 개의 방을 지나면 갈 수 있는 방은 8 ...

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

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

문제 링크 1. 문제 풀이 자연수들로 이루어진 집합 $U$ 에서 고른 세 수의 합이 $U$ 에 포함되는 가장 큰 수를 찾는 문제다. $N$ 이 최대 $1,000$ 이어서 3중 반복문을 통한 풀이는 시간 초과가 발생하게 되는데 이를 2중 반복문 두 개로 쪼개서 해결하는 중간에서 만나기를 적용해야 한다. 핵심은 $a + b + c = d$ 를 만족...

문제 링크 1. 문제 풀이 주어진 수열에서 임의의 두 수의 차가 $M$ 이상이면서 제일 작은 경우를 구해야 하는 문제로 두 수가 같아도 된다. $N$ 이 최대 $100,000$ 이라서 $O(N^2)$ 으로는 풀 수 없는데 투 포인터를 활용하면 해결할 수 있다. 먼저 주어진 수열을 오름차순으로 정렬한다. 이후 두 포인터를 앞에서부터 출발시켜 오...

문제 링크 1. 문제 풀이 주어진 $1$ 일 ~ $N$ 일 중 연속된 $X$ 일에 대해 방문자 수가 최대인 순간의 값을 구하고 그런 구간의 개수를 출력하되, 최대 방문자 수가 $0$ 이면 SAD 를 출력해야 하는 문제다. $N$ 이 최대 $250,000$ 이어서 $O(N^2)$ 으로는 해결할 수 없어 효율적인 탐색이 필요하다. 구간의 합을 빠르...