문제 링크 1. 문제 풀이 월곡이가 살아온 날 $N$ 이 최대 $10^6$, 특정 일에 가계부를 수정하거나 특정 구간의 합계를 구하는 쿼리의 수 $Q$ 가 최대 $10^6$ 인 문제로 구간 합을 효율적으로 구할 수 있는 세그먼트 트리 또는 펜윅 트리를 활용하면 해결할 수 있다. 1번 쿼리의 경우 점 갱신을 할 때, 새로운 값으로 변경하는게 아니...

문제 링크 1. 문제 풀이 주어진 구간의 합을 반복적으로 구하고, 특정 값도 변경할 수 있는 상황으로 세그먼트 트리 또는 펜윅 트리를 활용하면 해결할 수 있다. $x > y$ 인 입력이 있음에 주의해야 한다. 2. 코드 1. 세그먼트 트리 [Java] import java.io.*; import java.util.*; publi...

문제 링크 1. 문제 풀이 $1$ 번부터 $N$ 번까지의 사람이 원을 이루며 있을 때, $K$ 번째 사람을 제거하는 과정을 반복하는 문제다. 큐 자료구조를 활용하면 간단하게 해결할 수 있는데 큐의 맨 앞을 바라보며 $K$ 번째가 될 때까지 큐에서 꺼내서 큐 뒤에 넣다가 $K$ 번째면 큐에서 꺼내고 출력한 후 다시 큐에 넣지 않으면 된다. ...

문제 링크 1. 문제 풀이 $1$ 번부터 $N$ 번까지의 사람이 원을 이루며 있을 때, $K$ 번째 사람을 제거하는 과정을 반복하는 문제다. 큐 자료구조를 활용하면 간단하게 해결할 수 있는데 큐의 맨 앞을 바라보며 $K$ 번째가 될 때까지 큐에서 꺼내서 큐 뒤에 넣다가 $K$ 번째면 큐에서 꺼내고 출력한 후 다시 큐에 넣지 않으면 된다. ...

문제 링크 1. 문제 풀이 수열의 길이 $N$ 이 최대 $1,000,000$, 수열에서 특정 원소를 변경하는 쿼리의 수 $M$ 이 최대 $10,000$, 주어진 구간의 곱셈의 결과를 구하는 쿼리의 수 $K$ 가 최대 $10,000$ 인 문제로 쿼리 당 $O(\log{N})$ 의 시간복잡도로 해결할 수 있는 세그먼트 트리를 활용하면 해결할 수 있...

문제 링크 문제 설명 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다. 예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면 array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다. 1에서 나온 배열을 정렬하면...

문제 링크 문제 설명 H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이...

문제 링크 문제 설명 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개...

문제 링크 1. 문제 풀이 슈퍼 마리오가 얻은 점수가 $100$ 에 최대한 가깝게 하는 문제로 가까운 수가 2개면 큰 값을 선택해야 하며, 버섯은 안먹은 순간부터 뒤에 나오는 버섯은 전부 먹을 수 없다. 그냥 조건문 기반으로 구현하는 방식으로 해결해도 되고 누적합을 활용해서 해결해도 된다. 2. 코드 1. 구현 [Java] import...

문제 링크 1. 문제 풀이 활성화된 앱들이 주어져 있고 각 앱은 비활성화 했을 때, 비용 $c$ 와 확보할 수 있는 메모리 $m$ 을 가지고 있다. 이때 $M$ 이상의 메모리를 확보할 때 최소 비용을 알아내야 하는 문제다. 이는 비용을 무게, 확보할 수 있는 메모리를 가치로 간주하는 0／1 배낭 문제로 해결할 수 있다. 각 앱을 비활성화하느냐 ...