문제 링크 1. 문제 풀이 주어진 임금으로 만들 수 있는 수열에서 구간의 길이가 $m$ 인 구간 중 구간 합이 가장 큰 경우를 찾는 문제다. 누적합을 활용해도 해결할 수 있고 슬라이딩 윈도우를 활용해도 해결할 수 있다. 주어진 임금의 합이 정수 타입 범위를 넘어갈 수 있음에 주의해야 한다. 2. 코드 1. 누적합 [Java] impor...

문제 링크 1. 문제 풀이 두 배열을 합친 배열을 정렬한 뒤 출력하는 문제로 두 배열의 크기의 합만큼의 배열에 원소를 옮기고 정렬해도 되고, 각 배열을 정렬 후 투 포인터로 원소를 순서대로 넣어줘도 된다. 투 포인터 방식은 병합 정렬의 병합 과정과 유사하다고 봐도 된다. 2. 코드 1. 정렬 [Java] import java.io.*;...

문제 링크 1. 문제 풀이 두 정수는 콤마로 구분된다. 따라서 콤마를 기준으로 파싱한 후 합을 구하면 된다. 2. 코드 1. 구현 [Java] StringTokenizer 를 활용하여 콤마를 기준으로 파싱했다. 이후 $A + B$ 의 결과물을 StringBuilder 에 담았다가 한번에 출력하는 방식으로 최적화했다. import ja...

문제 링크 1. 문제 풀이 문자열 $S$ 에 포함된 정수는 콤마로 구분된다. 따라서 콤마를 기준으로 파싱한 후 각 정수의 개수를 구하면 된다. 2. 코드 1. 파싱 [Java] split 메서드와 배열의 길이인 length 를 조합하여 정수의 개수를 구했다. import java.io.*; public class Main { ...

문제 링크 1. 문제 풀이 삼각형의 종류에 따라 다른 문구를 출력하는 문제로 삼각형이 될 수 없는 조건은 가장 긴 변의 길이가 다른 두 변의 길이 보다 크거나 같은 경우인 것만 주의하면 된다. 2. 코드 1. 구현 [Java] import java.io.*; import java.util.*; public class Main { ...

문제 링크 1. 문제 풀이 에라토스테네스의 체에서 탐색한 수들을 카운팅하면 되는 문제로 에라토스테네스의 체 로직 중간에 탐색에 거쳐간 값들을 카운팅하는 방식으로 해결했다. 이때 에라토스테네스의 체는 중복 탐색을 하므로 방문 체크를 통해 방문한 적 없는 값들만 카운팅 해야 한다. 2. 코드 1. 에라토스테네스의 체 [Java] impor...

문제 링크 1. 문제 풀이 주어진 수들을 소인수분해한 결과를 출력하는 문제로 에라토스테네스의 체를 활용해 소수들을 얻고 이 소수들로 $1$ 이 될 때까지 반복적으로 나누면 된다. 2. 코드 1. 소인수분해 [Java] 소수를 리스트로 얻은 후 각 소수들로 나눌 수 있으면 나누고 몫을 카운팅하는 방식으로 구현했다. 에라토스테네스의 체의 ...

문제 링크 1. 문제 풀이 간단하게 $A^B \ (\mathrm{mod}\ C)$ 를 구해야 하는 문제다. $B$ 의 크기가 매우 커질 수 있어서 반복적으로 곱하는 방식으로는 해결할 수 없는데 분할 정복을 이용한 거듭제곱이라는 테크닉을 활용하면 해결할 수 있다. 2. 코드 1. 분할 정복을 이용한 거듭제곱 [Java] 반복문을 활용해 ...

문제 링크 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 java.util.*...