[Coding Test]누적합

 

 

 

---

1. 누적합 (Prefix Sum)

누적합을 왜 써야함?

• 정의 : 누적 합이란 배열의 각 요소에 대해 그 요소까지의 모든 요소의 합을 저장하는 방식.
• 쓰는 이유
  • 1. 구간합을 빠르게 구하기 위해서
  • 2. 특정값이 구간에 있는지 확인하기 위해서

 

1. 구간합을 빠르게 구하는 경우

• 배열에서 구간합을 구하는 경우일 때 사용한다.

int[] arr = {1, 2, 3, 4, 5};
int[] prefixSum = new int[arr.length];

prefixSum[0] = arr[0];
for (int i = 1; i < arr.length; i++) {
  prefixSum[i] = prefixSum[i - 1] + arr[i];
}

int start = 1;
int end = 3;

int sum = prefixSum[end] - prefixSum[start - 1];

System.out.println("구간 합: " + sum); // 출력: 10

• 이 경우에서는 1번부터 3번 인덱스에 있는 구간의 합을 구하고 싶을때 사용을 한 예시이다.

 

2. 특정값이 구간에 있는지 확인하는 경우

• 배열에서 특정 값이 구간에 있는지를 확인할 수 있다.

public static boolean isValueInRange(int[] arr, int start, int end, int value) {
  // 누적합 계산
  int[] prefixSum = new int[arr.length];
  prefixSum[0] = arr[0];
  for (int i = 1; i < arr.length; i++) {
    prefixSum[i] = prefixSum[i - 1] + arr[i];
  }

  // 구간 합 계산
  int sum = prefixSum[end] - prefixSum[start - 1];

  // 특정 값 비교
  return sum == value;
}


int[] arr = {1, 2, 3, 4, 5};
int start = 1;
int end = 3;
int value = 6;

boolean isPresent = isValueInRange(arr, start, end, value);

if (isPresent) {
  System.out.println("값 " + value + "이 구간에 존재합니다.");
} else {
  System.out.println("값 " + value + "이 구간에 존재하지 않습니다.");
}

 

 

3. 카운팅 정렬에서 사용하는 경우

• 카운팅 정렬에 관련해서는 따로 알고리즘을 올릴 예정이다. 그걸 참고하면 될듯.

 

---

2. 누적합 문제

• 1. 나머지 합 : 링크 ->
  • 이 문제는 누적합 + 나머지 배열을 만들어서 시간복잡도를 줄이는 방식으로 문제를 푼다.
• 2. 

 

🔎 3. 실제 사용 예시

💡 그래서 도대체 왜 배우고 어디에 쓰는건데?

-> 데이터 압축, 이미지처리, 암호화에 실제 사용이 된다.

 

1. 데이터 압축 (Data Compression)

• 빈도 기반 압축(Frequency-Based Compression)
  • 각 값의 등장횟수를 누적합으로 저장해서 공간 절약.
  • 예를 들어, 배열 [1, 2, 3, 1, 2, 3]의 경우 각 값의 등장 횟수를 [2, 2, 2]로 누적합으로 저장하면 원래 배열보다 공간을 절약할 수 있다.
• 델타 인코딩 (Delta Encoding) 
  • 연속된 값들의 차이를 누적합으로 저장하여 공간을 절약한다.
  • 예를 들어, 배열 [1, 3, 5, 7, 9]의 경우 델타 인코딩을 사용하면 [1, 2, 2, 2]로 저장하여 공간을 절약할 수 있다.
• 이동 평균 (Moving Encoding) 
  • 연속된 값들의 평균값을 누적합으로 저장하여 데이터를 요약한다.
  • 예를 들어, 센서 데이터 배열의 경우 이동 평균을 사용하면 데이터의 변화 추세를 파악하는 데 도움이 된다.
• 범위 쿼리 (Subarray Sum Problem)
  • 특정 범위 내의 값들의 합을 빠르게 계산한다.
  • 예를 들어, 누적합을 사용하면 특정 기간 동안의 매출 데이터를 빠르게 계산할 수 있습니다.

2. 이미지 처리 (Image Processing)

• 이미지 밝기 조절(Image Brightness Adjustment)
  • 이미지의 각 픽셀 값에 누적합을 적용하여 이미지의 밝기를 조절할 수 있습니다.
• 히스토그램 평활화(Histogram Equalization)
  • 이미지 히스토그램의 불균형을 없애기 위해서 누적합을 사용할 수 있다.
  • 히스토그램 평활화는 이미지의 명암 대비를 개선하고 노이즈를 줄이는 데 도움이 된다.
• 이미지 필터링(Image Filtering)
  • 특정 이미지 필터를 구현하기 위해서 누적합을 사용할 수 있다.
  • 예를 들어, 누적합을 사용하여 평균 필터, 가우시안 필터, 소벨 필터 등을 구현할 수 있다.
• 에지 추출(Edge Detection)
  • 이미지의 에지를 추출하기 위해 누적합을 사용할 수 있다.
  • 에지 추출은 이미지에서 중요한 특징을 추출하고 객체 인식, 이미지 분할 등에 사용된다.
• 이미지 합성( Image Composition)
  • 여러 이미지를 합성하기 위해 누적합을 사용할 수 있다.
  • 이미지 합성은 파노라마 이미지 생성, HDR 이미지 생성 등에 사용된다.

3. 암호화

• 메세지 인증 (Message Authentication)
  • 누적합을 사용하여 메시지 무결성 검증할 수 있다.
  • 메시지 변조 여부 확인을 할 수 있다.
• 디지털 서명 (Digital Signature)
  
  • 누적합을 사용하여 서명 위조 방지할 수 있다.
  • 서명 검증 시 서명자 확인할 수 있다.
• 해시 함수 (Hash Function)
  • 누적합을 사용하여 해시함수를 구현할 수 있다.
  • 충돌 가능성을 감소한다.
• 스트림 암호화 (Stream Cipher)
  
  • 누적합을 사용하여, 스트림 암호화 알고리즘에서 암호화 키 생성할 수 있다.