1. 문제 설명 📌문제 링크문제 설명이 어려워서 부연 설명을 하겠다.N개의 울타리와 너비가 X인 룰러가 있다. 울타리의 경우 너비는 1로 고정이고, 높이만 1차원 배열 형식으로 주어진다. 당신은 룰러를 활용하여 페인트를 칠할 것인데, 너비가 X임으로, X 너비 내의 울타리는 한 번에 칠하게 될 것이다. 여기서 중요한 조건은 다음과 같다.(1) 룰러의 부분이 허공에 닿으면 안된다.왼쪽과 같이 일련의 울타리가 주어진다면, 오른쪽 그림의 테두리 안 쪽만 롤러를 돌려 칠할 수 있다는 말이다. 즉 롤러 너비 X 내에 제일 작은 울타리가 색칠의 기준이 된다.(2) 칠한데는 또 칠할 수 있다.다음과 같이 롤러의 너비가 3일 때, 처음 맞딱뜨리는 구간에서는 최대로 칠할 수 있는 높이가 1일 것이다.롤러를 한 칸 옮기..

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 포인터를 늘리면 구간합이 줄어든다...

1. 문제 설명 📌https://www.acmicpc.net/problem/1806 문제가 직관적이라 설명 생략!2. 접근 방식 🗃️KEY WORD: TWO POINTER목표값 보다 Two Pointer 구간 내의 합이 작으면 오른쪽 포인터 이동목표값 보다 크거나 같으면 왼쪽 포인터 이동구간 내 합이 목표값 이상이면 Math.min(이전까지의 최소 개수, 현재 개수)로 최소값 갱신3. 코드 소개 🔎import java.io.*;import java.util.*;public class Main { /* * KEY WORD: 투 포인터 * 1. 목표값보다 작으면 오른쪽 포인터 이동 * 2. 목표값보다 크거나 같으면 왼쪽 포인터 이동 * 3. 목표값과 일치하면 그 개수를 뽑아내..

1. 구간합 알고리즘이란?1차원 배열에서 특정 구간 내의 원소들의 합을 구하는 알고리즘이다.2. 왜 써야 하는가?위의 예시에서 A에서 B까지의 구간 합을 구한다면, 어떻게 구할 것인가? 혹자는 2번 index부터 7번 index까지 for 반복문을 활용해 차례대로 더할 것이다. 혹자는 0에서 A번까지의 누적합을 구하고, 0~B번까지의 누적합을 구해, 둘을 빼서 구할 것이다. 만약 단일 계산이라면, 이런 식의 풀이는 n번의 반복일 뿐이니 괜찮을 수 있다. 하지만, 문제에서 여러 개의 구간합을 반환하길 바란다면? 매번 이러한 반복문을 반복하는 것은 비효율적이다. 이는 시간 초과로 이어질 수 있다.시간 복잡도로 계산해 보겠다. 최악을 상정해야하니, N개의 원소를 가진 배열에서 0~ N~1까지의 계산을 K번 반..

1. 문제 설명 📌문제 링크문제의 설명만 보면 이해하기가 어려운데, 밑의 시뮬레이터를 보면 문제에서 주어진 조건과 로봇의 작동원리는 이해할 만하다.하지만 헷갈리는 것이 있다면 바로, points와 routes의 의미 및 관계라고 할 수 있겠다.(1) 헷갈리는 것 바로 잡기points: 로봇이 방문해야하는 지점의 좌표를 배열 형태로 저장해놓았다.points[i]일 때, 이 i가 방문할 지점의 번호 이고, point[i]의 value가 각각 i란 지점의 행과 열 즉 좌표이다.routes; 로봇별로 방문해야할 지점을 순서대로 나열한 1차원 배열의 묶음이다.routes[i]의 i는 로봇의 번호이고, routes[i]에는 로봇이 방문해야할 지점의 번호가 순서대로 저장되어 있다.예를 들어, routes[2] = ..