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

문제 링크 1. 문제 풀이 주어진 수열에 대해 특정 구간에 포함된 홀수의 개수를 구하는 쿼리, 짝수의 개수를 구하는 쿼리, 특정 위치의 원소를 바꾸는 쿼리를 처리해야 하는 문제다. 홀수와 짝수는 $2$ 로 나눈 나머지로 구분할 수 있는데 이때 수열에서 홀수는 $1$, 짝수는 $0$ 으로 치환하면 홀수의 개수는 해당 구간의 합과 동일하게 되며...

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

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

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

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

문제 링크 1. 문제 풀이 BaekJoon 11866번 - 요세푸스 문제 0 에서 $N$ 과 $K$ 의 범위가 더 커진 문제로 여전히 큐를 활용하면 동일하게 해결할 수 있다. 2. 코드 1. 풀이 [Java] import java.io.*; import java.util.*; public class Main { publ...

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

문제 링크 1. 문제 풀이 주어진 배열 array에 대해 i 번째 숫자부터 j 번째 숫자까지 자르고 정렬했을 때, k 번째에 있는 수를 구하는 문제다. 각 쿼리들이 원본 배열에 대해 수행되기 때문에 주어진 원본 배열 자체를 정렬할 경우 이후 쿼리들이 이전 쿼리의 영향을 받게 되어 원본 배열은 수정하면 안된다. 2. 코드 1. 풀이...

문제 링크 1. 문제 풀이 H-Index는 h번 이상 인용된 논문이 h편 이상일 때 h의 최댓값이다. 이 문제는 정렬을 활용하면 간단하게 해결할 수 있는데 먼저 주어진 citations를 오름차순으로 정렬한다. [3, 0, 6, 1, 5]의 경우 [0, 1, 3, 5, 6]이 된다. 이렇게 정렬을 하면 특정 논문보다 인용 횟수가 많은 논문은...