<h3>🥅 들어가며</h3>코딩 테스트 준비를 하다보면 배열과 관련해서 구간 합(Range Sum)에 대한 문제를 마주하게 된다.구간합이란 간단하게 말하면 배열의 특정 구간 내의 원소들의 합을 구하는 문제이다. 굳이 코딩 테스트가 아니어도 특정 기간의 통계량을 계산하는 여러 현실 문제에 대해 구간 합은 자주 쓰이는 개념이다. 이러한 구간합을 어떻게 효율적으로 구할 수 있는지 알아보자.<h3>➕ 합 배열의 개념 및 구간 합의 계산</h3>구간합을 시간 복잡도를 고려하여 가장 효율적으로 계산하는 방법은 합배열(Prefix Sum) 이다. 합배열이란 배열의 누적 합을 저장하는 배열이다. 배열 A가 {1, 2, 3, 4, 5} 라면 합배열 S는 {1, 3, 6, 10, 15} 인 식이다. 수식으로는 다음과 같다.<img src="https://image.until.blog/woonideveloper423/article/1718540749059" alt="until-512">이렇게 구한 합배열 S를 이용하여 배열 A의 구간합을 쉽게 구할 수 있다. 예를 들어 배열 A의 인덱스 (i,j)의 구간 합을 구한다 하면 0~j까지의 누적 합에서 0~(i-1)의 누적 합을 빼면 된다. 이를 합배열을 사용한 수식으로 표현하면 다음과 같다.<img src="https://image.until.blog/woonideveloper423/article/1718540793537" alt="until-513"><h3>❓합 배열을 사용해서 구간 합을 구하는 것이 왜 효율적일까?</h3>합 배열을 사용하지 않고 구간합을 계산하는 방법은 구간의 모든 원소를 직접 더하는 방법이다. 다만 이는 시간 복잡도가 O(n) 이며 구간의 크기나 구간의 합을 구하는 개수 등이 클수록 연산 시간은 이에 비례하여 늘어난다. 따라서 시간 제한을 고려한다면 적절한 방법이 아니다.<pre spellcheck="false"><code class="language-java">int rangeSum(int[] numbers, int start, int end) { // 구간 합 수동 구
 int sum = 0;
 for (int i = start; i &lt;= end; i++) { // 시간 복잡도(O(n))
 sum += numbers[i];
 }
 return sum;
}
int result = rangeSum(numbers, 2, 4); // 구간 합을 여러개 구해야 한다면 메서드를 여러 번 실행해야 함
</code></pre>따라서 다음과 같이 합배열을 생성한 후 이미 생성된 합배열의 인덱스를 사용해서 구간 합을 구하는 것이 시간 복잡도 O(1) 로 훨씬 효율적이다.<pre spellcheck="false"><code class="language-java">// 합배열 생성
int[] prefixSum = new int[numbers.length];
prefixSum[0] = numbers[0];
for (int i = 1; i &lt; numbers.length; i++) {
prefixSum[i] = prefixSum[i-1] + numbers[i];
}// 구간 합
int rangeSum(int[] prefixSum, int i, int j) {
if (i == 0) {
return prefixSum[j];
} else {
return prefixSum[j] - prefixSum[i-1]; // 합배열 사용해서 계산 -&gt; 이미 생성된 배열의 요소로 계산 하므로 시간 복잡도O(1)
}
}</code></pre><h3>📚 참고자료</h3><ul class="tight" data-tight="true"><li><a target="_blank" rel="noopener noreferrer nofollow" href="https://www.inflearn.com/course/%EB%91%90%EC%9E%87-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%9E%90%EB%B0%94/dashboard">https://www.inflearn.com/course/%EB%91%90%EC%9E%87-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%9E%90%EB%B0%94/dashboard</a></li></ul>

합 배열 및 구간 합 알고리즘에 대해 알아보자

[Algorithm] 합배열(Prefix Sum)과 구간 합(Range Sum)

<blockquote>본 포스팅은 <a target="_blank" rel="noopener noreferrer" class="notion-link-token notion-focusable-token notion-enable-hover" href="https://www.acmicpc.net/">백준 온라인 저지</a> 에서 제공하는 문제의 풀이를 비상업적 목적으로 게시하였습니다.</blockquote><h3>ℹ️ 문제 정보</h3><a target="_blank" rel="noopener noreferrer nofollow" href="https://www.acmicpc.net/problem/28432">https://www.acmicpc.net/problem/28432</a><img src="https://image.until.blog/woonideveloper423/article/1718543306513" alt="until-521"><img src="https://image.until.blog/woonideveloper423/article/1718543323501" alt="until-522"><h3>🔍 문제 분석</h3><ul class="tight" data-tight="true"><li>입력받는 숫자의 개수 N이 1≤N≤100 이므로 최대 100자리의 N은 int,long 자료형으로 저장할 수 없다. 문자열 형태로 저장해야 한다.</li><li>문자열로 저장 후 각각의 문자로 분리한다. → 문자열을 문자의 배열로 분리한다.</li><li>각각의 문자를 숫자로 변환한다.</li><li>변환된 숫자들을 더한다.</li></ul><h3>🖊️ 구체화 하기</h3><ol class="tight" data-tight="true"><li>입력받은 숫자의 개수만큼 String으로 저장한다.</li><li>String으로 입력받은 값을 char[]형으로 변환한다.</li><li>인덱스 0부터 배열을 탐색하며 각 값을 정수형으로 변환하고 결과값에 더하여 누적한다.</li></ol><h3>🗒️ 의사 코드 작성</h3><ol class="tight" data-tight="true"><li>N 값 입력받기</li><li>길이 N의 숫자를 입력받아 String 변수sNum에 저장하기</li><li>sNum을 다시 char[]g형 변수 cNum에 변환하여 저장하기</li><li>int 형 변수 sum선언하기</li><li>for(cNum 길이만큼 반복하기) { 배열의 각 자릿값을 정수형으로 변환하며 sum에 더하여 누적하기 }</li><li>sum 출력</li></ol><h3>✅ 나의 정답 코드</h3><img src="https://image.until.blog/woonideveloper423/article/1718543526334" alt="until-523"><pre spellcheck="false"><code class="language-java">import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/* 1. N 값 입력받기
 2. 길이 N의 숫자를 입력받아 String 변수 sNum에 저장하기
 3. sNum을 다시 char[]형 변수 cNum에 변환하여 저장하기
 4. int 형 변수 sum선언하기
 5. for(cNum 길이만큼 반복하기)
 {
 배열의 각 자릿값을 정수형으로 변환하며 sum에 더하여 누적하기
 }
 6. sum 출력
 */
public class 숫자의합구하기11720 {

 public static void main(String[] args) throws IOException {

 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 int N = Integer.parseInt(br.readLine());
 String sNum = br.readLine();

 char[] cNum = sNum.toCharArray();
 int sum = 0;

 for (char num : cNum) {
 sum += num - '0'; // *아스키 코드 값을 이용한 문자의 숫자 변환
 }
 System.out.println(sum);
 }
}</code></pre><h3>🤔 회고</h3><ul class="tight" data-tight="true"><li>문제 분석 → 구체화 → 의사 코드 작성의 사고 순서를 앞으로도 적용해 봐야겠다.</li><li>아스키코드를 사용한 문자의 숫자 변환은 매우 빈번하게 쓰이므로 숙지해 둘 것.</li></ul><h3>📚 참고자료</h3><ul class="tight" data-tight="true"><li><a target="_blank" rel="noopener noreferrer nofollow" href="https://www.inflearn.com/course/%EB%91%90%EC%9E%87-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%9E%90%EB%B0%94/dashboard">https://www.inflearn.com/course/%EB%91%90%EC%9E%87-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%9E%90%EB%B0%94/dashboard</a></li></ul>

배열 관련 숫자의 합 문제를 풀어보자