1. 문제 설명 📌문제 링크용액마다 특수값이 존재두 용액을 골라서 둘의 특수 값을 합했을 때, 그 합이 0에 가장 가까운 조합을 구하여라2. 접근 방식 🗃️KEY WORD: Two way Two pointer용액의 특수값을 1차원 배열에 입력받고, 해당 배열을 오름차순으로 정렬한다.index = 0에 L 포인터, index = N-1에 R 포인터를 둔다L+R > 0 일 경우, R 포인터를 한 칸 후진 시켜서 합을 하향조정한다.L-R 일 경우, L 포인터를 한 칸 전진 시켜서 합을 상향조정한다.0에 가까운 값을 구해야함으로, 둘 사이의 합의 절대값이 최소인 경우를 찾으면 된다.(왜냐하면, 두 포인터 사이의 합의 절대값이 커질수록 0에서 멀어지기 때문이다.)(1) 단뱡항 투 포인터로 답을 구할 수 없는 ..

1. 문제 설명 📌문제 링크2. 접근 방식 🗃️KEY WORD: one-way Two pointer단방향 투 포인터를 사용하는 전형적인 문제이다. 왼쪽 포인터(L)과 오른쪽 포인터(R)을 둔다. 해당 구간 내 수들의 합을 sum이라 하겠다.sum : R 포인터를 전진시킨다.sum >= M: L 포인터를 전진시킨다. (만약 sum == M이면 답이 되는 경우의 수를 +1 올린다.)구간 내의 합은 구간 내의 값이 원소 하나인 경우도 포함한다. 따라서 arr[0] == M 인 경우도 예외 없이 계산에 포함되도록 해줘야 한다.나는 3번의 규칙을 지키기 위해 배열을 N+1로 만들어 값들을 1부터 채우고, 포인터들은 0부터 시작하도록 하였다.3. 코드 소개 🔎import java.io.*;import java..

0. 글이 흘러가는 방향먼저 개념 설명을 하고, 투 포인터를 활용하는 대표적인 문제 2개를 직접 풀어보며, 개념에 대한 보충을 하겠다.1. 개념1차원 배열에 두 개의 포인터를 두고, 두 포인터에 의미를 부여하여 문제를 푸는 기술배열 안에서 특정 조건의 값을 구하는 문제에서, 일반적으로 시간 복잡도가 O((N^{2}))가 든다면, 투 포인터 기법을 활용하면 시간 복잡도를 O(N)으로 줄일 수 있다. (이유는 활용을 살펴보며 설명하겠다.)(1) 유형투 포인터를 운용하는 유형에는 크게 2가지가 있다.a.단방향 운용L 포인터와 R 포인터가 한쪽 방향으로만 움직이는 것이다. 슬라이딩 윈도우의 양끝을 의미한다고 보면 된다. 슬라이딩 윈도우와 다른 점은 포인터에 따라 구간의 길이가 가변적이라는 것이다.b. 양방향 운..

1. 문제 설명 📌문제 링크슬라이딩 윈도우에서 더 나아가서, 윈도우 구간안에 최소값을 매번 출력하는 문제이다.2. 접근 방식 🗃️KEY WORD: Sliding Window, Data Structure (Deque)파이썬에서는 추가시간이 주어줘서 우선순위 큐를 이용해도 풀리지만, Java에서는 풀리지 않는다. 왜 우선순위 큐로는 안되는지에 대해 4번 항목에서 설명하겠다.(1) 전체 접근 방식ArrayDeque로 슬라이딩 윈도우를 구현한다.(해당 deque는 현재 구간인 값들만 가지고 있으며, 오름차순으로 값의 순서를 유지한다. (front = 최소값))슬라이딩 윈도우를 오른쪽으로 한 칸씩 움직인다.구간에 신규로 추가될 값을 A라고 쳤을 때, A와 deque의 rear(꼬리)를 비교한다rear > A:..

1. 문제 설명 📌문제 링크2. 접근 방식 🗃️KEY WORD: 누적 합, 이분 탐색동굴의 높이인 H와 깊이인 N이 각각 \(10^{5}\)이므로, 완전 탐색으로 하나의 행마다 모든 열을 조회한다면 1초에 \(10^{10}\)번 이상의 연산을 해야해서 시간 초과가 날 것이다.해당 문제는 *거꾸로 매달려 있는 종유석을 어떻게 처리할 것인가?* 에 대한 명확한 가이드라인만 계획할 수 있다면 풀 수 있는 문제이다. 종유석 처리방법에 따라 두 가지 방법으로 풀 수 있는데, 하나는 누적 합이고 다른 하나는 이분 탐색이다.(1) 누적합a. 결론 먼저1. "석순과 종유석 입력을 분류하여 Y축 위치에 따른 각 산물의 위치를 저장하는 배열 구현"2. "각 배열의 누적합 구하기 (석순 누적합 배열을 sum_S[i], ..

1. 문제 설명 📌문제 링크2. 접근 방식 🗃️KEY WORD: 구간 합누적합 배열 S에서 A~B 구간 내의 구간합을 구할 경우 어떻게 표현했는가?S[B] - S[A-1] 이였다. A가 구간내에 합해지도록 A-1까지의 구간합을 제거했다. 이러한 원리는 구간 내에 알파벳이 몇 번 등장하는가 찾는 이번 문제에서도 사용할 수 있다.위 그림과 같이, a가 A구간에서 한번, B구간에서 한번 나온다고 하자. 그러면, S[A] = 1, S[B] = 2가 될 것이다. 구간을 확인하면 문자열이 A의 위치를 넘어서서 B까지 구간을 정하는 순간 a는 한개이다. S[B]-S[A]는 A+1 ~ B까지의 구간합임으로 2-1 = 1이 나온다. 반면 S[B] - S[A-1]은 A의 위치부터 B까지의 거리에서 a의 개수임으로 S[..

1. 문제 설명 📌문제 링크f(n) = n이란 숫자의 약수들의 합g(n) = 1~n까지 각 숫자의 약수들의 합 즉 f(1) ~ f(n)의 합2. 접근 방식 🗃️KEY WORD: 누적 합, 시간 복잡도에 대한 감f(n)을 구한다. (1~ 1000000 까지 전체 수에 대해 구한다.)모든 f(n) 배열을 1로 초기화 (1은 무조건 약수에 포함되므로)f(ij) += i(i = 2 ~ 1000000까지 모두 순회, j = 1부터 1씩 증가함. 즉 `ij=i의 배수를 나타냄.`)g(n)은 f(n)의 누적으로 구한다.답을 출력한다.f(i*j) = i를 진행하면, i의 배수에는 i를 무조건 더하고 i가 1~ 1000000까지 모든 수를 순회하기 때문에 각 숫자마다 자신의 약수를 빠짐없이 더할 수 있다. 여기서 다..

1. 문제 설명 📌문제 링크두 배열의 구간합끼리 더해서 목표값인 T가 나오는 횟수를 세는 문제2. 접근 방식 🗃️KEY WORD: Two Pointer, Range sum이번 문제는 각 배열에서 나올 수 있는 구간합을 모두 구해서 List 화 시킨 뒤에, 이 두 List에서 값을 각각 꺼내어 보며, T가 될 수 있는 경우의 수를 세야한다. 한마디로 요약하면 구간합 후보군들 사이에서 Two Pointer로 요약할 수 있다.(1) 왜 그렇게 풀어야 하나요?답: 배열의 원소로 음수가 존재이 문제의 까다로운 점은 배열의 원소로 음수가 존재할 수 있다는 것이다. 누적합을 활용한 구간합을 구하는데 기본이 되는 전제 조건은 "right 포인터를 늘리면 구간합이 커진다. left 포인터를 늘리면 구간합이 줄어든다...