[알고리즘] LUT & 투 포인터 : 중복 계산 줄이기

 

 

데이터를 분석하거나 문제를 풀 때, 연속된 구간의 합을 빠르게 구하는 게 핵심인 경우가 많다.

하지만, 배열 크기가 크고, 구간 합을 여러 번 계산해야 하면, 매번 전체 합을 계산하면 시간이 많이 걸리는 문제가 있다.

그래서 1.중복 계산을 제거하거나, 2.효율적인 구간 처리를 하는 방법이 필요하다. 

 

 

이번 글에서는 1.중복 계산을 줄이는 방법 2가지(LUT, 투포인터)를 알아보고자 한다. 

 

 

1. LUT (Look-Up Table)

Look-Up : "찾아본다"

Table : "미리 준비된 값들을 저장해둔 배열/표" 

즉, 복잡한 계산 결과를 미리 구해놓고 테이블에서 꺼내 쓰는 방식을 말한다. 

“메모리(Memory)를  시간(Time)으로 바꾼다”는 전형적인 최적화 기법.

 

• 모든 정확한 입력 값에 대한 결과를 메모리에 저장 할 수는 없으므로 필요한 경우에는 보간 해서 사용한다.
  • 보간은 근사값이 충분히 사용가능하고, 실시간 계산 시간 > 보간 시간 인 경우 사용 

 

1-1. LUT 활용 예시

1. 삼각함수 근사 (게임/그래픽스)

• 정수 각도만 테이블에 저장하고, 소수점 입력 시 선형 보간(linear interpolation) 사용
  • 예: sin(12.7°) 계산 시 sin(12°)와 sin(13°) 사이를 보간

2. 컬러 그레이딩 LUT (3D LUT)

• 영화나 게임에서 색 보정할 때, 3D LUT(33×33×33 색공간) 사용
• 실제 색(RGB 값)이 LUT에 정확히 없으면
  • 삼선형 보간(trilinear interpolation)으로 주변 8개의 색상 값을 보간해 결과 출력
  • ( GPU 텍스처 샘플링이 대표적 사례 )

3. 1D LUT (Shading Ramp Texture)

• 화면에서 밝기값에 따라 다른 색을 입혀서 표현하고 싶을 때, 계산을 매번 하지 않고 미리 준비해둔 색표를 이용하는 것
  • 즉, “밝기 → 색상” 대응표를 만들어 두는 것
• 가로 256픽셀, 세로 1픽셀짜리 Ramp Texture를 만든다.
  • 셰이더에서 N·L (내적) 계산
    • N = 표면 법선 벡터, L = 광원 방향 벡터  ,  내적(N·L) 결과 = 밝기값 → 0~1 범위로 정규화
  • 정규화된 값을 Ramp Texture의 u좌표로 사용
    • 예: N·L = 0.3 → Ramp Texture 가로 256픽셀 중 30% 위치 픽셀 색을 가져옴
• 계단식 LUT: 픽셀을 그대로 사용 → 밝기가 칸마다 뚝뚝 끊겨 카툰풍 명암
• 보간된 LUT: 인접 픽셀 색을 섞어 부드럽게 → 자연스러운 명암

 

4. 물리/시뮬레이션

• 온도, 압력, 밀도 등 물리적 결과를 미리 LUT에 저장
• 입력값이 정확히 없으면 주변 포인트 보간 → 기상 시뮬레이션, 엔진 연료 분사 모델 등

 

 

 

2. 투 포인터 (Tow Pointer)

배열이나 리스트에서 두 개의 인덱스를 사용해, 조건을 만족하는 구간이나 원소를 효율적으로 탐색하는 알고리즘 기법

포인터(pointer) = 배열의 위치(인덱스)를 가리키는 변수

즉, 두 개의 포인터를 움직이며 탐색하며, 불필요한 반복을 줄이는 방식

 

2-1. 기본 아이디어

1. 포인터 두 개 설정: start와 end (또는 left, right)
2. 조건 검사: 현재 구간/값이 문제 조건을 만족하는지 확인
3. 포인터 이동: 조건에 따라 start나 end를 한 칸씩 이동
4. 반복: 배열 끝까지 이동하며 모든 경우를 탐색

 

2-2. 장점

 

• 완전 탐색(Brute Force)은 O(N²) 시간이 걸리지만,
  • Brute Force(완전 탐색:“가능한 모든 경우를 다 해보는 방식”)
• 투 포인터는 포인터가 한쪽 방향으로만 이동하므로 O(N) 안에 해결 가능 ( O(N²) → O(N) 줄어듦 )
• 예: 구간 합, 연속된 자연수 합, 특정 합 찾기 등

 

 

2-3. 투 포인터 활용 예시 ( N의 연속된 자연수 합 찾기 )

2-3-1. 문제

• 1부터 N까지의 연속된 자연수 중 합이 목표값 N이 되는 모든 구간 찾기 
• 예: N = 15 → 가능한 구간 

 

2-3-2. 비효율적 방법 ( Brute Force )

• 매번 구간 합을 처음부터 계산하면 중복 연산 발생
• 시간복잡도: O(N²)

1. start = 1부터
     1 → 1+2 → 1+2+3 … → 1+2+3+4+5 = 15 → 경우의 수 1개
     1+2+3+4+5+6 = 21 (N보다 커짐) → 중단

2. start = 2부터
      2 → 2+3 → 2+3+4+5 = 14 → 아직 작음
      2+3+4+5+6 = 20 (N보다 커짐) → 중단

3. start = 3부터
      3+4+5 = 12 → 아직 작음
      3+4+5+6 = 18 (N보다 커짐) → 중단

4. start = 4부터
     1.4+5+6 = 15 → 경우의 수 2개

5. start = 5부터 … 이런 식으로 계속 진행.
    - 1+2+3+4+5
    - 4+5+6
    - 7+8
    - 15
    총 4가지.

• 이전에 계산했던 부분을 또 계산하므로, 비 효율적이다.

 

2-3-3. 투 포인터 활용 

• total 변수로 현재 구간 합을 저장
  • 구간 확장: end++ → total += end
  • 구간 축소: start++ → total -= start
• 매번 전체 합을 다시 계산하지 않고 추가/제거만 수행

 

2-3-4. 투 포인터의 효율성

• 루프 수행 횟수 ≤ start 증가 횟수 + end 증가 횟수 ≤ 2N
• 따라서 시간복잡도: O(N) (상수배 무시)

 

 

3.정리

• LUT        : 반복되는 계산을 “미리 저장해서 빠르게 불러오기”
• 투 포인터 : 한 번 계산한 걸 다시 하지 않기 위해, 구간을 양쪽 포인터로 이동시키며 탐색

두 기법 모두, 쓸데없는 계산을 줄여서 효율적으로 계산한다.