기록방

👉 문제링크 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 🔸 문제 분석 🔸 두 배열 A와 B의 부배열의 합으로 T를 만드는 경우의 수를 출력한다. 🔸 문제 풀이 🔸 부배열을 구하는 방법으로 누적합을 이용한다. 입력 배열의 원소는 최대 1,000이므로, int형으로 2개의 배열을 선언해서 2,000 x 4Byte = 8KB가 쓰인다. 배열 A와 B의 누적합을 만든 뒤, 모든 부배열의 합을 구한다. A의 부배열의 수는 A의 원소 ..

💡 합의 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특한 목적의 알고리즘 🚀 합의 배열 S 정의 구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 한다. A[ 0 ]부터 A[ i ]까지의 합 : S[ i ] = A[ 0 ] + A[ 1 ] + A[ 2 ] + ... + A[ i-1 ] + A[ i ] 합 배열은 기존의 배열을 전처리한 배열 합 배열을 미리 구해 놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소 A[ i ] 부터 A[ j ] 까지의 배열 합을 합 배열 없이 구하는 경우, 최악은 i가 0이고 j가 N인 경우로 O(N) 합 배열을 이용하면 O(1) 🚀 합 배열 S를 만드는 공식 S[ i ] = S[ i-1 ] + A[ i ] 🚀 구간 합을 ..

👉 문제링크 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 🔸 문제 분석 🔸 N자리의 수열 중 합이 S이상이 되는 수열 중 가장 짧은 것의 길이를 출력한다. N은 10,000 이하의 자연수이다. S는 0이상, 100,000,000(1억) 이하이다. 수열의 모든 수를 확인하긴 해야한다. 합이 S가 되는 것을 효율적이게 비교하기 위해서, 매번 전부 더하는 것이 아니라 하나씩 더하고 빼며 진행한다. 따라서 투포인터 알고리즘을 사용한다. 🔸 코드 🔸 import java.io.BufferedReade..

👉 문제링크 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 🔸 문제 분석 🔸 n개의 수로 이루어진 수열에서 연속된 k개를 골랐을 때 그 합의 최대값을 출력한다. 전형적인 두 포인터, 슬라이딩 윈도우 문제이다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.util.StringTokeniz..

👉 문제링크 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 🔸 문제 분석 🔸 n개의 입력되는 숫자의 부분 구간 합이 m으로 나누어 떨어지는 경우의 수를 출력한다. n은 100만, m은 100이다. 구간 합을 매번 계산하면 시간이 부족하므로 구간 합 배열을 미리 계산한다. 구간 합 배열 공식 : S[i] = S[i-1] + A[i] 배열에서 구간 합 구하기 ( i ~ j ) : S[j] - S[i-1] 나머지도 미리 계산해 두는 것이 핵심 아이디어 (A + B) ..