문제 링크 1. 문제 풀이 간단하게 $A^B \ (\mathrm{mod}\ C)$ 를 구해야 하는 문제다. $B$ 의 크기가 매우 커질 수 있어서 반복적으로 곱하는 방식으로는 해결할 수 없는데 이진 거듭제곱 이라는 테크닉을 활용하면 해결할 수 있다. 모듈러 연산은 곱셈에 대한 분배가 가능하므로 연산마다 나머지만 취했다. 2. 코드 ...

문제 링크 1. 문제 풀이 $K$ 번째 소수를 출력하는 문제로 소수를 빠르게 판정할 수 있는 에라토스테네스의 체를 활용하면 간단하게 해결할 수 있다. $K$ 가 최대 $500,000$ 이라는 점을 활용해 $500,000$ 번째 소수를 미리 구해보고 해당 수까지의 범위에 대해 에라토스테네스의 체를 적용했다. 2. 코드 1. 풀이 [...

문제 링크 1. 문제 풀이 $(x_1,\ y_1)$ 부터 $(x_2,\ y_2)$ 까지 영역의 합을 $M$ 번 구해야 하는 문제로 매번 반복해서 찾으면 시간이 오래 걸린다. 1차원 누적 합을 응용한 2차원 누적 합 을 적용하면 해결할 수 있다. 2. 코드 1. 풀이 [Java] import java.io.*; import jav...

문제 링크 1. 문제 풀이 $N$ 개의 수에 대해 $M$ 개의 각 구간의 합을 구해야 하는 문제로 매번 주어진 구간의 합을 반복문으로 구하면 $O(NM)$ 의 시간복잡도로 동작한다. 반복되는 구간의 합을 빠르게 구할 수 있는 누적 합을 활용했다. 2. 코드 1. 풀이 [Java] import java.io.*; import ja...

문제 링크 1. 문제 풀이 주어진 좌표를 $y$ 좌표에 대한 오름차순으로, $y$ 좌표가 같다면 $x$ 좌표에 대한 오름차순으로 정렬하는 간단한 문제다. 다만 $N$ 이 최대 $100,000$ 이라서 $O(N^2)$ 보다 빠른 정렬 알고리즘이 필요하다. 2. 코드 1. 풀이 [Java] 2차원 배열로 좌표를 입력받고 람다식을 활...

문제 링크 1. 문제 풀이 주어진 좌표를 $x$ 좌표에 대한 오름차순으로, $x$ 좌표가 같다면 $y$ 좌표에 대한 오름차순으로 정렬하는 간단한 문제다. 다만 $N$ 이 최대 $100,000$ 이라서 $O(N^2)$ 보다 빠른 정렬 알고리즘이 필요하다. 2. 코드 1. 풀이 [Java] 2차원 배열로 좌표를 입력받고 람다식을 활...

문제 링크 1. 문제 풀이 $N$ 개의 수에 대해 $M$ 개의 각 구간의 합을 구해야 하는 문제로 매번 주어진 구간의 합을 반복문으로 구하면 $O(NM)$ 의 시간복잡도로 동작한다. 반복되는 구간의 합을 빠르게 구할 수 있는 누적 합을 활용했다. 2. 코드 1. 풀이 [Java] import java.io.*; import ja...

문제 링크 1. 문제 풀이 주어진 세 변의 길이를 통해 직각삼각형인지 여부를 판단하는 문제로 피타고라스 정리를 활용하면 해결할 수 있다. 주어진 세 변의 길이를 정렬한 후 가장 긴 변의 길이의 제곱이 나머지 두 변의 길이의 제곱의 합이랑 같은지 비교하면 된다. 2. 코드 1. 풀이 [Java] import java.io.*; i...

문제 링크 1. 문제 풀이 다트가 다트판에서 몇 점에 위치하는지 구할 수 있어야 하는 문제로 다트판의 중심과 다트와의 거리를 피타고라스 정리로 구하고 해당 거리가 어떤 고리에 위치하는지 판단하면 다트의 점수를 구할 수 있다. 2. 코드 1. 풀이 [Java] import java.io.*; import java.util.*; ...

문제 링크 1. 문제 풀이 BaekJoon 2565번 - 전깃줄 문제에서 전깃줄의 개수가 최대 $100,000$ 으로 커지고 없애야 하는 전깃줄까지 출력해야 하는 문제다. 이전 문제는 2중 반복문을 활용한 LIS로 해결할 수 있었다면 이제는 이분 탐색을 활용한 LIS 를 활용하면 해결할 수 있다. 2. 코드 1. 풀이 [Java]...