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번 반..

0. 사전에 정의할 변수r과 c: 특정 원소의 행과 열 위치N: 2차원 배열의 크기 (2차원 배열은 정사각형 형태)1. 원리90도 회전을 할 경우, 행이 열이 되고, 열이 행이 된다. (서로의 역할이 바뀜)시계 방향으로 회전하면, Before(r,c) = After(c, n-1-r)반시계 방향으로 회전하면, Before(r,c) = After(n-1-c, r)각각 역할 전환 ➜ 하나는 대칭 이동, 하나는 그대로 이다. 왜 그렇게 되는가 그냥 현상이라서 그렇게 알고 가야할 것 같다.

1. 문제 설명 📌문제링크2. 접근 방식 🗃️KEYWORD: SIMULATION어렵게 생각할 것 없이, 지민이가 가진 돗자리 중 큰 것부터 공원의 격자에 일일히 대보면 된다.만약 겹치면 어짜피 둘 수 없기 때문에, 다음 가능한 자리부터 start 한다.첫번째 자리부터 대보았는데, 전부 겹친다. 다음 start 가능한 곳으로 넘어간다.이렇게 쭉 가다가,되는 여백을 만나면 바로 탈출하면 된다. 왜냐하면 우리는 돗자리 큰 거부터 대보고 있었기 때문이다. 지민이는 5x5부터 들고 있었으나, 공원에는 5x5를 둘 자리가 없다.3. 코드 소개 🔎import java.util.*;class Solution { public int solution(int[] mats, String[][] park) { ..