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. 문제 설명 📌문제 링크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의 끝지점에서만 발생한다.예를 들어보겠다.다음과 같이 폭격 미사..

1. 문제 설명 📌문제 링크아날로그 시계의 초침이 시침 혹은 분침과 겹칠 때마다 알람을 울릴 건데, 주어진 시작 시간부터 끝시간 내에 알림이 몇 번 울렸는지 횟수를 반환하는 함수를 작성하는 문제. 시계의 초,분,시침은 연속적으로 움직인다. 따라서 겹치는 시기가 0.001초 단위일 수도, 0.00001초 단위일수도 있다. 이를 다 생각해서 겹치는 횟수를 구해라! (Lv2 맞나?? Lv3로 격상해야할 듯...)2. 접근 방식 🗃️KEY WORD: SIMULATION시계 침들의 겹침 현상을 최대한 코드로 구현해야 한다. 하지만 연속적으로 이루어지는 움직임 속에서 겹치는 순간을 포착한다는 것은 불가능한 일이다. 따라서 겹친다의 기준을 다음과 같이 정한다.(1) 겹친다의 기준각도 상 초침이 시침 혹은 분침보다..

1. 문제 설명 📌문제 링크회의시간의 시작과 끝이 주어질 때, 최대한 많은 강의를 회의실에 배정해라 (A 강의의 끝시간과 B 강의의 시작 시간이 같으면 연달아 배정할 수 있는 것으로 간주한다.) 2. 접근 방식 🗃️KEY WORDS: GREEDY ALGORITHMGreedy Algorithm은 선택의 순간에 최적의 선택지를 고르는 것이 전체 문제에서 최적의 선택을 하는 것이라 가정하는 알고리즘이다.빨리 끝나는 순으로 회의를 정렬제일 빨리 끝나는 회의가 A라면 A 회의 이후에 시작할 수 있으면서도, 최대한 빨리 끝나는 회의를 선택하는 것이 전체 문제에서 봤을 때 최대한 많은 강의를 고를 수 있는 방법임.2번을 모든 회의를 돌아보며 더 이상 고를 수 있는 회의가 없을 때까지 반복 3. 코드 소개 🔎..

1. 문제 설명 📌문제 링크문제에서 수열이 주어지는데, 수열은 기본적으로 모두 더해진다. 하지만 만약 사용자가 임의의 수 2개를 골라서 괄호를 쳤을 경우, 해당 수는 곱해진다. 모든 수는 단 하나의 괄호에 포함되거나 아니면 괄호에 아예 포함되지 않는 2가지 선택지밖에 없다고 했을 때, 수열로 만들 수 있는 최대값을 구하라.예를 들어 수열이 [0,1,2,4,3,5]로 주어졌을 때, 괄호가 없다면 합은 15이지만, 다음과 같이 괄호를 활용하면 0 + 1 + (2*3) + (4*5) 가 되면 값이 27로 최대가 된다.2. 접근 방식 🗃️KEYWORD: GREEDY ALGORITHM(1) 경우의 수 생각하기먼저 주어진 두 개의 수로 최대값을 만들 수 있는 경우는 무엇이 있을까?두 수 모두 0보다 클 때: 이..

1. 문제 설명 📌문제 링크설명이 직관적이라 추가 설명 생략2. 접근 방식 🗃️KEY WORD: Greedy Algorithm동전 수가 무한하기 때문에 Greedy 알고리즘을 적용하면 된다. Greedy 알고리즘은 매 순간 최적의 선택을 하는 것이다. 여기서 최적의 선택은 가능한한 큰 단위의 동전을 사용하여 동전 개수를 줄이는 것이다. 따라서 내림차순으로 동전 단위를 하나씩 훑으며, K원을 최대한 큰 단위의 동전으로 차감한다.내림차순으로 동전 조회만약 현재 조회 중인 동전으로 K원을 나눌 수 있다면? 나눈 몫만큼 동전을 사용 가능한 것임으로 몫을 답에 누적시킴K원은 (해당 동전의 단위 x 몫) 만큼 차감되었으므로, 나머지만큼만 남아있는 것이다. 따라서 K = K%단위로 갱신한다.1,2,3번을 K ==..