중복 제거 원리란? — 다양한 알고리즘에 적용되는 핵심 개념

중복 제거 원리는 단순히 누적합 알고리즘에만 쓰이는 기법이 아닙니다.

수학, 컴퓨터 과학, 알고리즘 전반에 걸쳐 "겹치는 영역을 조정하여 정확한 값을 계산하는 방법"으로 널리 사용됩니다.

---

📌 중복 제거 원리의 핵심

"겹치는 것을 한 번만 포함시키기 위해, 불필요하게 더해진 값을 빼주고, 과하게 빠진 값을 다시 더하는 것"

이 원리는 포함-배제 원리(Inclusion-Exclusion Principle)의 구조를 기반으로 합니다.

---

🧠 대표적인 활용 사례

1️⃣ 누적합(Prefix Sum, 특히 2D, 3D 확장)

2차원 누적합에서 사각형 구간 합을 구할 때, 다음과 같이 겹치는 부분을 제거합니다:

sum = S[y2][x2] 
    - S[y1-1][x2] 
    - S[y2][x1-1] 
    + S[y1-1][x1-1]

이때 마지막 항은 겹쳐서 두 번 제거된 영역을 보정하기 위해 더해줍니다.

---

2️⃣ 포함-배제 원리 (Inclusion-Exclusion Principle)

두 집합 A, B의 합집합 원소 수를 구할 때:

|A ∪ B| = |A| + |B| - |A ∩ B|

→ A와 B에 공통으로 들어있는 원소는 두 번 더해졌기 때문에 한 번 빼줍니다.

세 집합으로 확장되면:

|A ∪ B ∪ C| = |A| + |B| + |C|
             - |A∩B| - |B∩C| - |C∩A|
             + |A∩B∩C|

→ 중복된 교집합을 제거하고, 세 번 빠진 공통 부분을 한 번 더해주는 구조입니다.

---

3️⃣ 이미지 처리 (Integral Image)

OpenCV 등에서는 픽셀 누적합을 활용한 사각형 영역 처리 시에도 똑같은 원리를 사용합니다.

적분 이미지 (Integral Image)에서 사각형 내의 픽셀 합을 구할 때:

sum = A - B - C + D

이는 바로 누적합의 중복 제거 공식과 동일합니다.

---

4️⃣ 고차원 누적합 (3D, 4D 등)

3차원 배열에서 누적합을 구할 때도 같은 방식으로 교차된 면, 선, 점을 제거/보정합니다.

예:

S[x][y][z]
- S[x-1][y][z] - S[x][y-1][z] - S[x][y][z-1]
+ S[x-1][y-1][z] + S[x-1][y][z-1] + S[x][y-1][z-1]
- S[x-1][y-1][z-1]

중복 제거 원리가 차원이 높아져도 동일하게 적용된다는 걸 보여줍니다.

---

📌 마무리

중복 제거 원리는 단순히 누적합 계산을 위한 테크닉이 아닙니다.
여러 겹치는 구조를 정확히 정리하고 계산하기 위한 보편적인 개념입니다.

누적합, 조합, 이미지 처리, 고차원 데이터 등 다양한 문제에서 동일하게 등장하므로,
이 원리를 이해하는 것은 알고리즘 실력 향상에 큰 도움이 됩니다.