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

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

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

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

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

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

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

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

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

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