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) { ..

1. 문제 설명 📌문제 링크2. 접근 방식 🗃️KEY WORD: SIMULATION3. 코드 소개 🔎import java.util.*;class Solution { public int solution(int[] wallet, int[] bill) { int answer = 0; Arrays.sort(wallet); Arrays.sort(bill); while(wallet[0] 4. 배운 것들 🎯없음. 꾸준함을 위한 재물

1. 문제 설명 📌문제 설명문제 설명 생략2. 접근 방식 🗃️KEY WORD: GREEDY ALGORITHMGreedy 알고리즘은 매 선택의 순간에 당시 할 수 있는 최선의 선택을 하는 것이 전체 문제에서도 최적의 해를 구하는 것임을 가정하는 알고리즘이다.여기서는 미사일의 묶음을 끝지점 기준 오름 차순으로 정렬하고, 미사일 묶음의 최대한 끝지점에서 차례대로 요격해 나가면 최소한으로 요격 미사일을 사용하는 것이다. 해당 방법은 다음과 같은 이유로 유효하다.미사일을 만나면 무조건 요격해야 한다. 안하고 지나치는 경우는 없다.따라서 미사일을 만나면 최대한 겹치게 삭제해야 한다.하나의 미사일 묶음 A가 다른 미사일 묶음과 최대한 겹치는 경우는 A의 끝지점에서만 발생한다.예를 들어보겠다.다음과 같이 폭격 미사..