[Do it! 알고리즘 코딩 테스트 자바] 백준 10986나머지 합- 구간합/나머지 연산의 활용(3일차)

1. 주요 오개념 및 시행착오 (Pain Point)

• 연속된 부분의 정의: '연속된'이라는 표현을 인접한 두 요소의 합으로 한정 지어 오해함. 실제로는 시작점 i와 끝점 j 사이의 모든 요소를 포함하는 임의의 구간 합을 의미함을 인지함.
• 조합(nC_2) 활용의 당위성: 순서가 없는 조합을 사용하는 이유에 대해 의문이 있었으나, 누적 합 나머지가 같은 두 지점을 선택하는 행위가 곧 하나의 유일한 연속 구간을 정의하는 경계선 역할을 수행함을 이해함.
• 시간 복잡도 설계 오류: 모든 구간을 전수 조사하는 O(N^2) 방식은 데이터 100만 개 기준 약 1조 번의 연산이 발생하여 시간 초과(TLE)가 불가피함. O(N)으로의 최적화 필요성을 체감함.

 

2. 핵심 원리 및 수학적 근거 (Logic & Math)

• 나머지 연산의 뺄셈 분배 법칙: 구간 합의 나머지가 0이 되기 위한 조건은 다음과 같음.
•  
• (S[j] - S[i]) % M = 0 -> S[j] % M = S[i] % M
• 수학적 귀결: 누적 합 배열에서 나머지 값이 동일한 두 지점을 선택(nC_2)하면, 그 사이 구간의 합은 반드시 M의 배수가 됨.
• 예시 적용: 나머지 배열이 1 0 0 1 0일 때, 나머지가 1인 인덱스 2개 중 2개를 선택하는2C_2 조합을 통해 구간 합이 M의 배수인 사례 1개를 즉시 도출함.

 

3. 설계 통찰: 기록(Array) vs 통계(Variable)

문제의 요구사항에 따른 데이터 관리 전략의 차이를 습득함.

구분	기록 중심 (Array)	통계 중심 (Variable)
관리 방식	S[N] 배열에 전체 누적 합 저장	currentSum 변수 하나로 합산 유지
사용 사례	다중 쿼리: 임의의 구간 합을 반복적으로 구해야 할 때	전체 개수: 특정 조건을 만족하는 구간의 총합만 필요할 때
장점	임의의 구간 합을 O(1)에 즉시 계산 가능	메모리 사용량을 O(N)에서 O(M) 수준으로 최적화 가능

• 결론: 해당 문제는 조건 만족 구간의 '개수'만 구하면 되므로, currentSum 변수와 나머지 빈도를 체크할 D[M] 배열만으로 충분히 구현 가능함.

 

4. 구현상의 유의점 (Implementation Wisdom)

• 오버플로우 방지: 데이터 N=100만 기준, 가능한 구간의 쌍은 약 10^{11}개임. 이는 int 범위를 초과하므로 결과값 변수는 반드시 long 타입을 사용함.
• Java 실행 효율성: O(N) 로직 적용 시 472ms(0.472초) 소요. 1초 제한 환경에서 Java를 이용한 대용량 데이터 처리의 안정성을 확인 시킴.
• 나머지 0 처리: 누적 합 나머지 자체가 0인 경우, 그 자체로 조건에 부합하는 구간이므로 별도의 카운팅(count++) 혹은 S[0]=0의 가상 지점 처리가 필수적임.

 

5. 향후 확장 개념 (Next Step)

• 2차원 구간 합: 1차원 배열을 확장한 행렬 영역의 누적 합 계산(O(1)) 학습 필요 (예: BOJ 11660).
• 슬라이딩 윈도우: 구간의 길이가 고정된 특수 상황에서의 최적화 기법과 구간 합의 차이점 비교 분석.
• 세그먼트 트리: 데이터의 실시간 업데이트가 발생하는 환경에서의 구간 합 도출(O(\log N)) 자료구조 학습.
• Sparse Table: 구간 합이 아닌 구간 내 최솟값/최댓값(RMQ)을 빠르게 구하기 위한 희소 배열 활용법 고민.